제출 코드
✏️ S2531. 회전 초밥 과 동일한 문제이나, 테케의 범위가 더 넓어져 기존 코드로는 시간초과가 났다.
기존 코드의 로직 자체는 더이상 최적화 할 수 없다고 판단해서, 구현 부분에서 줄일 수 있는 것을 찾았다. 아래의 두가지를 수정해 보았다.
-
**queue 제거**자료구조에서 메서드 호출하는 부분이 잦아지면 시간소요가 크다고 했어서, Queue를 사용한 부분을 지워줬다. 다시보니 크게 필요하지 않은 부분이었더라.
-
**result 값 도출 방식**기존 코드에서는, 매번 result를 구할때마다 최대값만 저장하도록 매 회차마다 비교를 했다.
이전에 문자열 관련 문제 풀 때, 값을 받아오는 즉시 비교해서 값을 넣는것보다 모든 값을 불러온 뒤 Arrays.sort를 통해 정렬하는 것이 빨랐던 기억이 있어, 모든 값 저장후 정렬로 최대값 찾는 방식으로 바꿔보았다.
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
package gold;
import java.util.Arrays;
import java.util.Scanner;
public class G15961_rotateSushi {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int D = sc.nextInt();
int K = sc.nextInt();
int C = sc.nextInt();
int[] rotate = new int[N];
int[] overap = new int[D+1];
int overapCnt = 0;
for(int i=0; i<N; i++) {
rotate[i] = sc.nextInt();
if(i<K) {
if(++overap[rotate[i]]>1) overapCnt++;
}
}
int[] result = new int[N];
result[0] = K-overapCnt + (overap[C]>0 ? 0 : 1);
for(int i=K; i<N+K; i++) {
int out = rotate[(i-K+N)%N];
if(--overap[out]>0) overapCnt--;
int in = rotate[i%N];
if(++overap[in]>1) overapCnt++;
result[i%N] = K-overapCnt + (overap[C]>0 ? 0 : 1);
}
Arrays.sort(result);
System.out.println(result[N-1]);
}
}