[백준 / BOJ] 20922 겹치는 건 싫어

문제

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

20922번: 겹치는 건 싫어

N개의 수가 있는 수열이 주어진다.

이 수열중 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 문제다.

---

풀이

투 포인터로 풀은 문제다.

최장 연속 부분 수열이기때문에, 답이 될수있는 수열은 모두 붙어있어야한다.

 

따라서, 투 포인터로 left,right값을 지정한 후에 탐색하면 2N시간만에 답을 구할 수 있다.

 

메인 소스코드

    private int getLongestArr(){
        int ret = 0, right = 0, left = 0;
        while(right < N){
            if(!increase(right++)) while(!decrease(left++) && left < right);
            ret = Math.max(ret, right - left);
        }
        return Math.max(ret, right - left);
    }

(코드를 이쁘게 짤려고하다가 반례를 엄청 만든 문제였다.)

 

반례

6 1

1 1 2 2 3 3

 

답 : 2

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/BOJ%20source%20code/20922%20%EA%B2%B9%EC%B9%98%EB%8A%94%20%EA%B1%B4%20%EC%8B%AB%EC%96%B4/Main.java

devxb/JJUNalgo