[백준/JAVA] 20922번: 겹치는 건 싫어

🔺 문제

20922번: 겹치는 건 싫어

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        
        int[] A = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        int result = 0; // 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열 길이
 
        int left = 0;
        int right = 0;
        int[] counting = new int[100001];    // 카운팅 배열 !
        
        // 수열 탐색하면서 각 원소가 몇 개 있는지 카운트
        while(left <= right) {
            // 길이 늘릴 수 있는 경우
            if(right <= N - 1 && counting[A[right]] < K) {
                counting[A[right]]++;
                right++;
            }
            // 더 이상 늘릴 수 없는 경우, left 이동
            else if(counting[A[right]] == K) {
                counting[A[left]]--; // 기존에 left였던 원소의 카운팅 하나 빼기
                left++;              // left를 오른쪽으로 이동
            }
 
            // 더 이상 늘릴 수 없는 경우
            result = Math.max(result, right - left);
            
            if(right == N)  break;
        }
        
        System.out.println(result);
    }
}

✅ 해결 아이디어
✔ 투 포인터
- 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열 길이를 구하는 것이므로
  카운팅 배열을 생성해 해당 정수의 갯수 구함.
→ right가 K번 사용되지 않아 길이를 늘릴 수 있는 경우, 해당 원소의 사용횟수를 + 1하고, right를 늘려준다.
→ 이미 K번 사용된 경우, 기존에 left였던 원소의 카운팅 갯수를 하나 빼고, left을 오른쪽으로 이동

 

 

---

🔺 다른 풀이들

- while문이 조금 다름

백준 20922 겹치는 건 싫어 (Java,자바)

---

💬 느낀 점

투 포인터를 이렇게...?

복습을 해야겄다..

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 참고...😅

백준 20922[자바] java 겹치는 건 싫어

백준 20922번 - 겹치는 건 싫어