[백준] 20922. 겹치는 건 싫어 (자바 JAVA)

[ 문제 ]  [백준] 20922. 겹치는 건 싫어 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/20922

20922번: 겹치는 건 싫어

---

# 접근 방법 및 풀이 

 

• 투포인터 연습문제로 너무 좋은 문제다.
• 처음에 풀고 4퍼에서 틀려서 반례 찾았는데 다행히 질문검색에 어떤분이 반례 잔뜩 올려주셔서 풀었다.
• 투포인터는 start포인터와 end포인터를 어디서 시작하고, 각각의 포인터를 어떤 조건일때 움직일지 잘 생각해보아야한다.
• 코드 자체는 짧게 나오지만, 테케가 많지 않으면 진짜 쉽게 틀리는 유형같다ㅠㅠ
• 무튼! 문제 풀이는 다음과 같다. 
• 문제에서 수열을 연속적으로 보았을 때 같은 원소가 K개 이하로 포함하는 최장 연속 부분 수열의 길이를 구해야한다.
• 예제 1번처럼 K = 2일때 수열 3 2 5 5 6 4 4 5 7의 최장 연속 부분수열은 3 2 5 5 6 4 4 5 7로 길이는 7이된다.
• 여기서 같은 원소를 2개까지만 허용하므로, 또 5가 나오는 시점에선 5가 3개가 되기때문에 다음으로 갈 수 없다.
• 이렇게 연속적으로 수열을 탐색하면서 각 원소가 몇개 있는지 세어야한다. 그리고 원소는 1 <= a <= 100000범위이므로 int cnt[] = new int[100001];로 원소의 카운팅을 세는 cnt배열을 만들었다.
• start와 end는 둘다 시작지점 0번째부터 시작하고 포인터를 움직여줄거다.
• end를 연속적으로 최대한 옮길 수 있는 곳까지 움직여서 최장길이를 구할 것이고, 그 조건은 다음과 같다.
• end < arr.length && cnt[arr[end]] + 1 <= K
• end는 인덱스이므로 배열의 범위를 넘을 수 없고, end가 나타내는 인덱스의 원소값의 갯수가 K개 이하를 체크해주면된다. 
• 이렇게 end를 최대한 옮길 수 있을만큼 옮겼다면 start부터 end까지 거리를 구하고, 거리의 max값을 정답으로 갱신해주면된다.
• 그다음 start를 옮기는 조건인데, 나는 처음에 end까지 봤으니까 start를 end로 옮기고 쭉 탐색하면 된다고 생각했는데 틀렸다.
• 29 3
  1 2 3 4 5 6 7 8 9 1 1 11 1 14 15 16 23 43 24 53 24 25 99 29 36 45 64 69 45
  output : 28
• 그 이유는 이 반례를 찾아보면 알 수 있다!
• start는 하나씩 ++해서 옮기고 해당 기존에 start였던 원소의 카운팅을 하나 빼주면된다.
• 자세한건 코드참조!

 

# 주의할 점 

 

• start와 end 포인터 옮기는 조건 잘 생각해보기

 

JAVA 코드

package Silver;

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

public class bj20922_겹치는건싫어 {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int arr[] = new int[N];
		st = new StringTokenizer(in.readLine());
		for (int i = 0; i < arr.length; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		int ans = 0;
		int start = 0;
		int end = 0;
		int cnt[] = new int[100001];
		while(end < arr.length) {
			while(end < arr.length && cnt[arr[end]] + 1 <= K) {
				cnt[arr[end]]++;
				end++;
			}
			int len = end-start;
			ans = Math.max(ans, len);
			cnt[arr[start]]--;
			start++;
		}
		System.out.println(ans);
	}
}

 

 

 

REVIEW

한번에 맞추는 날이 왔으면 좋겠다.

정답률이 높아야 코테에서도 승산이 있다.