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

알고리즘 스터디 (투포인터)

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

 

 

# 문제

홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K$K$개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.

 100000$100\,000$ 이하의 양의 정수로 이루어진 길이가 N$N$인 수열이 주어진다.  이 수열에서 같은 정수를 K$K$개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.

 

# 예제

입력 : 

첫째 줄에 정수 N$N$ (1≤N≤200000$1 \le N \le 200\,000$)과 K$K$ (1≤K≤100$1 \le K \le 100$)가 주어진다.

둘째 줄에는 a1,a2,...an${a_1, a_2, ... a_n}$이 주어진다 (1≤ai≤100000$1 \le a_i \le 100\,000$)

9 2
3 2 5 5 6 4 4 5 7

 

출력 :  조건을 만족하는 최장 연속 부분 수열의 길이를 출력

7

 

# 필요개념

투포인터는 start와 end 두 개의 지점에서 일정 조건에 따라 이동하며 문제를 해결하는 방식이다. 해당 문제도 투포인터를 이용하여 풀 수 있다.

 

신경쓸 조건은 두가지이다. 

• 같은 원소가 몇개 들어있는가
• start와 end의 위차가 배열길이를 넘어는가

이 두 가지 조건에 걸리지 않으면 end를 한 칸씩 이동시키고, 해당 위치의 원소 개수를 카운트한다.

만약 조건에 걸린다면, 길이를 측정한다.

start가 1, end가 4라면 길이가 3인 수열이 되는 것이다. 길이는 계속 길이의 최대값을 따로 저장해 나가며 되고, 다시 위 두 가지 조건을 만족할 때까지 start를 한 칸씩 이동시킨다. 쉽게 말하면 end 위치에 있는 값과 같은 값이 나올 때까지 start를 이동시키면 되는 것이다.

 

# Code

import java.io.*;
import java.util.StringTokenizer;
public class Main {
    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 limit = Integer.parseInt(st.nextToken());
        int[] inputs = new int[N];
        int[] cnt = new int[100001];

        st = new StringTokenizer(br.readLine());
        for (int i = 0 ; i < N ; i++) {
            inputs[i] = Integer.parseInt(st.nextToken());
        }
        int start = 0;
        int end = 0;
        int max = -1;
        while (end < N) {
            while (end < N && cnt[inputs[end]] < limit) {
                cnt[inputs[end]]++;
                end++;
            }
            int length = end - start;
            max = Math.max(max, length);
            cnt[inputs[start]]--;
            start++;
        }
        System.out.println(max);
    }
}

 

# 결과