[BOJ] 2531번: 회전 초밥 (Java)
문제 (Silver 1)
풀이
길이가 k인 슬라이딩 윈도우로 구현하였다.
이 때, 매번 i번째에 대해서 k개를 탐색하는 것이 아니라 ( → 시간초과! )
초기의 window를 셋팅하고 start와 end 인덱스에 대해서만 처리하였다.
슬라이딩 할 때,
eat[start] 값을 -1하고, 그 값이 0이라면 cnt를 하나 감소시킨다.
→ 윈도우 안에 해당 종류의 초밥을 먹는 일이 없으므로
eat[end] 값을 +1하고, 그 값이 1이라면(= 아래 코드에서는 +1 하기전에 0인가를 판단) cnt를 하나 증가시킨다.
→ 이전에 없던 종류의 초밥을 먹는 것이므로
코드
package implement;
import java.io.*;
import java.util.*;
public class BOJ_2531_회전초밥 {
static int N, d, k, c;
static int[] sushi;
public static void main(String[] args) throws Exception{
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())-1;
sushi = new int[N];
int[] eat = new int[d]; // 해당 종류의 초밥을 몇개 먹었는지 저장하는 배열
for(int i =0 ; i < N ; i++){
sushi[i] = Integer.parseInt(br.readLine())-1;
}
int res = 0;
int cnt = 0;
for(int i =0 ; i < k ; i++){
if(eat[sushi[i]]++ == 0) cnt++;
}
for(int i =0 ; i < N ; i++){
if(res <= cnt){ // MAX 값 새로 갱신
if(eat[c] == 0) res = cnt+1;
else res = cnt;
}
int j = (i+k)%N; // end 값 (순환 → 인덱스 초과할 때의 처리)
if(eat[sushi[j]] ++ == 0) cnt++;
if(-- eat[sushi[i]] == 0) cnt--;
}
System.out.println(res);
}
}
제출
Author And Source
이 문제에 관하여([BOJ] 2531번: 회전 초밥 (Java)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dot2__/BOJ-2531번-회전-초밥-Java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)