[JAVA]백준 2531번: 회전 초밥

https://www.acmicpc.net/problem/2531

2531번: 회전 초밥

 

 

 

 

| 문제 해결방법

 

⭐Idea : 투 포인터

 

 

처음에 투 포인터를 사용하는 문제인 건 알았는데, 큐를 사용해서 시간이 꽤 오래 걸렸다.

 

 

 

| 시간 문제 

 

시간을 좀  단축하고 싶어서 구글링으로 방법을 찾아보았는데,

 

참고 링크 : https://buddev.tistory.com/43

 

이 글쓴이 분의 코드가 굉장히 짧고 간결해서 이 방법을 사용한 후

 

시간을 약 6분에 1정도로 줄일 수 있었다.

 

 

 

처음에 큐와 함께

 

D+1(스시 종류) 크기만큼의 int 배열을 만들어서 들어오는 스시의 번호에+1을 해줄 생각을 했었다.

 

근데 큐를 꼭 써야한다고 생각해서 굳이 큐와 함께 쓸 필요는 없을 것 같아서 큐만 썼다.

 

그래서 정올 문제는 50%에서 실패했다🤔

 

 

| 해결 방법

 

하지만,

 

아래의 방법은 스시 종류의 int 배열'만' 사용한다.

 

그래서 코드가 간결하고, 빠르다! 

 

빠르게 성공😊

 

 

[JAVA] 해설 코드

package simulation;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class JOL_2577 {

	static int N, D, K, C;
	static int[] sushiTable;
	static int[] sushi;
	static int ans = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		sushiTable = new int[N];
		for (int i = 0; i < N; i++) {
			sushiTable[i] = Integer.parseInt(br.readLine());
		}
		sushi = new int[D+1];
		System.out.println(check());

	}

	private static int check() {
		int count = 0;
		int max = 0;
		for (int i = 0; i < K; i++) {
			int a = sushiTable[i];

			if(sushi[a]==0) {				
				count++;
			}
			sushi[a]++;
		}
		max = count;
		

		for(int i=0;i<N-1;i++) {
			// 최댓값 판별
			if(count >= max) {
				// 추가로 먹은 초밥이 현재까지 먹은 초밥에 포함되어 있지 않은 경우
				if(sushi[C]==0) {
					max = count+1;
				}
				// 추가로 먹은 초밥이 이미 포함되어 있는 경우
				else {
					max = count;
				}
			}
			
			// 첫 번째 요소 빼기 
			sushi[sushiTable[i]]--;
			// 첫 번째 요소와 중복되는 요소가 없다면 count-1 
			if(sushi[sushiTable[i]]==0) 
				count--;
			
			// 마지막 요소 추가 전 중복되는 요소가 있는지 확인(중복x -> count+1)
			if(sushi[sushiTable[(i+K)%N]]==0) 
				count++;
			//  마지막 요소 추가
			sushi[sushiTable[(i+K)%N]]++;
			
		}
		
		return max;

	}
}

 

 

[제출] 메모리 및 시간

 

 

✔int배열만 사용한 경우

 

 

 

✔큐만 사용한 경우