백준 15961 <회전초밥>

일반적으로 알고 있는 투 포인터 문제이다. 물론 투 포인터라는 개념을 알고 있지 않으면 풀 수 없는 문제이다.

 

투 포인터라고 생각하게 된 이유는 접시의 수가 3000000으로 300만 개 연속으로 먹는 접시의 수가 3000으로 각각을 시작점으로 두고 3000번간다고 치면 300만*3000  90억이라는 어마어마한 수가 나오기 때문에 당연히 안 될 것이라고 생각했기 때문이다.

 

문제의 알고리즘을 이해하자면 이렇다

총 30가지 종류의 초밥이 있기때문에 체크를 해줄 배열을 만들고 시작점으로부터 연속해서 뽑을 때까지 체크를 해준다

 

현재는 4개까지 고를 수 있기 때문에

이렇게 3가지 종류의 초밥을 먹을 수 있게 된다.

 

이 이후에는 시작점으로부터 한 개씩 줄이고 끝점인 30의 위치부터는 증가시키면서 계속 이런 식으로 검사를 하게 된다. 다음번의 예를 들자면

이렇게 진행하게 된다. 앞의 포인터가 30에서 시작해서 다시 30으로 돌아오기 전가지의 총 많은 종류의 수를 출력해주면 되는 문제이다.

 

위의 코드는 기본적으로 맨 처음 시작점에서 k만큼 연속적으로 가면서 검사를 하고 만약 공짜로 주는 쿠폰 번호의 초밥을 안 먹을 경우 1을 더해주게 된다.

 

이후에는 위에서 설명한 것과 같다.

코드에서는 1차원 배열로 인해 원형으로 이어져 있지 않기 때문에 끝까지 간 다음 K이전까지 한 번 더 회전할 수 있도록 작성했다

전체 코드 

import java.awt.Point;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main{

	static int n, d, k, c, num[], sp, visit[], count,result=0;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		d = kb.nextInt();
		k = kb.nextInt();
		c = kb.nextInt();
		num = new int[n];
		visit = new int[d + 1];
		for (int i = 0; i < n; i++) {
			num[i] = kb.nextInt();
		}
		for (int i = 0; i < k; i++) {
			if(visit[num[i]]==0) {
				count++;
			}
			visit[num[i]]++;
		}
		result=Math.max(count,result);
		if(visit[c]==0) {
			result++;
		}
		for (int i = k; i < n; i++) {
			if(visit[num[sp]]==1) {
				count--;
			}
			visit[num[sp++]]--;
			if(visit[num[i]]==0) {
				count++;
			}
			visit[num[i]]++;
			if(visit[c]==0) {
				result=Math.max(count+1,result);
			}
			else {
				result=Math.max(count,result);
			}
		}
		for (int i = 0; i < k; i++) {
			if(visit[num[sp]]==1) {
				count--;
			}
			visit[num[sp++]]--;
			if(visit[num[i]]==0) {
				count++;
			}
			visit[num[i]]++;
			result=Math.max(count,result);
			if(visit[c]==0) {
				result=Math.max(count+1,result);
			}
			else {
				result=Math.max(count,result);
			}
		}
		System.out.println(result);
	}

}

시간이 많이 걸린다! 하면 Scanner를 BufferedReader로 풀면 시간은 단축!!