📙[Algo] 24.01.23 알고리즘

알고리즘 문제) BOJ 11728. 배열 합치기

11728번: 배열 합치기

문제 요약

• 정렬되어 있는 두 배열 A, B
• 두 배열을 합친 다음 정렬해서 출력하기

시간 제한

• 1.5초

입력

• 배열 A의 N, 배열 B의 크기 M ( 1 ≤ N, M ≤ 100만)
• 배열 A가 주어짐
• 배열 B가 주어짐
• 배열의 수는 절댓값이 10억보다 작거나 같은 정수

출력

• 두 배열을 합친 후 정렬한 결과 출력

접근법

• 정렬할 때, Arrays.sort()를 사용할 경우 평균 O(nlogn)이 발생하고, 최악의 경우 O(n*n)이 발생
  • 배열 A의 길이 100만개, 배열 B의 길이 100만개라면 둘이 합치면 200만개가 되고 이를 정렬할 경우, 최악의 경우 4조의 연산이 발생할 수 있다.
• 정렬 최적화 하기
  • A배열, B배열 각각 포인터를 하나씩 둔다.
    2 3 5 9
    a 
    1 4 7
       b
  • A[a] < B[b] 이므로, A[a]를 새로운 배열에 담고, a+=1
  • 1 4 7 b
  • A배열, B배열 각각 포인터를 하나씩 둔다.

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] arrA  = new int[N];
        int[] arrB  = new int[M];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arrA[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            arrB[i] = Integer.parseInt(st.nextToken());
        }

        int[] answer = new int[N+M];
        int a = 0, b = 0, idx = 0;
        while (idx < N + M) {

            if(a >= N || b >= M){
                if (a < N) {
                    for (int i = a; i < N; i++) {
                        answer[idx++] = arrA[i];
                    }
                } else if (b < M) {
                    for (int i = b; i < M; i++) {
                        answer[idx++] = arrB[i];
                    }
                }
                break;
            }


            if (arrA[a] > arrB[b]) {
                answer[idx++] = arrB[b];
                b += 1;
            } else if (arrA[a] <= arrB[b]) {
                answer[idx++] = arrA[a];
                a += 1;
            }

        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N + M; i++) {
            sb.append(answer[i]+" ");
        }

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 14465. 소가 길을 건너간 이유 5

14465번: 소가 길을 건너간 이유 5

문제 요약

• 1번부터 N번까지의 횡단보도 존재
• 고장난 신호등이 B개 존재
• 연속한 K개의 신호등이 존재하도록 하도록 수리하려 함
• 최소 몇 개의 신호등을 수리?

시간 제한

• 2초

입력

• N, B, K (1≤B,K≤N)
  • 1 ≤ N ≤ 10만
• B줄에 고장난 신호등이 주어짐

출력

• 정상 작동하는 연속 k개 신호등이 존재하려면 최소 몇 개 수리?

접근법

1. 완전 탐색으로 접근
   1 2 3 4 5 6 7 8 9 10
   f  f  t  t  f  t  t  t  f   f
   • 신호등을 고치는 경우의 수를 구하고(1개부터 B개까지), 그때 연속 K개 신호등이 존재하는 경우 고친 신호등의 개수가 가장 작은 값으로 갱신
2. 최적화 하기
   • 고장난 신호등 번호들을 나열한다.
     1 3 4 6 10 11 14
   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 / K=6
   • 연속된 신호등 6개씩 묶어서 이동시켜가며, 고장 난 신호등 개수를 체크한다.
   • 이때 고장난 신호등 개수를 체크해야한다.
     • 배열을 하나 만들어서 누적된 고장난 신호등 개수를 담아둔다.

       1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
       1	1	2	3	3	4	4	4	4	5	6	6	6	7	7

       • cnt = arr[e] - arr[s-1]
   • 1 2 3 4 5 6
     • cnt = 4
   • 2 3 4 5 6 7
     • cnt = 3
   • 3 4 5 6 7 8
     • cnt = 3
   • 4 5 6 7 8 9
     • cnt = 2
   • 5 6 7 8 9 10
     • cnt = 2
   • 6 7 8 9 10 11
     • cnt = 3
   • 7 8 9 10 11 12
     • cnt = 2
   • 8 9 10 11 12 13
     • cnt = 2
   • 9 10 11 12 13 14
     • cnt = 3
   • 10 11 12 13 14 15
     • cnt = 3

고민

• 고장난 신호등 개수 누적합 배열 만드는거에서 시간을 많이 썼다.
• 투포인터로 어떻게 풀라는거지? 고민을 많이 했는데, 너무 어렵게 생각한 거였다. 그냥 연속된 신호등 K개씩 묶어서 하나하나 이동하면서 고장난 신호등 개수 체크하는 문제였다.

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        int[] broken = new int[N];
        for (int i = 0; i < B; i++) {
            broken[Integer.parseInt(br.readLine())-1]++;
        }

        for (int i = 1; i < N; i++) {
            broken[i] += broken[i - 1];
        }

        int s = 1, e = s + (K-1), answer = broken[K-1];
        while (e < N) {
            answer = Math.min(answer, broken[e] - broken[s - 1]);
            s++;
            e++;
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 15961. 회전 초밥  

15961번: 회전 초밥

문제 요약

• 벨트 임의의 위치부터 k개 접시를 연속해서 먹을 경우 할인된 가격으로 제공
• 초밥의 종류가 적힌 쿠폰으로, 위의 행사에 참여할 경우 해당 초밥 하나 무료 제공
• 위 행사에 참여하여 최대한 다양한 종류의 초밥을 먹으려고 함!

시간 제한

• 1초

입력

• 회 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시 개수 k, 쿠폰 번호 c가 주어짐
  • 2 ≤ N ≤ 300만
  • 2 ≤ d ≤ 3000
  • 2 ≤ k ≤ 3000 ( k ≤ N)
  • 1 ≤ c ≤ d
• 회전 방향(→)을 따라갈 때 초밥의 종류가 1~각 줄마다 주어짐

출력

• 회전 초밥 벨트에서 먹을 수 있는 초밥의 가짓수의 최댓값 출력

접근법

7 9 7 30 2 7 9 25

• 순환이므로 인덱스가 N을 초과하면 %N으로 갱신
• 시작 포인트 s, 끝나는 포인트 e를 지정
• s=0, e=k-1부터 시작해서 s가 다시 0으로 올 때까지 실시 ⇒ 최대 300만연산 횟수 발생
• 가짓수 계산을 어떻게 진행할까?
  • 모든 케이스 일일이 다 체크하면 안 됨 ⇒ 300만*3000으로 시간초과
  • 최적화 필요
    • 0부터 k-1까지 방문체크를 한다.(+1)
      • 이때 방문 체크 배열은 3010정도 길이를 갖고 있음
        • 방문할 때마다 1씩 증가
        • 추가로 쿠폰번호 c도 방문 체크!
      • 동시에 현재 초밥 가짓수까지 기록한다.
    • 그 다음 한 칸 우측으로 이동할 때마다
      • visited[sushi[s]] -= 1; s-=1;
      • e+=1; visited[sushi[e]] += 1
      • 이때 가짓수(cnt)는 (s : 이동전, e: 이동후)
        • visited[sushi[s]]
          • visited[sushi[s]]>1 : cnt
          • visited[sushi[s]]==1 : cnt-=1
        • visited[sushi[e]]
          • visited[sushi[e]] ≥1 : cnt
          • visited[sushi[e]] == 0 : cnt +=1
    • 초밥 가짓수가 최댓값이 될 때까지 갱신반복…

고민

• while문 탈출 조건으로 순회 하나를 끝냈을 때로 하기위해 s=0부터 시작했는데, 그렇게 해버리니까 s=0, e=K-1부터 시작하면 아예 while문이 동작하지 않는다.
• 그렇다고 s=1, e=k부터 하면 s=0, e=k-1에서 한 칸 이동할 때 발생하는 가짓수 처리를 못한다.
• 그래서 중간에 if문으로 break를 걸었는데 뭔가 좀 그렇다..

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 접시의 수
        int d = Integer.parseInt(st.nextToken()); // 초밥의 가짓 수
        int k = Integer.parseInt(st.nextToken()); // 연속해서 먹는 접시 수
        int c = Integer.parseInt(st.nextToken()); // 쿠폰 번호

        int[] visited = new int[3010];
        int[] sushi = new int[N];
        for (int i = 0; i < N; i++) {
            sushi[i] = Integer.parseInt(br.readLine());
        }

        visited[c]++;
        int cnt = 1;
        for (int i = 0; i < k; i++) {
            if(visited[sushi[i]] == 0) cnt++;
            visited[sushi[i]]++;
        }


        int s = 0, e = k-1, ans = cnt;
        while (true) {

            if (visited[sushi[s]] == 1) cnt--;
            visited[sushi[s]]--;
            s = (s + 1) % N;

            if (s == 0) break;

            e = (e + 1) % N;
            if(visited[sushi[e]] == 0) cnt++;
            visited[sushi[e]]++;

            ans = Math.max(ans, cnt);
        }

        bw.write(String.valueOf(ans));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 23032. 서프라이즈~

23032번: 서프라이즈~

문제 요약

• 1부터 N명의 학생, 학생별로 먹고 싶은 스테이크 그램 수 지정.
• 다음 규칙으로 당첨자들에게 스테이크를 나눠줌
  1. 임의로 연속된 학번의 학생을 정함
  2. 임의로 대상 학생들을 두 그룹으로 나눔
     • 이 때 한 그룹의 학생들은 학번이 인접
     • 최소 1명 이상 존재
  3. 두 그룹의 스테이크 무게 합의 차 E (큰 그룹 - 작은 그룹)
  4. E가 최솟값인 두 그룹이 당첨
  5. 여러가지 존재 시 스테이크 무게 합이 가장 큰 두 그룹이 당첨
• 당첨자들의 스테이크 무게 합 구하기

시간 제한

• 1초

입력

• N ( 2 ≤ N ≤ 2,000)
• 1번부터 N번 학생까지 설문조사에 적은 스테이크 무게 정수 W가 주어짐
  • 1≤ W ≤ 10000

출력

• 이벤트에 당첨된 학생들의 스테이크 무게 합을 출력

접근법

N = 6

2 1 5 2 4 4

1. 완전 탐색으로 접근하기
   • 2명부터 N명까지 임의로 이벤트 대상 학생들을 선택하는 모든 경우의 수에 대해
     • 2중 for문
       • for i 0~N-2 : 대상 학생 시작 지점
         • for j i+1~N-1 : 대상 학생 끝 지점
   ⇒ 여기까지 2000*2000 = 4,000,000 ( 400만 )
   • 두 그룹으로 나눌 수 있는 모든 경우의 수에서
     • for k i~j-1 : 기준 점 [i~k, k+1~j]
   ⇒ 여기까지 200020002000 = 8,000,000,000 (80억) 시간초과 발생
   ⇒ 해당 부분 최적화 할 것  
   • E가 최솟값인 경우 찾기, 여러 개일 경우 무게 합이 가장 큰 경우 찾기  
     • 무게 합 구할 때도 일일이 방문하면서 합할 경우 추가 시간 발생
       ⇒ 여기도 최적화 필요
2. 최적화 하기
   • 두 그룹으로 나누는 경우와 스테이크 무게합 구하는 부분을 최적화 할 것
   • 무게합 최적화
     • 전체 무게 = 18
     • 결국 연속된 학생들로 두 그룹으로 나누기 때문에 누적합 배열(acc) 사용
       2 1 5 2 4 4 (i=1, j=N)
       

       2

       3

       8

       10

       14

       18

   • 그룹 나누기 최적화
     • 최소 1명부터 그룹이 만들어진다. s→0,e→0부터 시작
       2 3 8 10 14 18
       s             e
     • s→1, e→5
       • acc[e] = 14이므로, 두 그룹의 무게는 14와 4
         • 두 그룹의 무게 차는 14
       • 현재, e는 s기준 올 수 있는 가장 큰 인덱스값이다. 여기서 무게 차를 줄이기 위해서 e-=1;
     • s→1, e→4
       • acc[e] = 10이므로, 두 그룹의 무게는 10과 8
         • 무게 차 : 2
       • e-=1;
     • s→1, e→3
       • acc[e] = 8이므로, 두 그룹의 무게는 8과 10
         • 무게 차 : 2
       • e -= 1;
     • s→1, e→2
       • acc[e] = 3이므로, 두 그룹의 무게는 3과 15
         • 무게 차 12
       • 값이 오히려 커졌으므로 더 이상 탐색 종료
         • 이걸 체크하기 위해서는 전에 기록해둔 무게 차 변수를 하나 더 추가한다.

1.  

• 최솟값이 나올 수 있는 경우가 여러 개 있을 수 있으니까, 정답을 기록할 때 단순히 무게차의 최솟값만 기록하지 말고, 추가로 두 그룹의 무게 합까지 기록한다.
  • ansDiff < diff
    • ansDiff= diff, ansSum = sum
  • ansDiff == diff
    • ansSum < sum
      • ansSum = sum

고민

• 이게 왜 투 포인터일까?
  • 포인터 하나로만 했는데,,,
  • 그룹 시작지점 i가 start포인트가 되는 건가???
• 누적합 구할 때랑 뒤에 누적합 배열에서 두 그룹별 무게 구할 때 i=0부터 시작하면 i-1일 때 인덱스 오류 떠서 N+1배열로 선언해서 사용했다.
  • 다음부터 누적합 쓸 때 처음부터 배열 크기를 1늘려야겠다.
• beforeDiff라는 변수 만들어서 무게차가 커지는 경우 while문 탈출하도록 조건 걸었는데,, 이것말고 다른 방법은 없을까??

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[] acc = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            acc[i] = Integer.parseInt(st.nextToken()) + acc[i-1];
        }

        int p = 0, diff = 0, sum = 0, ansSum = 0, ansDiff = Integer.MAX_VALUE, beforeDiff = 0;
        for (int i = 1; i <= N-1; i++) {
            for (int j = i + 1; j <= N; j++) {
                p = j - 1;
                beforeDiff = Integer.MAX_VALUE;

                while (p >= 0) {
                    diff = Math.abs((acc[p]-acc[i-1]) - (acc[j] - acc[p]));
                    sum = acc[j] - acc[i-1];

                    if(beforeDiff < diff) break;

                    if (ansDiff > diff){
                        ansDiff = diff;
                        ansSum = sum;
                    }else if (ansDiff == diff) {
                        if (ansSum < sum) ansSum = sum;
                    }

                    p -= 1;
                    beforeDiff = diff;
                }

            }
        }

        bw.write(String.valueOf(ansSum));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 22862. 가장 긴 짝수 연속한 부분 수열 (large)

