[백준] 2531/15961.회전초밥 (java) / 투포인터, 슬라이딩 윈도우

@투포인터, 슬라이딩 윈도우 / 32m

두 문제는 범위 제한 빼고는 같은 문제이다. 15961번이 범위가 훨씬 크다

2531번은 정올 2572번과 같고 15961번은 정올 2577번과 같다

쿠폰때문에 조금 헷갈렸다.

 

 

문제 링크

2531번

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

2531번: 회전 초밥

15961번(범위가 더 크다)

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

15961번: 회전 초밥

 

구현 포인트

이 문제는 슬라이딩 윈도우 원리를 이용하지만, 추가로 설정해줘야 할 조건이 몇가지 더 있다.

쿠폰때문에 많이 헷갈렸는데,

쉽게 생각해서 현재 먹은 초밥에 쿠폰번호와 같은 초밥이 포함되어 있으면 그대로 두고, 그렇지 않으면 +1을 해주면 된다.

예제에서 (9, 7, 30, 2), (30, 2, 7, 9), (2, 7, 9, 25) 는 모두 4종류로 종류의 개수는 동일하지만

앞의 (9, 7, 30, 2)와 (30, 2, 7, 9)는 이미 쿠폰번호와 같은 30번 초밥이 포함되어 있으므로 종류의 수는 4가지이다

그러나 (2, 7, 9, 25)는 30번 초밥이 포함되어 있지 않으므로 +1을 해줘서 총 5가지가 된다.

 

 

구현 방법

일단 맨앞부터 k개의 접시를 for문을 돌면서 종류의 개수를 센다

이때 같은 접시를 또 먹을 수 있으므로 boolean형 visit을 쓰지 않고, int형 visit을 사용했다.

 

처음에 틀렸다고 나왔는데, 반례는

2 2 2 2

1

1

이었다. (옳은 답은 2)

 

원래 코드대로 하면 1번 초밥으로 total이 1이 되고

2번 초밥이 포함되어 있지 않으므로 +1을 해서 2가 초기값이 된다.

 

그런데, 아래 for문을 돌면서 max체크하는 부분에서 또 2번초밥이 포함되지 않아서 +1을 해서 답이 3이 나왔다.

쿠폰을 적용하는 부분이 중복돼서 그랬던 것이라, 쿠폰 적용부분 한군데를 지웠더니 제대로 동작했다.

 

 

코드

이 소스로 2531, 15961번 모두 통과했다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	private static int N, d, k, c, arr[], visit[];
	
	public static void main(String[] args) throws Exception {
		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());
		
		visit = new int[d + 1];
		arr = new int[N];
		for (int i = 0; i < N; i++)
			arr[i] = Integer.parseInt(br.readLine());
		
		System.out.println(slide());
	}

	private static int slide() {
		int total = 0, max = 0;
		for (int i = 0; i < k; i++) {
			if (visit[arr[i]] == 0) total++;
			visit[arr[i]]++;
		}
//		if (visit[c] == 0) total++;
		max = total;
		
		for (int i = 1; i < N; i++) {
			if (max <= total) {
				if (visit[c] == 0)
					max = total + 1;
				else
					max = total;
			}
			visit[arr[i - 1]]--;
			if (visit[arr[i - 1]] == 0) total--;
			
			if (visit[arr[(i + k - 1) % N]] == 0) total++;
			visit[arr[(i + k - 1) % N]]++;
			
		}
		return max;
	}
}

 

예전에는 꽤 고생해서 풀었던 것 같은데(2시간 동안 풀었음..ㅎㅎ), 이번에는 비교적 금방 푼 것 같아서 좋다.

 

끝!