오늘의 1솔 ♬

오늘의 문제는 백준의 Silver 1 겹치는 건 싫어 !
바로 풀고 싶다면 요기로 → 문제 바로가기

문제 설명

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

풀이

접근 방법

1. from(최장 부분 수열의 첫 인덱스) , to(최장 부분 수열의 마지막 인덱스) 두 개의 포인터를 사용한다
2. to 를 1씩 증가시키며 아래 과정을 반복한다
   2-1. 수열의 to 번째 인덱스에 있는 원소의 개수를 1 증가시킨다
   2-2. 증가시킨 값이 K를 초과한다면 from 번째 인덱스의 값이 to 번째 인덱스에 있는 값과 동일해질 때까지 from 을 증가시킨다
   2-3. 위의 과정이 끝나면 부분 수열은 모든 원소가 K개 이하인 상태이므로, 해당 부분 수열 길이로 최대값을 갱신한다

투 포인터

말 그대로 포인터를 두 개 쓰는 방법이다
해당 문제에서는 최장 부분 수열의 첫 인덱스, 마지막 인덱스를 가리키는 데에 사용했다

HashMap

{key} : {value} 로 데이터를 저장할 수 있는 자료구조다
여기서 {key} 는 수열을 이루는 원소, {value} 는 해당 원소가 부분 수열에 포함된 개수로 사용했다

코드

package a2408;

import java.io.*;
import java.util.*;

public class d10_bj_s1_20922_겹치는_건_싫어 {
    public static void main(String[] args) throws Exception{
        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[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int n=0; n<N; n++){
            int num = Integer.parseInt(st.nextToken());
            arr[n] = num;
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        int answer = 0;
        int from = 0;
        int to = 0;
        while(to < N){
            int num = arr[to];
            map.put(num, map.getOrDefault(num, 0) + 1);
            while (K < map.get(num)) {
                map.put(arr[from], map.get(arr[from]) - 1);
                from++;
            }
            to++;
            answer = Math.max(answer, to-from);
        }
        System.out.println(answer);
    }
}

마무리

문제에 대놓고 홍대병이라고 써있어서 띠용했다
나도 나만 아는 가수 유명해지면 괜히 섭섭하고 서운하고 으앙하고 부들부들하고 그런다