[백준/S1/투포인터/자바] 20922 겹치는건 싫어

💡 문제

 

홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다.

도현이를 위해 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.

 100 000이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다.

이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자

 

⌨ 입력

 

첫째줄 : N ( 1 <= N <= 20만) / K ( 1 <= K <= 100 )

둘째줄 : 수열의 원소 N개

 

💻 출력 / 제한

 

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

 

---

 

풀이 방법

 

투포인터 문제 입니다. 2가지 방법으로 구현 할 수 있습니다.

1. Queue, Map 을 사용 하여 구현
2. 투포인터 사용 하기

 

1.  큐, 맵으로 구현 하기

 

Queue<Integer> :

q.size() 를 통해 최장 연속 부분 수열 길이 갱신

 

Map<Integer, Integer> :

숫자의 개수를 알기 위한 Map

 

예시)

 

숫자의 개수 <= K 라면 큐에 넣습니다.

 

 

4,3,3 이 들어갈 때

3의 개수가 2개가 되므로 큐에서 3이 나올때 까지 poll() 하며 Map을 업데이트 합니다.

 

 

q.size() 가 가장 컸던 것은 3이므로 답은 3이 됩니다.

 

2. 투포인터 풀이

 

Queue -> 투 포인터로 대체

Map -> count[ ] 배열로 대체

 

 

end - start 값을 통해 수열의 최대 길이를 갱신 합니다.

Count[Arr[end]] 값을 통해 숫자의 개수를 파악 합니다.

 

 

조건을 만족 할경우 end 포인터를 움직이고, 아닐 경우 start 포인터를 움직입니다.

두번째 3을 체크할때 이미 Count[Arr[end]] = 1 이므로 start 포인터를 움직입니다.

 

 

조건을 만족 할때 까지 Count[Arr[start]]-- start-- 를 합니다.

즉 3을 찾을때 까지 반복 합니다.

 

---

 

전체 코드

import java.io.*;
import java.util.*;
import java.util.stream.Stream;

/*
* 문제 풀이 :
* 1. map, Queue 사용 한다.
* ( map<Integer,Integer> Key : 숫자 Value : 숫자의 개수 )
* ( Queue<Integer> 현재 큐에 들어 간 크기를 통해 max 값을 갱신 한다. )
*
* 동작 예시)
* 7 2
* 3 2 5 5 5 4 4
*
* 4번째 index 까지 큐,맵에 넣으 면서 최대 값을 갱신 한다 최대값 4
* 5번째 5가 들어 올때 3(5의 개수) > 2 이므로
*
* 큐에서 5 숫자가 나올때 까지 q.poll / map.put (뺀 숫자 개수 갱신) 한다.
* 큐에 남은 배열은 5 5 이다. 이후 끝까지 위 행동을 반복 한다.
* */

public class DuplicateHate20922 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Map<Integer,Integer> map = new HashMap<>();
        Queue<Integer> q = new LinkedList<>();

        //N, K, max 값
        int[] NAndK = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int N = NAndK[0]; int K = NAndK[1]; int max = 0;

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for(int i = 0; i < N; i++){
            int present = Integer.parseInt(st.nextToken());
            int keyCount = map.getOrDefault(present, 0) + 1;
            map.put(present, keyCount); q.add(present);

            if(keyCount <= K) max = Math.max(max, q.size());
            else{
                while(true){
                    int num = q.poll();
                    int mapValue = map.get(num) - 1;
                    map.put(num, mapValue);

                    if(num == present) break;
                }
            }
        }
        System.out.println(max);

        // 투포인터 풀이
       /*
        int[] count = new int[100001];
        int[] list = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int maxLength = 0; int start = 0; int end = 0;

        while(end < N){
            if(count[list[end]] < K){
                count[list[end]]++; end++;
                maxLength = Math.max(maxLength, end - start);
            }
            else{
                count[list[start]]--; start++;
            }
        }
        System.out.println(maxLength);
    }*/
    }
}