[Unsolved][JAVA] 백준 2531 15961 회전 초밥

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

2531번: 회전 초밥

 

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

15961번: 회전 초밥

 

1. 서론

 

2531(실버, 쉬운 버전) 회전초밥 풀다가 브루트포스라면서 시간 초과 나서 투 포인터로는 안 되는 거냐? 하고 슬라이딩 윈도우로 넘어가서 15961(골드, 어려운 버전)까지 되었다는 사연....

 

*투 포인터와 슬라이딩 윈도우의 차이

 

https://ansohxxn.github.io/algorithm/twopointer/

(C++) 투포인터 알고리즘, 슬라이딩 윈도우 알고리즘, Prefix Sum 구간합

 

투 포인터는 구간이 가변적이고, 슬라이딩 윈도우는 구간이 고정적이라고 한다. 회전초밥의 경우 k로 구간이 고정되어 있으니 슬라이딩 윈도우라고 볼 수 있나 보다.

 

 

 

 

 

 

 

2. 문제 풀이

 

두 문제는 내용은 같은데 처리해야 하는 숫자의 범위가 다르다. 골드 문제가 훨씬 범위가 크기 때문에 실, 골로 나뉘게 되었다.

그리고 이 문제는 뭔가 설명이 좀 명확하지가 않아서 이해하는데 좀 걸렸는데 화끈하게 말하자면 이런 문제다.

 

배열에서 숫자 k개가 연속으로 나오면 쿠폰 한 개를 받게 된다. 이때 k개는 각자 다른 종류여야 한다. 이 쿠폰은 c라는 초밥의 쿠폰이다. 그런데 먹은 초밥의 가짓수를 세야 하므로 만약 이 경우에 k개 안에 c가 포함이 되어있다면 다 먹은 초밥이 가짓수는 k개가 되는 것이고, 아니라면 k + 1개가 된다. 이때 배열을 도는 방향은 왼쪽에서 오른쪽 방향으로 정해져 있다. 이럴 때 초밥의 가짓수의 최댓값은 무엇인가를 구하는 문제이다.

 

 

 

 

 

 

만약 이걸 정말로 다 돌리게 된다면 시간 초과를 겪게 된다. 그래서 시간을 줄이기 위해 사용하는 것이 투 포인터, 슬라이딩 윈도우이다.

난 이 알고리즘의 개념만 어렴풋이 알고 있어서 당연히 응용하지 못했고 블로그를 찾아보게 되었다.

 

https://velog.io/@hahahaa8642/%EB%B0%B1%EC%A4%80-15961%EB%B2%88-%ED%9A%8C%EC%A0%84-%EC%B4%88%EB%B0%A5-JAVA-%ED%92%80%EC%9D%B4

[백준] 15961번 회전 초밥 JAVA 풀이

 

투 포인터, 슬라이딩 윈도우의 핵심은 배열은 그대로 있고 index들을 움직여 계산하는 방식이다. 그래서 배열을 돌지 않기 때문에 상당히 시간이 절약되는 것이다. 그런데? 앞에서 하나 빼고, 뒤에서 하나 넣어서 탐색한다는 것은 알겠는데 그 방법을 구현 못하겠어서 코드를 보니까 확실히 무슨 소리인지 알 것 같은 느낌이 들었다^^

 

이 블로그 같은 경우에는 원래의 입력받은 배열 말고 앞뒤로 미는 것을 체크할 수 있는 배열을 하나 더 뒀다. 그래서 계수 정렬처럼 그 index의 값이 있으면 +1 -1 하는 식으로 초밥을 앞에꺼 빼고 뒤에꺼 넣는 식으로 체크해서 문제 풀이를 진행했다.

 

 

 

 

 

 

3. 코드 설명

 

import java.io.*;
import java.util.*;

public class Main {

	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[] a = new int[n];
		
		for (int i = 0; i < n; i++) 
			a[i] = Integer.parseInt(br.readLine());
		
		int cnt = 0; //초밥의 수
		int[] visit = new int[d + 1]; //먹었던 초밥 개수를 저장할 배열
		for (int i = 0; i < k; i++) { //k개 초기 설정
			if (visit[a[i]]== 0)
				cnt++;
			visit[a[i]]++;
		}
		
		int check = cnt; //초밥 수 체크
		for (int i = 1; i < n; i++) {
			if (check <= cnt) {
				check = cnt;//큰값이 있으면 큰 값 저장
				if (visit[c] == 0) //쿠폰에 적힌 초밥이 배열에 없는 경우
					check++;
			}
			//슬라이드 이동시 앞쪽 값 하나 빼줌
			visit[a[i - 1]]--;
			if (visit[a[i - 1]] == 0) cnt--;
			
			//슬라이드 이동시 뒤엣값 넣어줌, 초밥은 회전하기 때문에 % n
			if (visit[a[(i + k - 1) % n]] == 0) cnt++;
			visit[a[(i + k - 1) % n]]++;
		}
		System.out.println(check);
	}
}

 

코드 자체는 심플하다. visit 배열에서 현재 k개의 구간을 체크해준다.

그래서 초기값은 0~k-1까지 넣어두고 반복문을 돌면서 맨 앞의 값은 빼주고, 맨 뒤의 값은 넣어줘서 항상 k개의 값을 확인한다.

이때 cnt로 k개 중 중복을 제외한 진짜 가짓수가 몇 개인지 적고, check로 최댓값을 계속 갱신해준다.

index들은 현재 제일 앞의 초밥 index가 i이므로 a[i - 1]은 빼주고 i를 기준으로 k번째 값인 a[(i + k - 1) % n]을 추가해준다.

이때 n의 나머지인 이유는 초밥이 회전하므로 배열 맨 마지막 값을 넘어서 다시 0번째로 돌아가기 때문이다.

 

블로그에 적고 나니 이해는 가는데 실전에서 풀 수 있을지 원,, ㅎ 쉽지 않은 문제다.

처음에는 실버 문제 풀라고 했는데 실버랑 골드가 같은 코드로 풀리더라...(당연함. 범위 말고는 같은 문제임)