[BOJ 투 포인터] 회전초밥 2531.JAVA

문제 링크 : https://www.acmicpc.net/problem/2531
등급 : Silver I

2531번: 회전 초밥

프로세스

1. 내가 먹을 수 있는 초밥의 개수만큼 먹는다.
2. 처음 먹은 초밥(원포인트), 마지막 먹은 초밥(투 포인트)을 기준으로 잡는다.
3. 처음 먹은 초밥을 버리고, 먹을 초밥을 삽입한다.
4. 3번을 반복하면서 시작 지점 직전까지 초밥을 먹는다.
   1. 4개의 초밥을 먹을 수 있을 때 1, 2, 3, 4, 5, 6, 7, 8의 초밥이 있다고 가정한다.
   2. 초밥을 먹을 수 있는 조합은 1234, 2345,... 8123까지 먹을 수 있다.
5. 최대 먹을 수 있는 접시를 한번 먹을 때마다 쿠폰으로 먹을 수 있는 접시가 있는지 파악한다.
6. 3~5번을 반복하여 가장 많이 먹을 수 있는 초밥의 가지 수를 찾는다.

문제 핵심

이 문제의 핵심은 내가 먹을 수 있는 초밥의 가짓수를 찾는 것이어서 내가 먹은 초밥의 가지수를 중복 제거하는 게 필요하다.

일반적인 stream으로 distinct하거나 for문을 돌려 중복 제거하면 시간 초과가 발생한다.

그래서 HashMap을 이용하여 초밥을 먹을때 이미 먹은 초밥인지 체크하여 중복을 제거한다.

 

아래와 같이 소스를 공유합니다.

public class Main {

    public static int[] sushis;
    public static int nu, ma, di, cp;
    public static int max = Integer.MIN_VALUE;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] commend = br.readLine().split(" ");

        nu = Integer.parseInt(commend[0]);
        ma = Integer.parseInt(commend[1]);
        di = Integer.parseInt(commend[2]);
        cp = Integer.parseInt(commend[3]);

        sushis = new int[nu];
        Map<Integer, Integer> eat = new HashMap<>();

        eat.put(cp, 1);

        for(int i = 0; i < nu; i++) {
            int sushi = Integer.parseInt(br.readLine());
            sushis[i] = sushi;
            if(i < di) {
                if(eat.containsKey(sushi)) {
                    eat.put(sushi, eat.get(sushi)+1);
                }else {
                    eat.put(sushi, 1);
                }
            }
        }

        for(int i = di; i < sushis.length + di; i++) {
            counting(eat.size());

            int e = sushis[Math.abs(di-i)];

            if(eat.containsKey(e) && eat.get(e) > 1) {
                eat.put(e, eat.get(e)-1);
            }else {
                eat.remove(e);
            }

            int sushi = sushis[(i >= sushis.length) ? Math.abs(sushis.length - i) : i];

            if(!eat.containsKey(sushi)) {
                eat.put(sushi, 1);
            }else {
                eat.put(sushi, eat.get(sushi)+1);
            }
        }

        System.out.println(max);
    }

    public static void counting(int num) {
        max = Math.max(num, max);
    }
}