22862번: 가장 긴 짝수 연속한 부분 수열 (large)

문제 요약

• 길이가 N인 수열 S
• 수열 S는 1이상인 정수로 이루어져 있음
• 원하는 위치에 있는 수를 골라 최대 K번 삭제 가능
• 이때 최대 K번 원소를 삭제한 수열에서 짝수로 이루어져있는 연속 부분 수열 중 가장 긴 길이 구하기

시간 제한

• 1초

입력

• N K
  • 1≤N≤100만
  • 1≤K≤10만
• 수열 S
  • 1≤원소의 값≤100만

출력

• 수열 S에서 최대 K번 원소를 삭제한 수열에서 짝수로 이루어진 연속 부분 수열 중 가장 긴 길이 찾기

접근법

K=2

1 2 3 4 5 6 7 8

1. 먼저 완전 탐색으로 접근하기
   • 재귀로 depth가 2가 될 때까지 수열 중 2 개의 원소를 찾아 제거하고, 수열 앞에서부터 짝수로 시작하는 부분수열을 찾아 가장 길이가 긴 값으로 갱신한다.
   • 100만의 k승(원소 K개 삭제한 경우들) * 100만(짝수로 시작하는 연속 부분 수열 최장 길이 찾기)이므로 엄청난 연산 시간이 발생
