[백준] Silver I. 겹치는 건 싫어

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

 

 

사용 알고리즘 

• 투 포인터

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int n, k; // n: 정수 , k: k개 이하 겹치는 수
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

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

        int hi = 0;
        int result = 0;
        int[] counts = new int[100002];
        for(int lo = 0; lo < n; lo++) {
            while(hi < n && counts[arr[hi]] < k) {
                counts[arr[hi]]++;
//                System.out.println(arr[hi] + " " + counts[arr[hi]]);
                hi++;
            }

            // 같은 원소 갯수가 K가 넘을 때 루프를 빠져나온다
            result = Math.max(result, hi - lo);
            counts[arr[lo]]--;
        }
        System.out.println(result);
    }
}

 

 

회고

 

같은 원소를 K개 이하일 때 체크하는 자료구조를 뭐를 써야하지? 에서 고민이 많았다.

• 맵을 사용하여 등장 횟수를 저장
• 리스트를 사용하여 contains 일 때 등장 횟수를 증가시켜줌

리스트를 사용한 방식은 특정 원소에 대한 등장 횟수를 계산할 수 없기 때문에 틀린 방식이다. 맵을 사용하는 방식은 생각 자체는 옳았으나 계산 과정에 있어서 로직이 틀렸어서 남의 코드를 보고 배열로 풀이하게 되었다.

 

기존 코드에선, 루프를 빠져 나왔을 때

if (hi == n) break;

counts[arr[hi]]--;

 

이런식으로 로직을 구현해서 OOB에러가 발생하지 않도록 설정했는데, 

 

10 1
1 1 2 1 2 1 3 4 5 6

 

이 예제 케이스에 대해서 돌려보면 최장 수열은 [2,1,3,4,5,6]라서 답은 6인데, 2가 나오게 된다.

 

while 문 안에서 hi가 n-1인 동안 동작하고, n이 된 순간 루프를 빠져 나온다.

 

그런데, 루프 밖에서 hi == n일 때 break를 터트려버리기 때문에 마지막 원소까지 도달하지 못하는 것이다.

 

그렇기 때문에 break 조건을 없애주고, 등장 횟수를 줄여주는 인덱스를 hi가 아닌 lo로 설정해야한다.

counts[arr[lo]]--;

 

 

 

시작점이 어떻게 변하는지, 또 원소의 등장 횟수를 어떻게 감소시킬 것인지 생각을 더 깊게 해야겠다.