백준 회전 초밥 2531 - JAVA

1. 문제

 

 

2. 접근

문제의 핵심은 먹을 수 있는 초밥 가짓수의 최댓값이다. 가짓수이다. 개수가 아니다.

 

먹을 수 있는 가짓수가 최댓값일 때는 언제일까?

먼저, 보너스 초밥을 포함하여 k개의 초밥을 먹을 때 k+1개를 먹을 수 있어서 최대이다. 하지만 무조건 보너스 초밥을 먹어야 되는 경우가 있을 수 있다. 예를 들어 보너스 초밥을 제외한 초밥의 가짓수가 k보다 적을 때는 보너스 초밥도 먹어야 한다. 이때 가짓수는 k개이다.

 

두 경우를 보면 여기서 중요한 것은 보너스 초밥을 포함해서 먹느냐 말냐이다. 그리고 가짓수이니깐 같은 종류의 초밥을 먹을 떄 중복 카운팅이 일어나며 안된다. 

 

정리하면 갱신 및 저장이 필요한 데이터는 보너스 초밥의 포함 여부, 먹은 초밥의 가짓수이다. 

보너스 초밥의 포함 여부는 `boolean`값으로, 먹은 초밥의 가짓수는 중복을 포함하면 안되니 편하게 `HashSet`을 이용한다.

 

3. 문제 풀이

초밥 하나하나 카운팅하면서 연속된 k개를 같이 움직여줘야 하니 투포인터를 사용하기로 했다. 문제를 풀다가 잘못 생각한 것이 초밥의 종류만 저장하면 되니 `HashSet`이 적합한줄 알았는데, 같은 초밥을 2개 이상먹었을 때를 고려할 수가 없어서 중간에 `HashMap`으로 바꿔서 카운트도 같이 저장했다.

 

해쉬맵을 이용한 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;

class Main {

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    public static void main(String[] args) throws IOException {

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

        int N = Integer.parseInt(st.nextToken());   // 접시의 수
        int d = Integer.parseInt(st.nextToken());   // 초밥의 가짓수
        int k = Integer.parseInt(st.nextToken());   // 연속해서 먹는 접시의 수
        int c = Integer.parseInt(st.nextToken());   // 쿠폰 번호

        int [] dishes = new int[N];
        for(int i=0; i<N; i++){
            dishes[i] = Integer.parseInt(br.readLine());
        }

        HashMap<Integer, Integer> eaten = new HashMap<>();
        boolean isBonus = false;

        int notEat = -1;
        int eat = -1;

        // 초기셋팅
        for(int i=0; i<k; i++){
            eat++;
            eaten.put(dishes[eat], eaten.getOrDefault(dishes[eat], 0) +1);

            // 보너스 초밥 체크
            if(dishes[eat] == c){
                isBonus = true;
            }
        }
        int max = isBonus? eaten.size(): eaten.size() +1;

        int count = 0;
        while(count < N + k +2){
            count++;

            // 초밥 먹기
            eat = (eat+1)%N;
            eaten.put(dishes[eat], eaten.getOrDefault(dishes[eat], 0) +1);
            if(dishes[eat] == c){
                isBonus = true;
            }

            // 먹은 초밥 빼기
            notEat = (notEat+1)%N;
            int removeDish = dishes[notEat];
            if(eaten.get(removeDish) == 1){
                eaten.remove(removeDish);
                // 보너스 초밥 체크
                if(removeDish == c){
                    isBonus = false;
                }
            }
            else{
                eaten.put(removeDish, eaten.get(removeDish)-1);
            }

            // 최대값 체크
            max = Math.max(isBonus? eaten.size(): eaten.size() +1, max);
            if(max == k+1){
                break;
            }
        }

        System.out.println(max);
    }
 }

 

3-1. 해쉬맵 안써도 되겠는데?

문제에서 d값을 안써도 정답이길래 뭔가 다른 방법이 있나 고민하다가 d의 값이 최대 3000이어서 배열을 이용해서 풀어도 되겠구나 했다. 아래는 HashMap을 사용하지 않고 `int[]`을 사용해서 푼 방법이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;

class Main {

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    public static void main(String[] args) throws IOException {

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

        int N = Integer.parseInt(st.nextToken());   // 접시의 수
        int d = Integer.parseInt(st.nextToken());   // 초밥의 가짓수
        int k = Integer.parseInt(st.nextToken());   // 연속해서 먹는 접시의 수
        int c = Integer.parseInt(st.nextToken());   // 쿠폰 번호

        int [] dishes = new int[N];
        for(int i=0; i<N; i++){
            dishes[i] = Integer.parseInt(br.readLine());
        }

        int [] eaten = new int[3001];
        boolean isBonus = false;

        int notEat = -1;
        int eat = -1;

        int kind = 0;
        // 초기셋팅
        for(int i=0; i<k; i++){
            eat++;
            eaten[dishes[eat]]++;
            if(eaten[dishes[eat]] == 1){
                kind++;
            }

            // 보너스 초밥 체크
            if(dishes[eat] == c){
                isBonus = true;
            }
        }
        int max = isBonus? kind: kind +1;

        // 최대 가짓수 구하기
        int count = 0;
        while(count < N ){
            if(max == k+1){
                break;
            }
            count++;

            // 초밥 먹기
            eat = (eat+1)%N;
            eaten[dishes[eat]]++;
            if(eaten[dishes[eat]] == 1){
                kind++;
            }
            if(dishes[eat] == c){
                isBonus = true;
            }

            // 먹은 초밥 빼기
            notEat = (notEat+1)%N;
            eaten[dishes[notEat]]--;
            if(eaten[dishes[notEat]] == 0){
                kind--;
                // 보너스 초밥 체크
                if(dishes[notEat] == c){
                    isBonus = false;
                }
            }

            // 최대값 체크
            max = Math.max( isBonus? kind: kind +1, max);

        }

        System.out.println(max);
    }
 }

 

 

역시 배열로 푼 것이 더 빠르다. 물론 지금 문제는 값의 범위가 크지 않아서 배열이 더 적합한데 조금만 커져도 메모리쪽에서 상당한 차이가 날 것 같다. 그때는 HashMap이 좋을려나?