백준 회전 초밥 2531 - JAVA

1. 1. 문제

 

 

2. 2. 접근

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

 

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

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

 

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

 

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

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

 

3. 3. 문제 풀이

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

 

해쉬맵을 이용한 풀이

      

      

      

    
    

      <java />
    
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);
    }
 }

 

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

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

      

      

      

    
    

      <java />
    
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이 좋을려나?