[Baekjoon][Java] 회전초밥

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

📒 문제

📒 예제

🎃 코드

import java.util.Scanner;

public class P_15961 {
	static int plate, allType, eventPlate, couponNumber;
	static int[] sushi;
	static int[] selected;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		plate = sc.nextInt();
		allType = sc.nextInt();
		eventPlate = sc.nextInt();
		couponNumber = sc.nextInt();
		sushi = new int[plate];
		selected = new int[allType + 1];

		for (int i = 0; i < plate; i++) {
			sushi[i] = sc.nextInt();
		}
		System.out.println(MaxTypeCount());
	}

	private static int MaxTypeCount() {
		int total = 0;

		for (int i = 0; i < eventPlate; i++) {
			if (selected[sushi[i]] == 0)
				total++;
			selected[sushi[i]]++;
		}

		int maxCnt = total;

		for (int i = 1; i < plate; i++) {
			int frontPlate = sushi[i - 1];
			selected[frontPlate]--;

			if (selected[frontPlate] == 0) {
				total--;
			}

			int endIndex = (i + eventPlate - 1) % plate;

			if (selected[sushi[endIndex]] == 0)
				total++;
                
			selected[sushi[endIndex]]++;

			if (maxCnt <= total) {
				if (selected[couponNumber] == 0)
					maxCnt = total + 1;
				else
					maxCnt = total;
			}
		}
		return maxCnt;
	}
}

🧸 정리

• 중복이라는 단어만 떠올리면 왜 Hash를 생각하게 되는건지..

• 제일 처음에는 LinkedList 노드처럼 next가 있는 새로운 객체를 만들었다. 왜냐하면 순환구조였기 때문에 next가 있는 노드를 만들면 편하겠다고 생각을 했다.

• 또한 eventPlate 만큼 먹은 plate를 담는 구조를 List를 사용했다.

• List를 사용한 이유는 0번째 index를 지우고 제일 마지막에 start + 1 번째 plate를 새로 add 해주면 될 것이라고 생각했기 때문이다.

• 하지만 계속 시간 초과가 났었다.. 결국엔 검색을 했다. 아무래도 List를 계속 조작하려한 부분에서 시간 초과가 난 것 같다. 물론 HashSet을 사용한 부분도

• 투포인터인건 알 수 있었지만 윈도우 슬라이스 라는 방법은 오늘 처음 알게되었다.

• 또 하나 배우고 갑니다 ~