백준 - 20922 겹치는 건 싫어 (java)

📒 20922 겹치는 건 싫어

📌 풀이법

기본적인 two pointer 문제였다. two pointer 영역에 존재하는 수 종류마다 갯수를 세주어 해결했다.

Two Pointer

리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘

---

📌 소스코드

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

public class Main {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    int[] cnt = new int[111111];
    int[] num = new int[222222];

    void solution() throws Exception {
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int a = Integer.parseInt(st.nextToken());
            num[i] = a;
        }
        int l = 0, r = 0, len = 0;
        while (l < n) {
            if (r < n && cnt[num[r]] < k) {
                cnt[num[r]]++;
                r++;
            } else {
                cnt[num[l]]--;
                l++;
            }
            len = Math.max(len, r - l);
        }
        System.out.println(len);
    }

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

---

📌 리뷰

two pointer 문제임을 알게된 후에는 쉽게 풀었지만, 처음에 떠올리지 못해서 헤맸었다. 리스트에서 어떤 연속된 영역을 순차적으로 접근하면서 처리해야 한다면 two pointer를 생각해보자.