[백준 / Java] 15961번: 회전초밥 (골드4)

문제 풀이 날짜: 2023.08.24
포스트 작성일: 2023.08.26

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

BOJ 15961번: 회전초밥 (골드4)

 

키워드

투 포인터, 슬라이딩 윈도우

 

풀이 접근법

• 주어진 그림이 그래프와 유사하지만 그래프로 풀기는 어렵다.
• 투 포인터와 슬라이딩 윈도우를 사용해 풀이한다. k개의 원소를 한꺼번에 확인하면서 옆으로 한 칸씩 민다.
• 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공 ⇒ 결과로 찾은 k개의 초밥 가짓수에 이 가짓수를 보너스로 더할 수 있음. (+1)
• 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다. ⇒ 주어진 레일에 없어도 무관.
• 투 포인터를 이용한 풀이
  • 투 포인터 변수 p와 q는 항상 k(연속해서 먹는 접시 수)만큼 차이난다. p와 q를 1씩 증가시키며 탐색했다가 가장 처음 상태로 되돌아 온다면 탐색을 멈춘다.
  • Set에 현재까지 선택한 접시의 가짓수를 저장한다. Set에 쿠폰번호에 해당하는 접시가 있다면(contains()) 그대로 결과를 취하고, 있지 않으면 쿠폰 접시를 포합한 가짓수를 결과로 저장한다.
• 주의해야 할 반례
  • 문제에서 주어진 예시에서 {7, 9, 7, 30} 이라는 묶음을 확인할 때, 이 다음 탐색에는 첫 번째 접시(7)를 제거하고 마지막 위치에 새 접시(2)를 가져와야 한다.
  • 따라서 다음 탐색의 이상적인 접시 묶음은 {9, 7, 30, 2} 이다.
  • 그런데 Set에서 7을 제거해버리면 Set 안의 모든 7이 삭제되기 때문에 {9, 30, 2}가 되어버린다.
  • 따라서 중복되는 접시 수를 세고 있다가 0이 되는 순간에만 Set에서 제거해주자.

 

코드

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));

		String[] temp = br.readLine().split(" ");

		int N = Integer.parseInt(temp[0]); // 벨트에 놓인 접시의 수
		int d = Integer.parseInt(temp[1]); // 초밥의 가짓수
		int k = Integer.parseInt(temp[2]); // 연속해서 먹는 접시 수
		int c = Integer.parseInt(temp[3]); // 쿠폰번호

		int[] dishes = new int[N]; // 벨트 위에 놓인 모든 접시
		int[] selections = new int[d + 1]; //중복 접시 세기, 0은 사용하지 않음
		Set<Integer> set = new HashSet<>(); // 선택된 접시의 가짓수를 모은다.

		for (int i = 0; i < N; i++) {
			int v = Integer.parseInt(br.readLine());
			dishes[i] = v;
		}

		int p = 0;
		int q = p + k - 1;

		for (int i = 0; i <= q; i++) {
			set.add(dishes[i]); // 초기 상태
			selections[dishes[i]]++;
		}

		int initP = p;
		int initQ = q;

		int currMax = -1;
		do {
			currMax = Math.max(set.size(), currMax);

			if (!set.contains(c)) {
				currMax = Math.max(set.size() + 1, currMax);
			}
			
			selections[dishes[p]]--;
			if(selections[dishes[p]] == 0) {
				set.remove(dishes[p]);
			}
			
			if (p + 1 >= N) {
				p = 0;
			} else p++;

			if (q + 1 >= N) {
				q = 0;
			} else q++;
			
			selections[dishes[q]]++;
			set.add(dishes[q]);
		} while (p != initP || q != initQ);
		
		System.out.println(currMax);
	}
}

---

 

 

git 링크

(git 링크 첨부)