백준 15961 회전 초밥 c++, Kotlin (투 포인터)

문제 출처 : https://www.acmicpc.net/problem/15961

15961번: 회전 초밥

문제

회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다. 초밥의 종류를 번호로 표현할 때, 다음 그림은 회전 초밥 음식점의 벨트 상태의 예를 보여주고 있다. 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다. 

새로 문을 연 회전 초밥 음식점이 불경기로 영업이 어려워서, 다음과 같이 두 가지 행사를 통해서 매상을 올리고자 한다.

1. 원래 회전 초밥은 손님이 마음대로 초밥을  고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한다. 
2. 각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공한다. 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다.  

위 할인 행사에 참여하여 가능한 한 다양한 종류의 초밥을 먹으려고 한다. 위 그림의 예를 가지고 생각해보자. k=4이고, 30번 초밥을 쿠폰으로 받았다고 가정하자. 쿠폰을 고려하지 않으면 4가지 다른 초밥을 먹을 수 있는 경우는 (9, 7, 30, 2), (30, 2, 7, 9), (2, 7, 9, 25) 세 가지 경우가 있는데, 30번 초밥을 추가로 쿠폰으로 먹을 수 있으므로 (2, 7, 9, 25)를 고르면 5가지 종류의 초밥을 먹을 수 있다. 

회전 초밥 음식점의 벨트 상태, 메뉴에 있는 초밥의 가짓수, 연속해서 먹는 접시의 개수, 쿠폰 번호가 주어졌을 때, 손님이 먹을 수 있는 초밥 가짓수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 ≤ k ≤ 3,000 (k ≤ N), 1 ≤ c ≤ d이다. 두 번째 줄부터 N개의 줄에는 벨트의 한 위치부터 시작하여 회전 방향을 따라갈 때 초밥의 종류를 나타내는 1 이상 d 이하의 정수가 각 줄마다 하나씩 주어진다. 

출력

주어진 회전 초밥 벨트에서 먹을 수 있는 초밥의 가짓수의 최댓값을 하나의 정수로 출력한다.

알고리즘 분류

• 두 포인터
• 슬라이딩 윈도우

풀이

투 포인터에 기반한 풀이이지만, 두 포인터의 간격(k)가 정해져있으므로 본인은 굳이 end포인트를 따로 두지 않고 start 포인트에 k만큼 더하는 방법을 사용했다.(회전 초밥이므로, end 포인트가 배열의 끝에 다다랐을 때 끝나지 않고, 인덱스 0으로 넘어가는 것에 주의하자)

슬라이딩 윈도우라는 알고리즘은 굳이 알고 있지 않더라도 구현할 수 있으니 궁금하면 검색해보길 바란다.

 

풀이를 세 번 정도 바꿨는데, 문제를 제대로 읽지 않아서 원하는 답을 헷갈렸다.

우리가 구해야 할 값은, 인덱스 i부터 연속적으로 k개를 선택했을 때, 선택한 초밥들의 종류 개수이다!

i부터 연속적으로 k개를 선택하는 것은

0부터 k까지

1부터 k+1까지

2부터 k+2까지

~~~~~~

n-1부터 0+k-1까지

이기 때문에, i+1부터 j+1까지의 선택한 초밥들의 리스트는 i부터 j까지 초밥들의 리스트에서 j+1인덱스의 초밥을 더하고 i인덱스의 초밥을 빼면 된다.

여기서 주의할 점은 우리는 선택한 초밥의 개수를 구하는 것이 아닌, 선택한 초밥들의 종류를 구하는 것이기 때문에,

kind라는 변수를 두고, 어떠한 초밥의 종류가 1개 이상이면 더해주고, 어떠한 초밥의 종류가 0개라면 빼주는 식으로 i부터 j까지 초밥의 리스트에서 초밥 종류의 수를 구할 수 있다.

 

2022.01.25 - [알고리즘 문제 풀이/백준] - 백준 2531 회전 초밥 Kotlin (투 포인터)

투 포인터를 제대로 구현했다면 해당 문제의 코드와 현재 문제의 코드 동일하게 제출해도 통과한다. 

코드(c++)

#include <iostream>
#include <algorithm>

using namespace std;

int n, d, k, c;
int input[3000000];
int cnt[3001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> d >> k >> c;
	for (int i = 0; i < n; i++) {
		cin >> input[i];
	}
	int start = 0;
	int kind = 0;
	for (int i = 0; i < k; i++) {
		if (!cnt[input[i]]) {
			kind++;
		}
		cnt[input[i]]++;
	}

	int answer = kind;
	
	while (start <= n) {
		
		if (cnt[c]==0) {
			answer = max(answer, kind + 1);
		}
		else{
			answer = max(answer, kind);
		}
		if (!cnt[input[(start + k) % n]]++) {
			kind++;
		}
		if (--cnt[input[start]]==0) {
			kind--;
		}
		start++;
	}
	cout << answer;
	return 0;
}

코드(Kotlin)

val br = System.`in`.bufferedReader()
//2<=n<=30000
//2<=d<=3000
//2<=k<=3000
//1<=c<=d
fun main() = with(System.out.bufferedWriter()){
    //가짓수의 최댓값 구하기

    val (n, d , k , c )= br.readLine().split(' ').map{it.toInt()}
    val set = IntArray(d+1)
    val input = IntArray(n){br.readLine().toInt()}

    var cnt=0
    var answer=0
    var e =0
    while(e<k){
        val next = input[e]
        if(set[next]==0){
            cnt++
        }
        set[next]++
        e++
    }
    if(set[c]==0){
        answer = answer.coerceAtLeast(cnt+1)
    }
    else{
        answer = answer.coerceAtLeast(cnt)
    }

    for(s in input.indices){
        if(set[input[s]]==1){
            cnt--
        }
        set[input[s]]--
        if(set[input[e]]==0){
            cnt++
        }
        set[input[e]]++
        e = (e+1)%n

        answer = if(set[c]==0){
            answer.coerceAtLeast(cnt+1)
        } else{
            answer.coerceAtLeast(cnt)
        }
        if(answer==k+1){
            break
        }
    }

    write("$answer")
    close()
}