[백준]20922번. 겹치는 건 싫어 (JAVA)

https://www.acmicpc.net/problem/20922

---

문제

---

풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] arr = new int[n];
        int[] count = new int[100001];

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

        int start = 0, end = 0, max = 0;

        while(end < n){
            while(end < n && count[arr[end]] + 1 <= k){
                count[arr[end]]++;
                end++;
            }
            int len = end - start;
            max = Math.max(max, len);
            count[arr[start]]--;
            start++;

        }

        System.out.println(max);

    }
}

 

풀이는 일반적인 투포인터와 비슷하다. 하지만 여러 가지 고민점이 존재했다.

일단 [100001] 크기의 정수 배열을 선언해도 메모리 크기 조건에 부합하는가이다. int는 4바이트이기 때문에 대략 1,000,000의 크기가 돼야 4바이트이다. 걱정될 수 있었겠지만, 문제 조건이 1024mb이기 때문에 여유롭다.

 

100000까지니까 100001의 배열을 직접 선언한 뒤에 하나씩 관리한다. 또한 arr의 인덱스에서 나오는 정수값을 그대로 사용하기 위해(카운트의 인덱스를 보다 편리하게 관리하기 위해) 하나 더 크게 선언하여 인덱스값을 숫자값과 일치시킨다.

 

마지막으로 실수가 나오기 쉬운 부분은 int len = end -start; 부분이다.
간단하게 생각하면 인덱스 0~1의 길이를 구하기 위해서는 end - start +1을 해야 한다. 즉 +1을 해야 하나 말아야 하나의 문제가 생긴다.

 

하지만 문제 풀이 과정을 잘 살펴보면 end 값은 ++로 while문을 탈출한 상태이다. 이때 start값도 ++가 되어야 위에서 말한 0~1 사이의 문제가 생기는 것인데 아직 start가 바뀌지 않았으므로 +1이 되어있는 상황이라고 생각해도 된다.