BOJ 2531 : 회전 초밥

BOJ 2531 : 회전 초밥

링크

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

풀이

index out of bound 에 대한 처리만 생각한다면 큰 문제 없이 풀 수 있는 문제

나열된 스시 번호 (sushi)

내가 먹은 스시 번호 (eat) : 스시 가지수 + 1 해서 모든 번호를 인덱스로 매핑할 수 있도록 만든다.

지금까지 먹은 스시 개수(cnt)

연속으로 먹는 스시 k만큼 eat에 넣어준다. 인덱스 1부터 n까지 k 크기 만큼 먹었다 뱉었다 해본다. (이 때 가장 끝에 인덱스를 end라고 한다.) i가 올라갈 때마다 eat[sushi[i-1]] 은 -1 해줘야 한다. end는 i + k 지만 인덱스 범위를 초과할 경우 모듈러 연산을 활용해서 맨 앞으로 옮긴다. eat[sushi[end]] ++

대신 최대의 가지수를 구하는 것이기 때문에

먹을 경우, eat[x] >= 1 인 경우에 이미 먹은 스시이기 때문에 cnt를 올리지 않고 eat[sushi[end]] ++

뱉는 경우, eat[sushi[i-1]]-- 로 먼저 뱉고, eat[x] >= 1 이면 cnt를 내리지 않는다.

코드

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] command = br.readLine().split(" "); int arrSize = Integer.parseInt(command[0]); int kind = Integer.parseInt(command[1]); int dishCnt = Integer.parseInt(command[2]); int coupon = Integer.parseInt(command[3]); int[] sushi = new int[arrSize]; int[] eat = new int[kind + 1]; for(int i = 0; i < arrSize; i++) { sushi[i] = Integer.valueOf(br.readLine()); } int cnt = 0; for(int i = 0; i < dishCnt; i++) { if(eat[sushi[i]] == 0) cnt++; eat[sushi[i]] ++; } int max = 0; for(int i = 1; i < arrSize; i++) { if(max <= cnt) { if(eat[coupon] == 0) { max = cnt + 1; } else { max = cnt; } } int e = (i + dishCnt - 1) % arrSize; if(eat[sushi[e]] == 0) { cnt ++; } eat[sushi[e]]++; eat[sushi[i - 1]]--; if(eat[sushi[i-1]] == 0) { cnt --; } } System.out.println(max); } }

parseInt 는 return primitive type,

valueOf 는 return Reference type,

그냥 한 번 써봤다.

from http://woogie.tistory.com/18 by ccl(A) rewrite - 2021-09-28 01:27:25