BOJ - 15961 회전 초밥

15961 회전 초밥 : https://www.acmicpc.net/problem/15961

---

Problem

---

Solve

초밥의 종류 개수를 쿠폰을 고려하며 최대값을 구하는 문제이다.

초밥의 선택 여부를 가리키는 1차원 배열을 이용해서 현재 K범위에 초밥 종류의 개수를 구하고 K범위에 쿠폰 초밥이 없다면 초밥 종류의 개수에 +1을, 쿠폰 초밥이 있다면 현재 초밥 종류의 개수를 max값과 비교한다.

문제 풀이순서는 아래와 같다.

1. 초밥의 순서를 저장할 배열(sushi)와 초밥의 선택 여부를 저장할 배열(visit) 초기화
2. sushi의 0부터 K-1까지의 종류를 visit에 +1식 갱신한다.
3. 앞 포인터 i를 1부터 초밥의 개수(N)까지 반복한다.
   • i-1의 초밥을 범위에서 빼면서 범위안에 i-1의 초밥이 없다면 total에서 -1
   • i+k-1의 초밥을 범위에 추가하면서 범위안에 i+k-1의 초밥이 없다면 total +1
4. 현재 범위의 total이 max보다 크거나 같다면
   • 현재 범위에 쿠폰 초밥이 있는지 확인한다. 만약 없다면 max에 total과 1을 추가해준다. 쿠폰 초밥이 있다면 total로만 갱신한다.

---

Code

package org.algorithm.java.hyunjong.Algorithm.BOJ.투포인터;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class 회전초밥 {
	static int N;
	static int d;
	static int k;
	static int c;
	static int[] susi;
	static int[] visit;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		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());

		susi = new int[N];
		visit = new int[d+1];
		for(int i=0;i<N;i++){
			susi[i] = Integer.parseInt(br.readLine());
		}

		bw.write(String.valueOf(eat()));
		bw.flush();
		bw.close();
	}

	static int eat(){
		int total=0;
		int max=0;
        //K범위까지의 초밥 종류 개수 초기화
		for(int i=0;i<k;i++){
			if(visit[susi[i]]==0) total++;
			visit[susi[i]]++;
		}
		max = total;

		//앞 포인터를 기준으로 1부터 N까지 슬라이딩 윈도우 실행
		for(int i=1;i<N;i++){
        	//i-1 초밥을 visit에서 빼준다.
			visit[susi[i-1]]--;
            //만약 범위에 i-1의 초밥이 존재하지 않는다면 초밥 개수 total에서 -1을 해준다.
			if(visit[susi[i-1]] == 0) total--;
            //뒷 포인터 (i+k-1)%N의 초밥을 추가해준다.
			visit[susi[(i+k-1)%N]]++;
            //i+k-1 초밥이 새로 추가되었다면 total에 +1
            //앞 포인터가 N-1일때 sushi배열의 앞의 초밥들이 K범위에 포함되어있으므로 %N으로 앞 초밥들을 범위에 포함시켜준다.
			if(visit[susi[(i+k-1)%N]] == 1) total++;

			//초밥 종류의 개수 total이 현재 최대 종류의 개수보다 크거나 같다면 max를 갱신해준다.
			if(max<=total){
            	//범위에 쿠폰 초밥이 포함되어있지않다면 max에 total에 +1을 하여 갱신
				if(visit[c]==0){
					max = total + 1;
				}else{
                	//포함되어있지않다면 total만 max에 갱신.
					max = total;
				}
			}
		}

		return max;
	}
}

---

Result

---

Reference

https://buddev.tistory.com/43