[백준/JAVA] 2531번: 회전 초밥

📖 문제

https://www.acmicpc.net/problem/2531

 

 

 

💡  풀이 방식

• 투 포인터

1. 입력된 정보를 저장한다.

  - int[N] sushi : 초밥 종류 저장 배열

  - int[d+1] chk  :  초밥 각 종류가 몇 개 존재하는지 나타내는 배열

 

2. 투 포인터를 이용해 먹을 수 있는 최대 가짓수를 구한다.

  1) 회전하지 않았을 때 초밥을 먹는다.

  2)  N-1번 회전하며 탐색을 진행한다.

      → [규칙] 처음 먹은 초밥은 제거하고, 마지막+1 번째 초밥은 추가한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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[] sushi = new int[N];
        for(int i = 0 ; i < N ; i++) {
            sushi[i] = Integer.parseInt(br.readLine());
        }
        
        int[] chk = new int[d+1];   // 먹은 초밥 종류 관련 배열
        chk[c] = 3001;  // 무료 초밥 종류
        
        int cnt = 1;    // 무료 초밥이 1개이므로
        
        // 1. 회전하지 않았을 때 초밥 종류 구하기
        for(int i = 0 ; i < k ; i++) {
            if(chk[sushi[i]] == 0)
                cnt++;
            
            chk[sushi[i]]++;
        }
        
        int max = cnt;
        
        // ⭐ 2. N-1번 회전을 투 포인터로 실행
        for(int i = 0 ; i < N-1 ; i++) {
            int sIdx = sushi[i];    // 처음 먹은 초밥 종류
            int eIdx = sushi[((i+k) < N) ? (i+k) : (i+k) % N];    // 마지막 + 1번째 먹을 초밥 종류
            
            // 처음 먹은 초밥 종류가 더 이상 없을 때
            if(--chk[sIdx] == 0)
                cnt--;
                
            // 마지막 +1번째 먹을 초밥이 처음 먹는 것일 때
            if(++chk[eIdx] == 1)
                cnt++;
           
            max = Math.max(max, cnt);
        }
        
        System.out.println(max);
    }
}

 

 

➕ 다른 풀이 방식

조오금 다르다.

[JAVA]백준 2531번: 회전 초밥

---

💦 어려웠던 점

- 슬라이딩 윈도우 쓸 생각을 못 했다.

 

 

🧐 새로 알게 된 내용

- 처음 원소는 빼고, 마지막 +1번째 원소는 추가하는 아이디어

 

 

1회독	2회독	3회독	4회독	5회독
V

 

---

(참고)

[백준] 알고리즘 분류(브루트포스 알고리즘,JAVA)2531번, 회전 초밥