[BOJ] 15961.회전 초밥(슬라이딩 윈도우).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

 

좋지 않은 고정관념일 수 있지만...

회전(?!) 초밥인걸 보고

투포인트 아니면 슬라이딩 윈도우 문제겠구나.. 생각이 들었다.

나올 수 있는 접시의 최대는 3,000,000 그릇

연속해서 먹는 접시의 최대는 3,000 그릇일 때,

1 부터 3,000,000 번 그릇까지 3,000 번씩 연속으로 먹는 과정을 체크해본다면

3,000,000 X 3,000 = 9,000,000,000..

직관적인 접근으로 해결하려한다면 시간 초과의 늪에 빠질 것이다..

연속된 K개의 접시를 미는 느낌으로 새로 먹게되는 그릇은 추가해주고

버려지는 그릇은 제거해주는 식으로 해결했다.

예제를 보면

초기에 먼저 K(4)개를 먹어본 후,

다음 그릇(2)을 먹어보고, 꼬리 그릇(7)은 뱉어내는 느낌이다.

다음 동작은 아래와 같을 것이다.

연속된 K개의 그릇들은 유지된 채로

마치 유리창을 미는 느낌으로?!

그래서 알고리즘 이름도 슬라이딩 윈도우라고 지어진 것 같다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class BOJ15961 {       static int N, D, K, C, res, cnt, dishs[];     static int ate[];     public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());           N = Integer.parseInt(st.nextToken());    // 접시 수         D = Integer.parseInt(st.nextToken());    // 초밥의 가짓수         K = Integer.parseInt(st.nextToken());    // 연속해서 먹는 접시의 수          C = Integer.parseInt(st.nextToken());    // 쿠폰 번호                  dishs = new int[N];         ate = new int[D + 1];         for (int i = 0; i < N; i++)              dishs[i] = Integer.parseInt(br.readLine());           // 0번 idx 접시에 있는 초밥들부터 먼저 먹어보자.         for (int i = 0; i < K; i++) {             // 먹었던 초밥이 아니면             if(ate[dishs[i]] == 0) {                 res++;             }             ate[dishs[i]]++;         }         // 쿠폰에 적힌 초밥이 새로운 종류라면         cnt = res;         res = (ate[C] == 0) ? cnt + 1 : cnt;                  // 이 상태에서 추가로 하나씩 먹어보자         belt();                  System.out.println(res);     }       private static void belt() {           // 시작점         int start = K;         // 회전 초밥은 계속 돌아가고 있다.         while(true) {                          // 이전에 먹었던건 퉤퉤             ate[dishs[(start - K) % N]]--;             // 뱉었는데 먹은적이 없으면              if(ate[dishs[(start - K) % N]] == 0) cnt--;                          // 다음에 위치한 초밥이 먹었던게 아니면 냠냠             if(ate[dishs[start % N]] == 0) {                 cnt++;             }             ate[dishs[start % N]]++;                          // 얼마나 다양한 종류를 먹었나             // 쿠폰에 적힌 초밥이 안 먹어본거면 종류라면 + 1             res = Math.max(res, (ate[C] == 0) ? cnt + 1 : cnt);                          // 그 다음 초밥을 먹어볼까나             start++;             // 한바퀴 다 돈 상태면             if(start == (N-1) + K) break;         }     } }   Colored by Color Scripter

cs