2. 최적화 진행하기
   1 2 3 4 5 5 6 6 8
      s
      e
   
   • 홀수만 제거하면 된다.
   • 구간 시작 포인터인 s, 끝 포인터인 e를 만든다.
     • 이 두개 포인터는 무조건 짝수를 가리킨다.
     • 초기에는 s와 e를 같은 곳을 가리키도록 한다.
   • 제거한 개수 delCnt = 0;
   • s → 2, e→ 2
     • delCnt=0;
     • e+=1;
     • len = 1
   • s→2, e→3
     • e→3일 때 홀수이므로
       • delCnt+=1;
     • e+=1
     • len = 1
   • s→2, e→4
     • delCnt = 1
     • e+=1
     • e→4일 때 짝수이므로 len += 1
     • len = 2
   • s→2, e→5
     • delCnt += 1 → 2
     • e+=1
   • s→2, e→5
     • delCnt += 1 → 3
     • s→2일때 짝수이므로 len-=1
     • s+=1
     • len = 1
   • s→3, e→5
     • delCnt = 3
     • s+=1
     • s→3일때 홀수이므로 delCnt-=1
     • len = 2
   • s→4, e→5
     • delCnt = 2
     • e+=1
     • len = 1
   • s→4, e→6
     • delCnt = 2
     • e+=1
     • e→6일 때 짝수이므로 len += 1
     • len = 2
   • s→4, e→6
     • delCnt = 2
     • e+=1
     • e→6일 때 짝수이므로 len += 1
     • len = 3
   • s→4, e→8
     • delCnt = 2
     • e+=1
     • e→8일 때 짝수이므로 len += 1
     • len = 4
   • 종료조건 : e ≥ N

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] arr = new int[N+1];
        st = new StringTokenizer(br.readLine());
        int s = -1, e = -1;
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());

            if (s == -1 && arr[i] % 2 == 0) {
                s = i;
                e = i;
            }
        }

        int delCnt = 0, len = 1, answer = 0;
        while (0 <= e && e < N) {

            if (delCnt > K) {
                if (arr[s] % 2 == 0) len--;
                else delCnt--;
                s++;
            } else {
                answer = Math.max(answer, len);
                e++;
                if (arr[e] % 2 == 0) len++;
                else delCnt++;
            }

        }


        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 15831. 준표의 조약돌

