[백준 - 2531] 실버1 회전 초밥 (투포인터)

 

www.acmicpc.net/problem/2531

2531번: 회전 초밥

1. 유형

투 포인터

 

2. 풀이

이중 for문을 쓰면 시간 초과가 나기 때문에, 슬라이딩 윈도우를 써야한다

 

3. 코드

import java.util.Scanner;

public class back_2531회전초밥 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int d = sc.nextInt();
		int k = sc.nextInt();
		int c = sc.nextInt();
		int inp[] = new int[N+k-1];
		int answer=0;
		for (int i = 0; i < N; i++) {
			inp[i] = sc.nextInt();
		}
		for (int i = 0; i < k-1; i++) {
			inp[N+i] = inp[i];
		}
		int visit[] = new int[d+1];
		int sum=0;
		for (int i = 0; i < k; i++) {
			if(visit[inp[i]]==0) {
				sum++;
				visit[inp[i]]++;
			}else {
				visit[inp[i]]++;
			}
		}
		if(visit[c]==0) {
			answer = answer < sum+1 ? sum: answer;
		}else
			answer = answer < sum ? sum: answer;
		for (int i = k; i < inp.length; i++) {
			visit[inp[i-k]]--;
			if(visit[inp[i-k]]==0) sum--;
			if(visit[inp[i]]==0) {
				sum++;
				visit[inp[i]]++;
			}else {
				visit[inp[i]]++;
			}
			if(visit[c]==0) {
				answer = answer < sum+1 ? sum+1: answer;
			}else
				answer = answer < sum ? sum: answer;			
		}
		System.out.println(answer);
	}
}

 

처음에 k까지 탐색한다.

		for (int i = 0; i < k; i++) {
			if(visit[inp[i]]==0) {
				sum++;
				visit[inp[i]]++;
			}else {
				visit[inp[i]]++;
			}
		}

그 다음 k+1을 탐색하고 i-k는 지워주는 식으로 탐색을 한다

for (int i = k; i < inp.length; i++)

k-1부분을 지워준다

visit[inp[i-k]]--;
if(visit[inp[i-k]]==0) sum--;

다음 값이 방문하지 않았다면 값을 추가

if(visit[inp[i]]==0) {
    sum++;
    visit[inp[i]]++;