[자바] 백준 25822 - 2000문제 푼 임스 (java)

 문제 : boj25822

---

 

필요 알고리즘 개념

• 누적 합(prefix sum)
  
  • 내 경우엔 이걸 메인 아이디어로 사용했다. 문제 태그에 없긴하다.
• 투 포인터 (two pointer)
  
  • 누적합을 사용한 아이디어에 대해 시간복잡도를 줄이기 위해 사용했다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  내 경우엔 누적합을 사용해 특정 구간에 대해 스트릭이 유지됬다고 가정할 때 필요한 스트릭 프리즈의 수를 O(1)로 알 수 있게 하는게 메인 아이디어였다. 혹시 누적합을 모른다면 '누적 합(prefix sum), 2차원 누적합(prefix sum of matrix) with java' 글을 참고하자.

 

 

1. 입력으로 받은 코인 C를 기반으로 사용 가능한 스트릭 프리즈의 수를 우선 구해놓자. (코드의 strict)

String c = br.readLine();
int strict = 0;
if (c.compareTo("1.98")>=0)
    strict = 2;
else if (c.compareTo("0.99")>=0)
    strict = 1;
    
내 경우엔 최대한 double형 연산을 피하는걸 좋아해서 위와 같이 했다.

double c = Double.parseDouble(br.readLine());
int strict = 0;
if (c >= 1.98)
    strict = 2;
else if (c >= 0.99)
    strict = 1;

그냥 이렇게 해도 동일하게 동작한다.

 

 

2. 우선 두 번째 출력해줘야 하는 '임스가 문제를 최대로 많이 푼 개수'는 입력받으면서 최대값을 찾아주면 되므로 별 문제가 되지 않는다 (가장 긴 구간을 구하고 그 중 최대로 많이 푼 개수가 아니라 그냥 모든날 중 최대로 많이 푼 개수이다.)

int max = 0;	// 이걸 그냥 두 번째 줄에 출력해주면 된다.
for (int i = 1; i <= n; i++) {
    int cur = Integer.parseInt(st.nextToken());
    ...
    max = Math.max(max, cur);
}

 

 

3. '2'만 처리하고나면, 입력값의 입력으로 주어진 수의 크기는 의미가 없어진다. 1이상이라면 아무튼 하나라도 푼거고, 0이라면 안푼거다. 따라서 안푼날을 기준으로 누적합을 구해줬다. 그럼 임의의 날 A와 B(A<=B)에 대해 [A, B] 구간에 대해 스트릭을 유지하기 위해 필요한 스트릭 프리즈의 개수 O(1)로 알 수 있다.

int max = 0;
for (int i = 1; i <= n; i++) {
    ..
    arr[i] = arr[i-1] + (cur==0?1:0);	// 누적합 계산!
    ..
}

  즉, 누적합을 계산한 배열을 arr이라 할 때, arr[x]은 첫째날부터 x날까지 스트릭을 유지하기 위해 필요한 스트릭 프리즈의 개수이다. arr[B]-arr[A-1]은 그럼 A번째 날부터 B번째 날까지 스트릭을 유지하기 위해 필요한 스트릭 프리즈의 개수가 된다.

 

 

4. 그럼 이제 우리가 해줄건 누적합을 이용해 구한 필요 스트릭 프리즈의 개수가 '1'에서 구한 strict보다 작거나 같은 모든 구간 중 가장 큰 구간을 찾는 것이다. 물론 모든 구간을 직접 보게되면 O(N^2)이므로 통과할 수 없다. 따라서 구간을 찾기 위해 투 포인터를 사용했다.

  두개의 포인터 s, e에 대해 s=1번째, e=1번째를 가르키게 한다. 이후 필요 스트릭 프리즈의 개수가 '1'에서 구한 strict보다 작거나 같다면 가능한 경우이므로 범위를 늘려서 더 찾아보기 위해 e를 증가시켜주고, 불가능한 경우라면 s를 증가시켜 구간을 감소시켜준다. 이걸 통해 가능한 모든 구간을 O(N)에 확인해볼 수 있다. 최종적으로 O(N*1) = O(N)으로 풀 수 있다.

int s = 1, e = 1;
int maxStrict = 0;
while (e <= n) {
    int need = arr[e]-arr[s-1];	// need : [s, e]구간이 스트릭 유지를 하기 위해 필요한 스트릭 프리즈의 개수
    if (need <= strict) {
        maxStrict = Math.max(maxStrict, e-s+1);
        e++;
    } else {
        s++;
    }
}

 

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String c = br.readLine();
        int strict = 0;
        if (c.compareTo("1.98")>=0)
            strict = 2;
        else if (c.compareTo("0.99")>=0)
            strict = 1;

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        int max = 0;
        for (int i = 1; i <= n; i++) {
            int cur = Integer.parseInt(st.nextToken());
            arr[i] = arr[i-1] + (cur==0?1:0);
            max = Math.max(max, cur);
        }

        int s = 1, e = 1;
        int maxStrict = 0;
        while (e <= n) {
            int need = arr[e]-arr[s-1];
            if (need <= strict) {
                maxStrict = Math.max(maxStrict, e-s+1);
                e++;
            } else {
                s++;
            }
        }
        System.out.println(maxStrict);
        System.out.println(max);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}