15831번: 준표의 조약돌

문제 요약

• 1~N개까지 일렬로 검은색과 흰색 조약돌이 있음
• 이때 시작 지점을 임의로 정하고, 원하는 지점까지 조약돌을 줍는다.
  • 단 구간을 정할 때 아래 기준 충족
    1. 검은색 조약돌은 B이하
    2. 흰색 조약돌은 W이상
• 이때 최대 구간 길이 구하기

시간 제한

• 1초

입력

• 조약돌의 총 개수 N, 원하는 검은색 조약돌 최대 개수 B, 원하는 하얀색조약돌 최소 개수 W가 주어짐
  • 1 ≤ N ≤ 30만
  • 0 ≤ B, W, B+W ≤ N
• N개의 조약돌의 정보 ( B : 검은색, W : 흰색)

출력

• 걸을 수 있는 가장 긴 구간 길이 구하기, 없다면 0 출력

접근법

N = 10, B = 1, W = 2 WBBWWBWWBW

1. 완전 탐색으로 생각하기
   • 시작지점과 끝지점을 각각 지정해준 이중 for문을 사용
   • 이때 모든 케이스에 대해서 조건을 충족하는 경우 찾고 최대 구간 길이로 갱신
   ⇒ 30만30만30만 ⇒ 시간초과
2. 최적화 하기
   • 먼저 구간의 조약돌 갯수를 일일이 체크하기 번거로우므로 미리 누적합배열을 사용해서 기록할 것(W, B 갯수 모두 기록해야므로 2차원 배열)

     0

     1,0

     1,1

     1,2

     2,2

     3,2

     3,3

     4,3

     5,3

     5,4

     6,4

   • 구간 구하기
     1 2 3 4 5 6 7 8 9 10
     W B B W W B W W B W
     s
     e
     
     • s→1, e→1
       • bCnt = acc[e][1] = 0 < B
       • wCnt = acc[e][0] = 1 < W (X)
       • e+=1
     • s→1, e→2
       • bCnt = acc[e][1] = 1 == B
       • wCnt = acc[e][0] = 1 < W (X)
       • e+=1
     • s→1, e→3
       • bCnt = acc[e][1] = 2 > B (X)
       • wCnt = acc[e][0] = 2 == W
       • s+=1
     • s→2, e→3
       • bCnt = acc[e][1] - acc[s-1][1] = 2 > B (X)
       • wCnt = acc[e][0] - acc[s-1][1] = 0 < W (X)
       • s+=1, e+=1
     • s→3, e→4
       • bCnt = acc[e][1] - acc[s-1][1] = 1 == B
       • wCnt = acc[e][0] - acc[s-1][1] = 1 < W (X)
       • e+=1
     • s→3, e→5
       • bCnt = acc[e][1] - acc[s-1][1] = 1 == B
       • wCnt = acc[e][0] - acc[s-1][1] = 2 == W
       • e+=1 → 혹시 더 가능성 있는 케이스가 있을 수 있으니
     • s→3, e→6
       • bCnt = acc[e][1] - acc[s-1][1] = 2 > B (X)
       • wCnt = acc[e][0] - acc[s-1][1] = 2 == W
       • s += 1
     • s→4, e→6
       • bCnt = acc[e][1] - acc[s-1][1] = 1 == B
       • wCnt = acc[e][0] - acc[s-1][1] = 2 == W
       • e+=1
     • s→4, e→7
       • bCnt = acc[e][1] - acc[s-1][1] = 1 == B
       • wCnt = acc[e][0] - acc[s-1][1] = 4 > W
       • e+=1
     • s→4, e→8
       • bCnt = acc[e][1] - acc[s-1][1] = 1 == B
       • wCnt = acc[e][0] - acc[s-1][1] = 4 > W
       • e+=1
     • s→4, e→9
       • bCnt = acc[e][1] - acc[s-1][1] = 2 > B (X)
       • wCnt = acc[e][0] - acc[s-1][1] = 4 > W
       • s+=1
     ⇒ 이렇게 구간 이동하면서 구간 길이 최댓값을 갱신한다. 이때 종료 조건은 s > e인 순간 ⇒ e>N일떄
     ⇒ 검정 조약돌이 B보다 큰 경우만 s+=1 하고, 나머지는 e+=1로 바꿈(코드 깔끔하게 하기 위해)

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());

        String road = br.readLine();
        int[][] acc = new int[N+1][2]; // 0 : 검정색 누적개수, 1: 하얀색 누적개수
        // 조약돌 갯수 누적합 배열에 담기
        for (int i = 1; i < N + 1; i++) {
            if (road.charAt(i - 1) == 'B') {
                acc[i][0] = acc[i - 1][0] + 1;
                acc[i][1] = acc[i - 1][1];
            } else {
                acc[i][0] = acc[i - 1][0];
                acc[i][1] = acc[i - 1][1] + 1;
            }
        }

        // 구간별 조건 충족여부 체크 & 충족시 구간 길이 최댓값으로 갱신
        int s = 1, e = 1, answer = 0, bCnt = 0, wCnt = 0;
        while (e <= N) {
            bCnt = acc[e][0]-acc[s-1][0];
            wCnt = acc[e][1]-acc[s-1][1];

            if(bCnt <= B && wCnt >= W) answer = Math.max(answer, e - s + 1);

            if (bCnt > B) s++;
            else e++;

        }


        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 1806. 부분합

