[BOJ]2531号:回転寿司(Java)
1828 ワード
質問する (Silver 1)
2531号:回転寿司
に答える
長さkのスライドウィンドウとして表現される.
このとき,i回目にk個ブラウズするたびではない(→タイムアウト!)
初期ウィンドウを設定し、startとendインデックスのみを処理します.
スライド時、
eat[start]値-1、値が0の場合はcntを1つ減らします.
→窓口内ではそれなりの種類のお寿司は食べず、
eat[end]値+1、値が1(=以下のコードは+1の前に0と判断)の場合、cntを1つ追加します.
→以前食べたことのないお寿司を食べていたので
コード#コード#
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);
}
}
送信
Reference
この問題について([BOJ]2531号:回転寿司(Java)), 我々は、より多くの情報をここで見つけました https://velog.io/@dot2__/BOJ-2531번-회전-초밥-Javaテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol