[알고리즘] Java / 백준 / 회전 초밥 / 15961
[알고리즘] Java / 백준 / 회전 초밥 / 15961
문제
접근 방식
- 0번째 초밥부터 k번째 초밥까지의 초밥들을 카운팅 배열에 저장하고 중복을 제외한 값을 카운팅한다
- 투포인터로 다음 1번째부터 k+1번째 초밥으로 이동하며 이 때 0번째의 초밥을 카운팅 배열에서 제거하고 k+1번째 초밥을 카운팅 배열에 추가한다.
- 카운팅 배열에서 제거할 초밥이 쿠폰적용 초밥일 경우에는 제거하지 않는다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_15961 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int[] arr = new int[N+k];
for(int i=0;i<N;i++) {
arr[i] = Integer.parseInt(br.readLine());
}
for(int i=N;i<N+k;i++) {
arr[i] = arr[i-N];
}
int[] countArr = new int[d+1];
int cnt = 0;
for(int i=0;i<k;i++) {
if(countArr[arr[i]] == 0) {
cnt++;
}
countArr[arr[i]]++;
}
if(countArr[c] == 0) {
countArr[c]++;
cnt++;
}
int max = cnt;
int l = 0;
int r = k;
while(l != N-1) {
if(arr[l] != c ) {
countArr[arr[l]]--;
if(countArr[arr[l]] == 0) cnt--;
}
if(countArr[arr[r]] == 0) {
cnt++;
}
countArr[arr[r]]++;
max = Math.max(max, cnt);
l++;
r++;
}
System.out.println(max);
}
}
Author And Source
이 문제에 관하여([알고리즘] Java / 백준 / 회전 초밥 / 15961), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gandi0330/알고리즘-Java-백준-회전-초밥-15961저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)