(JAVA) 백준 2531번 : 회전 초밥 -- [투포인터]

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

2531번: 회전 초밥

 

안녕하세요.

 

회전초밥ㅁ?ㅁ

투포인터를 사용하는 문제입니다.

하지만, start ~ end 길이가 고정된 길이기 때문에, sliding window 알고리즘이라고도 할 수 있겠죠.

 

위 그림이 회전초밥이라고 해서 마치 원형처럼 느껴져서 처음에 당황해하실 수 있는데요.

 

알고보면 간단합니다.

배열 길이(N개) 이상 넘어가면 해당 배열 길이만큼 % 연산을 수행하면 되니까요!

 

나머지는 문제에서 주어졌으니까 문제 없습니다.

 

중요한건!

연속해서 먹는 접시의 수와 쿠폰 번호 입니다.

 

연속해서 먹는 접시 = Sliding Window(길이는 K) 를 설정하고, 이를 한 칸씩 움직이면서 최대 먹을 수 있는 초밥의 종류를 얻으면 끝!

 

 

 

쿠폰 번호에 해당하는 초밥이 Window 안에 있다면?

-> count는 그대로!

 

쿠폰 번호에 해당하는 초밥이 Window 안에 없다면??

-> 오오! 초밥 한 종류 공짜로 하나 더 먹을수있네? 개이득! count + 1

 

해서 최대 초밥의 종류 개수를 얻으면 됩니다.

 

 

 

알고리즘

---

1. 스시 종류 번호 배열에 넣기

 

2. 초밥의 종류 개수(d) 크기의 배열 선언 -> 해당 배열은 index 번호의 초밥을 먹은 개수를 저장

 

3. 처음 0번부터 k개수만큼 먹었을 때를 파악해 값을 설정

  -> for(int i = 0; i < k; i++) 하면 쉽죠? 

  -> 이 초밥을 하나도 안먹었다면? count++

  -> 이 값이 현재 최대 초밥의 종류 개수 입니다.

 

4. 1번부터 n-1까지 for문으로 sliding window 수행

-> 1번부터 n-1번까지 start만 이동시키면 k는 고정이기 때문에 end를 활용할 필요가 없습니다.

-> end = (i + k - 1) % n 로 선언하고, 해당 지점에서 3번과 비슷하게 처리합니다. (코드참고)

-> start 지점 또한 end와 마찬가지로 3번과 비슷하게 처리합니다. (코드참고)

-> 현재 count값과 max값을 비교해서 max값을 갱신합니다. 이 때, 맨 위에 적은 것과 같이 쿠폰초밥을 먹었는지 안먹었는지 파악해서 개수파악을 잘 합니다.

 

 

이상입니다.

 

감사합니다.

 

소스코드

---

 

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	// 회전초밥
	// 투포인터
	public class p2531 {
	static int n, d, k, c;
	static int[] sushi;
	static int[] eated;
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	n = Integer.valueOf(st.nextToken());
	d = Integer.valueOf(st.nextToken());
	k = Integer.valueOf(st.nextToken());
	c = Integer.valueOf(st.nextToken());
	sushi = new int[n];
	eated = new int[d + 1];
	// 스시 종류 번호 배열에 넣기
	for(int i = 0; i < n; i++) {
	sushi[i] = Integer.valueOf(br.readLine());
	}
	// 1) 처음 0번부터 k개수만큼 먹었을 때의 초기화
	int count = 0;
	for(int i = 0; i < k; i++) {
	if(eated[sushi[i]] == 0) {
	count++;
	}
	eated[sushi[i]]++;
	}
	int maxLen = count;
	// 2) 1번부터 n-1번까지 start만 이동시키면 k는 고정이기 때문에 end를 활용할 필요가 없다.
	// i : start
	for(int i = 1; i < n; i++) {
	if(maxLen <= count) {
	if(eated[c] == 0) { // 아직 쿠폰초밥을 안먹은 상태
	maxLen = count + 1;
	}
	else { // 아직 쿠폰초밥을 먹은 상태
	maxLen = count;
	}
	}
	// end 이동
	int end = (i + k - 1) % n;
	if(eated[sushi[end]] == 0) {
	count++;
	}
	eated[sushi[end]]++;
	// start 이동
	eated[sushi[i - 1]]--; // start점 한 칸 이동했으니 이전의 초밥 제거
	if(eated[sushi[i - 1]] == 0) {
	count--;
	}
	}
	System.out.println(maxLen);
	}
	}

view raw p2531.java hosted with ❤ by GitHub