[Java] 백준 20922 - 겹치는 건 싫어 (투포인터)

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

정답 코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] NK = br.readLine().split(" ");
        int N = Integer.parseInt(NK[0]);
        int K = Integer.parseInt(NK[1]);
        String[] seqStr = br.readLine().split(" ");

        //mapToInt는 IntStream을 반환. intStream.toArray()는 int[]를 반환
        int[] seq = Arrays.stream(seqStr).mapToInt(Integer::parseInt).toArray();
        //map은 Stream을 반환. Stream.toArray()는 object[]를 반환
//        int[] seq2 = Arrays.stream(seqStr).map(Integer::parseInt).toArray();

        int answer = 0;

        int s = 0;
        int e = 0;

        Map<Integer, Integer> map = new HashMap<>();

        while (s <= e && e < N) {
            if (map.getOrDefault(seq[e], 0) < K) {
                map.put(seq[e], map.getOrDefault(seq[e], 0) + 1); //증가
                answer = Math.max(answer, e - s + 1);
                e++;
                continue;
            }
            map.put(seq[s], map.get(seq[s]) - 1); //감소
            s++;
        }

        System.out.println(answer);
    }
}

연속 부분 수열을 구하는 문제는 투포인터의 단골 유형이다. 출제 빈도가 많지는 않지만 너무 연습이 안돼있는 것 같아 풀게 되었다.

시나리오

1. 원소의 개수 카운팅을 위해 map을 생성해준다.
2. start포인터와 end포인터를 생성하고 end가 가르키는 원소가 K개 보다 작을 때 그 원소의 개수를 추가하고 연속 부분 수열의 최대 길이를 갱신, end++ 해준다. 부분 수열의 길이는 end-start+1이 된다.
3. end가 가르키는 원소가 K개와 같을 때는 더 추가할 수 없으므로 end포인터를 고정시켜놓고 start++해준다. 이 때 start포인터가 가르키고 있던 원소를 감소시켜야 한다.
4. while문이 종료되면 answer를 출력한다.

시나리오를 구현할 때 end포인터를 증가시키는 코드와 원소의 개수를 추가하는 코드, 그리고 최댓값을 갱신하는 코드의 순서를 알맞게 배치해야 한다.
뒤죽박죽되면 귀찮아진다..

리마인더

Map은 Stream을 반환하고 MapToXXX은 XXXStream을 반환한다.
XXXStream.toArray()는 XXX[]을, Stream.toArray()는 Object[]를 반환한다.
따라서 스트림을 매핑한 뒤 Array로 collect하고자 할 땐 자료형에 맞는 map메서드를 사용하면 되겠다.