[백준] 2531 회전 초밥 - 슬라이딩 윈도우(Sliding Window) + 투포인터(Two Pointer) + 원형(Circular) + HashMap(해시맵) JAVA

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

2531번: 회전 초밥

코드설명

슬라이딩 윈도우(Sliding Window) + 투포인터(Two Pointer) + 원형(Circular) + HashMap(해시맵) 활용하는 문제입니다.

 

1. 일반적인 투포인터에 단순이 직선을 처리하는것이 아닌, 원형으로 돌면서 적절한 구간에서 종료조건을 넣어야합니다.

여기서 적절한 구간은,

- start는 똑같이 start < N 으로 처리하지만,

- end같은경우 end < N + K로 처리하여 K 접시를 먹으면서 end % N을 처리하여 원형조건을 해결합니다.

 

헷갈리는점은 원형큐라고 모든 구간을 원형으로 다시 처리하는것이 아닌,

start < N 으로 처리하여 , start 는 N까지 처리하고, End를 처리함으로써 중복된 구간은 다시 처리하지 않습니다.

 

2. HashMap을 활용하여 먹은 음식의 번호를 가지고 있습니다.

- 처음에 풀어낼시 entry.getValue() 처리를 하여서 각 음식의 종류가 아닌 각 음식의 개수를 더하여 틀렸었습니다.

- 아래 주석의 예시코드를 보고 해당 오류를 찾아내어 기록해보았습니다.

//먹는 그릇의 종류를 확인
for(Map.Entry<Integer, Integer> entry : hashmap.entrySet()) {
    //그릇의 value가 0이 아닐경우 해당 조건의 음식을 한번이라도 먹었으므로 1개처리. 
    // 이전에 잘못하고 entry.getValue를 더해서 해당 문제 오류 복기함
    // foodKind += entry.getValue();
    // 예시 코드
    //2 2 2 2
    //1
    //1
    if(entry.getValue() != 0) {
    	
        foodKind += 1;	
    }
}

 

3. HashSet은 사용불가하고, HashMap을 사용해야 빠르게 처리할 수 있습니다.

이유는, 중복된 음식들이 존재하기 때문입니다. HashSet을 사용한다면 중복된 음식이 있을경우, 슬라이딩 되면서 개수가 존재하지 않기에 해당 Window(창)에 해당 재료가 존재함에도 삭제되겠지요.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	public static int N, d, k, c;
	public static int[] arr;
	public static int answer = 0;
	public static HashMap<Integer, Integer> hashmap = new HashMap<>();
    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());
    	
    	arr = new int[N];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	
    	slidingWindowWithTwoPoitner();
    	
		System.out.println(answer);
    }
    
    public static void slidingWindowWithTwoPoitner() {
    	int start = 0;
    	int end = 0;
    	int foodKind = 0;
    	
    	int endCircularIdx = 0;
    	
    	while(start < N) {
    		foodKind = 0;
    		
    		endCircularIdx = end % N;
    		
    		//슬라이딩 윈도우
    		while(start + k > end && end < N + k) {
    			endCircularIdx = end % N;
    			hashmap.put(arr[endCircularIdx], hashmap.getOrDefault(arr[endCircularIdx], 0) + 1);
    			end += 1;
    		}
    		
        	//먹는 그릇의 종류를 확인
        	for(Map.Entry<Integer, Integer> entry : hashmap.entrySet()) {
        		//그릇의 value가 0이 아닐경우 해당 조건의 음식을 한번이라도 먹었으므로 1개처리. 
        		// 처음 풀시 잘못하고 entry.getValue를 더해서 해당 문제 오류발견         		
        		if(entry.getValue() != 0) {
        			foodKind += 1;	
        		}
        	}
        	
        	//쿠폰번호가 존재하는지 확인
        	if(hashmap.get(c) == null || hashmap.get(c) == 0) {
        		foodKind += 1;
        	}
        	answer = Math.max(answer,  foodKind);
        	//초밥의 가짓수 한개 뺴줌
        	hashmap.put(arr[start], hashmap.get(arr[start]) - 1);
        	
        	//start 이동처리
        	start += 1;
    	}
    }
}

 

정답코드2입니다.

이 코드에서 가장 중요점은, 이 부분입니다.

for(int i=k-1; i<N + k - 1; i++) {

처음에는 N까지하는것 아니야? 라고 생각했습니다만, 슬라이딩 윈도우 기법과 원형 시프트배열을 곰곰히 생각해보면 이유를 알 수 있습니다.

이유는, 마지막 위치 N-1번째 에서 다시 0, 1, 2 ..의 초밥 구간도 고려해야하기 때문입니다.

사실상 여기서 i는 새로운 초밥을 구매하고, 이전 (i-(k-1) 번쨰 초밥은 구간에서 제거하는 슬라이딩 윈도우기법을 사용하므로 i는 <N이 아닌, < (N + K - 1)로 처리해야 모든 구간을 탐색한다는 점을 이해할 수 있습니다. 여기서 -1을 하는 이유는 arr[0]이 두번 처리되지 않게 하기 위함입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D, T, d, c;
	static int answer = 0;
	static int[] arr = new int[30001];
	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());
		
		for(int i=0;i<N; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		answer = slidingWindow();
		
		System.out.println(answer);
	}

	static int slidingWindow() {
		HashMap<Integer, Integer> hashmap = new HashMap<>();
		hashmap.put(c, 1);
		for(int i=0; i<k-1; i++) {
			hashmap.put(arr[i%N], hashmap.getOrDefault(arr[i%N], 0)+1);
		}
		
		for(int i=k-1; i<N + k - 1; i++) {
			hashmap.put(arr[i%N], hashmap.getOrDefault(arr[i%N], 0)+1);
			hashmap.put(c, hashmap.getOrDefault(c, 0) + 1);
			answer = Math.max(answer, hashmap.size());
			hashmap.put(c,  hashmap.get(c) - 1);
			if(hashmap.get(c) == 0) hashmap.remove(c);
			
			if(hashmap.get(arr[(i-(k-1))%N]) > 1) {
				hashmap.put(arr[(i-(k-1))%N], hashmap.get(arr[(i-(k-1))%N]) - 1);
			}else if(hashmap.get(arr[(i-(k-1))%N]) == 1 ) {
				hashmap.remove(arr[(i-(k-1))%N]);
			}
			
		}
		
		return answer;
	}
}