public class Main{
public static void main(String[] args){
}
}
문제 설명
접근 방법
이 문제에 핵심
1. 초밥 음식점 벨트는 시작과 끝이 연결되어 있습니다.
2. 쿠폰에 적힌 초밥은 무료로 먹을 수 있습니다.
3. k개를 연속으로 먹을 때 먹을 수 있는 최대의 가짓수를 결과로 출력합니다.
알고리즘 진행 순서.
1. 입력된 정보를 저장합니다.
2. 두 포인터를 이용하여 먹을 수 있는 최대 가짓수를 구합니다.
3. 최대 가짓수를 결과로 출력합니다.
최대 가짓수 탐색!
초밥 벨트가 회전하는 모양을 살펴보면
규칙을 발견하실 수 있습니다.
처음 먹었던 초밥 : 제거
(마지막 + 1)번째 초밥 : 추가
초밥의 각 종류가 몇 개가 존재하는지 eating[]에 저장한 뒤
시작과 끝에 대한 투 포인터를 적용하여 탐색을 진행합니다.
회전을 진행!
eating[처음 먹었던 초밥] - 1
eating[마지막 +1번째 초밥] + 1
진행하여 회전을 (N - 1)번을 진행할 때 최대 가짓수를 구합니다.
예제입력 1.
1. 입력된 정보를 저장합니다.
N : 8
d : 30
k : 4
c : 30
2. 두 포인터를 이용하여 먹을 수 있는 최대 가짓수를 구합니다.
회전하지 않았을 때 초밥 먹기!
먹은 가짓수 : 7, 9, 7, 30 : 3개
(N-1)번 회전 탐색 진행!
1번째
7 : 제거, 2 : 추가
먹은 가짓수 : 9, 7, 30, 2: 4개
2번째
9 : 제거, 7 : 추가
먹은 가짓수 : 7, 30, 2, 9:4개
....
4번째
30 : 제거, 2 : 추가
먹은 가짓수 : 2, 7, 9, 25:4개 + 1개(30) : 5개
....
7번째
9 : 제거, 7 : 추가
먹은 가짓수 : 25, 7, 9, 7: 3개 + 1개(30) : 4개
3. 최대 가짓수를 결과로 출력합니다.
4번째 회전일 때 : 2, 7, 9, 25, 30 : 5개
5을 결과로 출력합니다.
BufferedReader를 사용하여 입력되는 정보를 저장합니다.
StringTokenizer를 이용해서N, d, k, c를 띄어쓰기 기준 나누었습니다.
회전하지 않았을 때 초밥 종류가 기본 최대값으로 저장합니다.
N-1번 초밥 벨트를 회전할 때마다 투 포인터를 이용하여 탐색합니다.
탐색이 끝난 뒤 최대 가짓수를 결과로BufferedWriter에 저장하였습니다.
BufferedWriter에 저장된 결과값을 출력하였습니다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException{
//입력값 처리하는 BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//결과값 출력하는 BufferedWriter
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
//N, d, k, c의 입력값 저장
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[] eating = new int[d+1]; //먹은 초밥 종류 관련 배열
eating[c] = 3001; //무료 초밥 종류
int[] sushi = new int[N];
int count = 1; //무료 초밥이 1개 있으므로 default Value = 1
//회전 벨트 정보 저장
for(int i=0;i<N;i++)
sushi[i] = Integer.parseInt(br.readLine());
//회전하지 않았을 때 초밥 종류 구하기
for(int i=0;i<k;i++){
int sushiId = sushi[i];
if(eating[sushiId]==0)
count++;
eating[sushiId]++;
}
int max = count;
//(N-1)번 회전을 투 포인터를 이용하여 탐색
for(int i=0;i<N-1;i++){
int s_id = sushi[i]; //처음 먹은 초밥 종류
int e_id = sushi[i+k<N ? i+k : (i+k) % N]; //마지막 + 1번째 먹을 초밥 종류
if(--eating[s_id] == 0) //처음 먹은 초밥 종류 더 이상 없을 때
count--;
if(++eating[e_id] == 1) //마지막 + 1번째 먹을 초밥이 처음 먹는 것일 때
count++;
max = Math.max(max, count); //최대값 비교
}
bw.write(String.valueOf(max)); //최대 가지수 BufferedWriter 저장
bw.flush(); //결과 출력
bw.close();
br.close();
}
}
댓글