baekjoon. 회전 초밥 (2531) | hashmap사용 [java]

여기 문제집에서 회전초밥 문제를 풀었다.

ㄴ 문제집 : https://www.acmicpc.net/workbook/view/8708

ㄴ 문제 : https://www.acmicpc.net/problem/2531

 

 

문제가 조금 길게 설명이 되어있는데 요약하면 

- 연속으로 먹을 수 있는 초밥에 최대한 숫자가 고유하게 들어가면 된다. 

- 그리고 나서 이 초밥에 쿠폰초밥이 들어가있으면 그대로 두고, 아니라면 쿠폰초밥을 +1하면 된다. 

 

초밥 그릇 갯수 (n)에 매번 for문을 돌면서 연속 숫자 (k)를 체크하면 되는데 그럴 경우 

n최대 30,000에 k 3,000까지 해서 시간이 오래 걸릴 것 같아서 효율적인 방법을 찾아야 되었었다. 

 

그래서 초밥 그릇 갯수 (n)에서 각 초밥마다 HashMap으로 몇번의 초밥이 몇 개를 가지고 있는지 저장했다가 

다음 초밥으로 옮기면서 맨 첫 초밥을 지우고 새로운 초밥을 넣으면서 계산했다. 

 

정리하면 

1. 회전 초밥이기 때문에 뒤에서부터 k개의 초밥을 (초밥의 종류, 갯수) 형태로 map에 넣는다. 

2. 처음부터 k개 전까지는 뒤에서 하나를 제거하고 처음꺼를 넣는다. 

3. 그 다음 부터는 지금 돌고 있는 거에서 k개 전꺼를 제거하고 지금꺼를 넣는다. 

4. 회전 초밥 갯수는 이 map의 size에다 쿠폰의 여부에 따라 +1을 더한다. 

 

다른 해설 풀이를 살펴보면 조금 더 단순하게 문제를 푸는 방법들이 있었다. 

- 위의 2번,3번을 나눠서 가져가지 않고 처음부터 뒤에 값을 넣어놓고 2번 3번은 for문을 태웠다. https://code-lab1.tistory.com/m/182

- 슬라이딩 윈도우를 통해서 로직을 단순하게 가져간다.  https://hunucho.tistory.com/m/312

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.HashMap;


public class Main {
    static int[] dishArr;
    static HashMap<Integer,Integer> temp;
    static int c;
    
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c
        int N = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        
        dishArr = new int[N];
        // 접시 세팅 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            dishArr[i] = Integer.parseInt(st.nextToken());
        }
        
        temp = new HashMap();
        
        // 초밥이 원형이기 때문에 시작전 마지막 넣어두기 
        for (int i = 0; i < k; i++) {
            add(dishArr[N-1-i]);
        }
        
        int size = Integer.MIN_VALUE;
        size = max(size);
        
        for (int i = 0; i < N; i++) {
            
            // 제거할 초밥 정하기 : 원형이기 때문에 분기태움 
            int deleted;
            if (i < k) {
                deleted = dishArr[N - k + i];
            }
            else {
                deleted = dishArr[i - k ]; 
            }
            
            // 앞의 초밥 제거 
            remove(deleted);
            
            int dish = dishArr[i];
            add(dish);
            
            size = max(size);
        }
        
        System.out.printf("%d \n", size);
    }
    
    static void remove(int deleted) {
        if (temp.get(deleted) == 1) {
            temp.remove(deleted);
        }
        else {
            temp.put(deleted, temp.get(deleted) - 1);
        }
    }
    
    static void add(int dish) {
        if (! temp.containsKey(dish)) {
            temp.put(dish, 1);
        }
        else {
            temp.put(dish, temp.get(dish) + 1);
        }
    }
    
    static int max(int size) {
        int free = 0; 
        if (! temp.containsKey(c)) {
            free = 1;
        }
        
        int max = Math.max(temp.size() + free, size);
        return max;
    }
}