[BOJ]백준 15961번: 회전초밥(C++/Java/Python)/Two Pointer

www.acmicpc.net/problem/15961

15961번: 회전 초밥

오랜만에 풀어보는 투포인터 문제!

투포인터는 보통 최적의 해를 갖는 특정 구간을 찾아내는 문제에서 많이 사용한다

 

이 문제는 중복되지 않는 원소의 개수를 최대로 하는 k개의 연속된 구간을 찾아내는 문제이당

(+쿠폰 사용을 위해 쿠폰 번호 element 또한 포함되어 있는지 확인)

예제에서는 그림과 같이 [2, 7, 9, 25]에 보너스로 30까지 포함한 5가 정답이 된다.

 

 

이진탐색 문제와 마찬가지로 left, right 포인터와 해당 포인터들의 위치가 변하는 조건 및 처리가 중요하다고 생각했기 때문에

1️⃣ 현재 구간의 중복X 원소 개수가 k개 이상이면 -> left ++

2️⃣ 현재 구간의 중복X 원소 개수가 k개 미만이면 -> right ++

이 과정에서 중복되지 않는 원소는 Map(파이썬은 Dictionary)를 이용해서 관리해주고, Circular Array 처리를 해주었다

 

코드(C++)

#include <bits/stdc++.h>
using namespace std;

int n, d, k, c;
vector<int> sushi;
map<int, int> m;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> d >> k >> c;
	for (int i = 0,t; i < n; i++) {
		cin >> t; sushi.push_back(t);
		if (m.find(t) == m.end())m.insert(make_pair(t, 0));
	}
	if (m.find(c) == m.end())m.insert(make_pair(c, 0));

	int left = 0, right = 0, cnt = 0, kind = 0, answer = 0;
	while (left != n - 1) {
		if (cnt >= k) {
			if (--m[sushi[left]] == 0)
				kind--;
			left = (left + 1) % n;
			cnt--;
		}
		else {
			if (m[sushi[right]]++ == 0)
				kind++;
			right = (right + 1) % n;
			cnt++;
		}
		if (kind >= answer) {
			answer = kind;
			if (m[c] == 0)answer++;
		}
	}
    cout<<answer;
	return 0;
}

코드(Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        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];
        Map<Integer,Integer> m=new HashMap<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            sushi[i]=Integer.parseInt(st.nextToken());
            if(!m.containsKey(sushi[i]))
                m.put(sushi[i],0);
        }
        if(!m.containsKey(c))
            m.put(c,0);

        int left=0,right=0,cnt=0,kind=0,answer=0;
        while(left!=n-1){
            if(cnt>=k){
                m.put(sushi[left],m.get(sushi[left])-1);
                if(m.get(sushi[left])==0)
                    kind--;
                left=(left+1)%n;
                cnt--;
            }else{
                if(m.get(sushi[right])==0)
                    kind++;
                m.put(sushi[right],m.get(sushi[right])+1);
                right=(right+1)%n;
                cnt++;
            }
            if(kind>=answer){
                answer=kind;
                if(m.get(c)==0)answer++;
            }
        }
        bw.write(answer+"");

        br.close();
        bw.flush();
        bw.close();

    }
}

코드(파이썬)

import sys

n,d,k,c=map(int,sys.stdin.readline().split())
sushi=[]
for _ in range(n):
    sushi.append(int(sys.stdin.readline()))
keys=dict.fromkeys(set(sushi),0)
if keys.get(c) is None:keys[c]=0

left=0
right=0
cnt=0
kind=0
answer=0
while left!=n-1:
    if cnt>=k:
        keys[sushi[left]]-=1
        if keys[sushi[left]]==0:
            kind-=1

        left=(left+1)%n
        cnt-=1
    else:
        if keys[sushi[right]]==0:
            kind+=1
        keys[sushi[right]]+=1
        right=(right+1)%n
        cnt+=1
    if kind>=answer:
        answer=kind
        if keys[c]==0:answer+=1
#print(sushi)
print(answer)