1806번: 부분합

문제 요약

• 10,000이하 자연수로 이루어진 길이 N짜리 수열
• 연속된 수들의 부분합 중 그 합이 S이상 되는 것 중, 가장 짧은 것 출력

시간 제한

• 1초

입력

• N S
  • 10 ≤ N < 10만
  • 0 < S ≤ 1억

출력

• 구하려는 최소 길이

접근법

N=10 S=15 5 1 3 5 10 7 4 9 2 8

1. 완전 탐색
   • 2중 for문을 사용해서 시작점과 끝점을 정하고, 원소 하나하나 접근해서 더한 후 S이상인지 체크
   ⇒ 10만10만10만 시간 초과
2. 최적화 진행
   • 구간 정하는 부분이랑 합 구하는 부분 모두 최적화 필요 ⇒ 0.5초 안에 들어와야 하니 ⇒ 즉 최대한 10만 연산 안에 이루어지도록 할 것
   • 일단 처음부터 입력 받을 때부터 전체 수열 원소의 합을 구한다. sum = 54
   • 현재까지의 원소 합을 변수에 기록 sum
     • 이동할 때마다 sum에서 더하고 빼고,,
   • s → 0, e→ 0를 가리키고 시작
     5 1 3 5 10 7 4 9 2 8
     s
     e
     • s→0, e→0
       • sum : 5 < S
       • e+=1
       • sum += arr[e];
     • s→0, e→1
       • sum : 6 < S
       • e+=1
     • s→0, e→2
       • sum : 9 < S
       • e+=1
     • s→0, e→3
       • sum : 14 < S
       • e+=1
     • s→0, e→4
       • sum : 24 > S
       • s+=1
     • s→1, e→4
       • sum : 19 > S
       • s+=1
     • s→2, e→4
       • sum : 18 > S
       • s+=1
     • s→3, e→4
       • sum : 15 == S
       • 정답 찾음 ⇒ 답 갱신
       • e +=1
     • 위 과정을 반복한다.
     • 종료 조건 : e ≥ N

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());

        int[] arr = new int[N+1];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int s = 0, e = 0, sum = arr[0], answer = Integer.MAX_VALUE;
        while (e < N) {

            if (sum < S) {
                e++;
                sum += arr[e];
            } else {
                if (sum >= S) {
                    answer = Math.min(answer, e - s + 1);
                }
                sum -= arr[s];
                s++;
            }
        }

        if(answer == Integer.MAX_VALUE) answer = 0;

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}