BOJ 2531번: 회전초밥

1. 문제

문제 바로가기> BOJ 2531번: 회전초밥

2531번: 회전 초밥

 

2. 풀이

두 포인터를 조작해가며, 푸는 문제다.

회전 초밥이 "회전하는 벨트 위"에 있음을 주의해야 한다.

따라서 종료 조건이 right == k-1, 즉 회전 초밥 벨트를 모두 확인했을 경우다!!!!

 

2.0.1. C++

      

      

      

    
    

      <cpp />
    
#include<iostream>
#define DISH 30001
#define KIND 3001
using namespace std;

int N, d, k, c; // 회전 초밥 벨트에 놓인 접시의 수, 초밥의 가짓수, 연속해서 먹는 접시의 수, 쿠폰 번호
int sushi[DISH], cnt[KIND];

void input(){
    cin >> N >> d >> k >> c;
    for(int i=0; i<N; i++) cin >> sushi[i];
}

void solution(){ // 주어진 회전 초밥 벨트에서 먹을 수 있는 초밥의 가짓수의 최댓값
    
    int ans = 0, kind = 1; 
    cnt[c] = 1; // coupon
    
    for(int i=0; i<k; i++){ // 처음 k개 
        if(cnt[sushi[i]] == 0) kind++;
        cnt[sushi[i]]++;
    }

    int left = 0, right = k-1; // two pointer
    while(1){

        // left
        cnt[sushi[left]]--;
        if(cnt[sushi[left]] == 0) kind--; // 종류 한 개 감소
        left++;

        //right
        right++; right%=N;
        if(right == k-1) break; // 회전 초밥 벨트 모두 확인 
        cnt[sushi[right]]++;
        if(cnt[sushi[right]] == 1) kind++; // 종류 한개 증가

        // ans update 
        ans = max(ans, kind);
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    // freopen("input.txt", "r", stdin);
    input();
    solution();
}

 

2.0.2. Java

      

      

      

    
    

      <java />
    
import java.io.*;
import java.util.*;

public class Main {
	
	public static void main(String[] args) throws Exception {
		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[] sushi = new int[N];
		int[] cnt = new int[d+1];
		
		for(int i=0; i<N; i++) sushi[i] = Integer.parseInt(br.readLine());
			
		int kind = 1, ans = 1; // 손님이 먹을 수 있는 초밥 가짓수의 최댓값
		cnt[c] = 1; // 쿠폰
		for(int i=0; i<k; i++) {
			if(cnt[sushi[i]]++ == 0) kind++;
			ans = Math.max(kind, ans);
		}
		
		
		int l=0, r=k-1;
		for(int i=0; i<N; i++) {
			if(--cnt[sushi[l++]]==0) kind--;
			if(cnt[sushi[(++r)%N]]++==0) kind++;
			ans = Math.max(kind, ans);
		}
		System.out.println(ans);
		br.close();
	}
}