[JAVA] 백준 q20922 - 겹치는 건 싫어

20922번: 겹치는 건 싫어

 

---

의식의 흐름

투 포인터로 앞뒤 이동하면서 최대 길이 구하면 되겠징,,
> 투 포인터의 시간 복잡도 = O(N)

풀이 과정

1. 수열의 길이(N), 같은 숫자의 최대 개수(K)를 입력받는다.
2. N개의 숫자를 배열(nums)에 담아둔다.
3. 만약 `N != 1`인 경우, 최장 연속 부분 수열의 길이(maxLength)를 구한다. -> `findMaxLength()`
3-1) start, end 포인터를 둔다.
3-2) 포인터 사이 숫자들에 대해 K개를 넘는 중복 숫자가 있는지 확인한다.
         만약, K개를 넘는 중복 숫자가 없다면 maxLength를 업데이트하고 end 포인터를 뒤로 이동한다.
         만약, K개를 넘는 중복 숫자가 존재한다면 해당 중복 숫자 하나를 벗어날 때까지 start 포인터를 이동한다.
4. maxLength를 출력한다.

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
    public static int N, K;
    public static int[] nums;
    public static Map<Integer, Integer> map = new HashMap<>(); // 숫자 포함 횟수 저장할 map
    public static int maxLength = 1;

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

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

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

        if (N != 1) {
            findMaxLength();
        }
        bw.write(Integer.toString(maxLength));
        bw.flush();

        br.close();
        bw.close();
    }

    public static void findMaxLength() {
        int start = 0;
        int end = 0;

        while (end < N) {
            int endNum = nums[end];
            int endNumCnt = map.getOrDefault(endNum, 0);
            map.put(endNum, endNumCnt + 1);

            if (endNumCnt < K) {
                maxLength = Math.max(maxLength, end-start+1);

                end++;
                continue;
            }

            while(true){
                int startNum = nums[start];
                int startNumCnt = map.get(startNum);
                map.put(startNum, startNumCnt - 1);

                start++;

                if(startNum == endNum){
                    end++;
                    break;
                }
            }
        }
    }
}