[백준] 2531번 회전 초밥 JAVA (자바) 풀이
문제 2531번 (투포인터, 슬라이딩 윈도우)
: 초밥 벨트 임의의 위치부터 k개의 접시를 연속해서 식사
: 쿠폰에 쓰여진 초밥은 무료 시식 가능
: 손님이 먹을 수 있는 최대 초밥 가짓수를 구해라
[입력]
: 첫 줄에 접시 수 N / 초밥 가짓 수 d / 연속해서 먹는 접시의 수 k / 쿠폰 번호 c
둘째 줄에는 수열 N개의 줄에는 각 줄 마다 초밥 종류가 하나씩 주어진다
[출력]
: 먹을 수 있는 초밥의 최대 가짓 수 출력
[설명]
(예시)
k=4, 30번 초밥을 쿠폰 획득일 경우
- 가능한 모든 경우의 수
(7,9,7,30),(9,7,30,2),(7,30,2,7),(30,2,7,9),(2,7,9,25),(7,9,25,7),(9,25,7,9),(25,7,9,7)
- 최대한 많은 종류를 먹어야해서 초밥 종류가 중복이라면 제외
(7,9,7,30),(9,7,30,2),(7,30,2,7),(30,2,7,9),(2,7,9,25),(7,9,25,7),(9,25,7,9),(25,7,9,7)
- 쿠폰(=30)은 어차피 무료시식이 가능하니까 제외
(9,7,30,2),(30,2,7,9),(2,7,9,25)
< 투포인터 >
- 2개의 포인터 필요 (start, end)
- 길이가 가변적인 부분 배열을 다룰 때 사용
< 슬라이딩 윈도우 >
- 1개의 포인터 필요 (시작 지점)
- 부분 배열 길이 고정
< 과정 >
→ 처음 초밥종류( = type ) 개수 검사 ( i~k번까지) type 개수
→ private static int slide(){} 안에서 첫번째 for문을 통해 check
→ 지금부터는 시작지점과 끝지점을 하나씩 이동하면서 계산
→ private static int slide(){} 안에서 두번째 for문을 통해 처음부터 비교
→ 초밥이 원형으로 회전하기 때문에 위와 같은 모양으로 이어져 있다
[코드]
import java.util.*;
import java.io.*;
public class Main {
static int N,d,k,c,arr[],eat[];
public static void main(String[] args) throws IOException{
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());
arr = new int[N];
eat = new int[d+1];
for(int i=0; i<N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
System.out.println(slide());
}
private static int slide() {
eat[c] = 3001;
int type = 1;
for(int i=0; i<k; i++) {
if(eat[arr[i]] <= 0) type ++;
eat[arr[i]] ++;
}
int max = type;
for(int i=0; i<N; i++) {
int end = (i+k)%N;
if(--eat[arr[i]] == 0) type-- ;
if(eat[arr[end]]++ == 0) type ++;
max = Math.max(max, type);
}
return max;
}
}
[해설]
: static int N, d, k, c, arr[], eat[]; 첫째줄 입력값, 초밥배열, 먹은 초밥
: 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()); 무료 시식 초밥 종류
: eat = new int[d + 1]; 초밥 종류 당 몇 개씩 먹었는지 저장
arr = new int[N]; 총 접시 배열
: for (int i = 0; i < N; i++) 접시 개수 만큼 입력받기
arr[i] = Integer.parseInt(br.readLine());
예를 들어 N = 4 / 초밥: 7, 9, 7, 30, 2, 7, 9, 25 / 쿠폰 초밥 c = 30 / k = 4 라면
arr[0] = 7
arr[1] = 9
arr[2] = 7
arr[3] = 30
arr[4] = 2
arr[5] = 7
arr[6] = 9
arr[7] = 25
: System.out.println(slide()); 슬라이딩 윈도우 출력
: private static int slide() { 슬라이딩 윈도우 메서드
eat[c] = 3001; 최대가 3000개라서 쿠폰 초밥 3001로 가정
int type = 1; 쿠폰 초밥은 이미 먹었다고 가정 → 1
for (int i = 0; i < k; i++) { 처음 먹은 k만큼의 초밥 저장
if (eat[arr[i]] == 0) type ++; eat 배열에 아직 값이 없다는 것은 먹지 않았다는 뜻
초밥먹지 않았다면 (eat = 0) 해당 종류 type에 추가
eat[arr[i]]++; 해당 초밥 종류 먹었다고 count
}
예를 들어 N = 4 / 초밥: 7, 9, 7, 30, 2, 7, 9, 25 / 쿠폰 초밥 c = 30 / k = 4 라면
1. eat [ arr [0] ] = eat [7] = 0 ▶ type = 1+1 (초깃값 1이니까) = 2
▶ eat [7] = 1 로 변경
2. eat [ arr [1] ] = eat [9] = 0 ▶ type = 2+1 = 3
▶ eat [9] = 1 로 변경
3. eat [ arr [2] ] = eat [7] = 1 ▶ type = 3 (유지)
▶ eat [7] = 2 로 변경
4. eat [ arr [3] ] = eat [30] = 3001 ▶ type = 3 (type 아예 1로 먼저 잡고 시작해서 유지)
▶ eat [30] = 3001+1 로 변경
→ 7초밥 2개 / 9초밥 1개 / 30초밥 3002개(임의로 설정)
→ type = 3 => 초밥 종류 3개
max = type; max 값을 type으로 저장
for (int i = 0; i < N; i++) { 중복된 값을 구분하기 위해서 다시 처음부터 계산
int j = (i+k)%N; i를 시작지점, j를 끝지점 이라고 지정
j = 4, 5, 6, 7, 0, 1, 2, 3
if (--eat[arr[i]] == 0) type--; 증감 연산자가 앞에 있으니 eat배열을 뺐을 때 0이라면 type --
if (eat[arr[j]] ++ == 0) type++; 증감 연산자가 뒤에 있으면 eat배열 값이 0 이라면 더하고 type ++
끝지점만 옮겨가며 안 먹어본 초밥 종류를 추가하는 과정
(앞부분 k만큼의 초밥 종류는 파악O, 끝지점부터 보는게 맞다)
max = Math.max(max, type); if 문을 거쳐서 계산한 type과 max값을 비교해 갱신
}
return max; max 값 출력
예를 들어 N = 4 / 초밥: 7, 9, 7, 30, 2, 7, 9, 25 / 쿠폰 초밥 c = 30 / k = 4 라면
1) for 문 i = 0 → j = 4
- 첫번째 if문 eat [ arr [0] ] = eat [7] = 2 ▶ eat[7] - 1 해도 0이 아니니까 type 은 유지
▶ eat[7] = 1 되고, type = 3
- 두번째 if문 eat [ arr [4] ] = eat [2] = 0 ▶ eat[2] 값이 0이니까 eat[2] + 1, type도 + 1하기
▶ eat[2] = 1 되고, type = 4
- 왜 양끝만 검사하는 이유 : 중간부분은 이미 slide의 맨 처음 for문에서 계산완료
- 결과 : max = 3 / type 4 → type이 커서 max값을 4로 갱신
2) for 문 i = 1 → j = 5
- 첫번째 if문 eat [ arr [1] ] = eat [9] = 1 ▶ eat[9] - 1 하면 0이니까 type - 1
▶ eat[9] = 0 되고, type = 3
- 두번째 if문 eat [ arr [5] ] = eat [7] = 1 ▶ eat[7] 값이 0이 아니니까 eat[7] + 1, type 유지
▶ eat[7] = 2 되고, type = 3
- 결과 : max = 4 / type 3 → max가 커서 max값 유지
3) for 문 i = 2 → j = 6
- 첫번째 if문 eat [ arr [2] ] = eat [7] = 2 ▶ eat[7] - 1 하면 0 아니니까 type 유지
▶ eat[7] = 1 되고, type = 3
- 두번째 if문 eat [ arr [6] ] = eat [9] = 0 ▶ eat[9] 값이 0이니까 eat[9] + 1, type + 1
▶ eat[9] = 1 되고, type = 4
- 결과 : max = 4 / type 4 → max값 유지
4) for 문 i = 3 → j = 7
- 첫번째 if문 eat [ arr [3] ] = eat [30] = 3002 ▶ eat[30] - 1 하면 0 아니니까 type 유지
▶ eat[30] = 3001 되고, type = 4
- 두번째 if문 eat [ arr [7] ] = eat [25] = 0 ▶ eat[25] 값이 0이니까 eat[25] + 1, type + 1
▶ eat[25] = 1 되고, type = 5
- 결과 : max = 4 / type 5 → type가 커서 max값 5로 갱신
5) for 문 i = 4 → j = 0
▶ eat[2] = 1 - 1 되고, type = 5 - 1 = 4
▶ eat[7] = 1 + 1 = 2, type = 4 유지
- 결과 : max = 5 / type 4 → max값 유지
6) for 문 i = 5 → j = 1
▶ eat[7] = 2 - 1 되고, type = 4 유지
▶ eat[9] = 1 + 1, type = 4 유지
- 결과 : max = 5 / type 4 → max값 유지
7) for 문 i = 6 → j = 2
▶ eat[9] = 2 - 1 되고, type = 4 유지
▶ eat[7] = 1 + 1, type = 4 유지
- 결과 : max = 5 / type 4 → max값 유지
8) for 문 i = 7 → j = 3
▶ eat[25] = 1 - 1 되고, type = 4 - 1
▶ eat[30] = 3001 + 1, type = 3 유지
- 결과 : max = 5 / type 3 → max값 유지
(얘네는 처음 먹은 초밥, 위에서 미리 검사했다
이대로 해도 괜찮지만 for문 범위를 N-1 까지하면 중복되는 구간 검사 안한다)
이제 풀어보러 갈께요 :)
https://www.acmicpc.net/problem/2531
2531번: 회전 초밥
첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤
www.acmicpc.net
* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *