BOJ - 20922 겹치는 건 싫어

20922 겹치는 건 싫어 : https://www.acmicpc.net/problem/20922

---

Problem

---

Solve

최장 연속 부분 수열의 길이를 구하고 최대길이 N이 N*N이 1억을 넘기때문에 투포인터를 고려해 볼 필요가 있다.

start와 end를 0으로 놓고 end가 수열의 끝에 도달할때까지 start와 end에 포함되어있는 숫자를 map에 갱신을 하면서 K개 이상 같은 수를 포함하고 있다면 그 이하의 개수를 가질때까지 start를 이동시켜주는 것을 반복한다.

---

Code

public class 겹치는건싫어 {
	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 K = Integer.parseInt(st.nextToken());

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

		//start와 end가 포함하고 있는 값의 개수 저장
		HashMap<Integer, Integer> map = new HashMap<>();

		int answer = 0;
		int start = 0;
		int end = 0;
		while (end < sequence.length) {
        	//두 포인터 사이에 값을 포함하고 있다
			if (map.containsKey(sequence[end])) {
            	//만약 해당 값이 K개를 이미 포함하고 있다면
				if (map.get(sequence[end]) == K) {
                	//해당 값이 K개 미만이 될때까지 start를 이동시켜주고 start가 가리키던 값의 개수를 빼준다.
					while (map.get(sequence[end]) >= K) {
						map.put(sequence[start], map.get(sequence[start])-1);
						start++;
					}
				}
				map.put(sequence[end],map.get(sequence[end])+1);
			} else {
            	//해당 값을 포함하지 않고있다면 새로운 값 추가
				map.put(sequence[end],1);
			}

			//조건을 만족하는 두 포인터 사이의 길이 중 가장 긴 값 갱신
			answer = Math.max(answer, end-start+1);
			end++;
		}

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

---

Result

---

Reference