백준15961 - 회전초밥 java

 

전형적인 투포인터 문제다 

map 자료구조를 이용하여 풀었다.

 

package a0405;

import java.util.*;
import java.io.*;

/*
 투포인터 이용하면 될듯?
 */

public class 백준15961_회전초밥 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int dish = sc.nextInt();
		int menu = sc.nextInt();
		int len = sc.nextInt();
		int plus = sc.nextInt();
		
		int[] arr = new int[dish];
		
		for(int i=0; i<dish; i++) {
			arr[i] = sc.nextInt();
		}
		
		Map<Integer, Integer> map = new HashMap<>();
		int maxcnt = 0;
		
		for(int i=0; i<len; i++) {
			if(map.containsKey(arr[i]))map.replace(arr[i], map.get(arr[i])+1);
			else {
				map.put(arr[i], 1);
			}
		}
		
		int nowcnt = map.size();
		
		int frontidx = 0;
		int backidx = len;
		int front = 0;
		int back =0;
		
		while(true) {
			front = arr[frontidx];
			back = arr[backidx];
			//System.out.println("front:"+front+" back:"+back);
				
			if(map.get(front)==1)map.remove(front);
			else map.replace(front, map.get(front)-1);

			if(map.containsKey(back))map.replace(back, map.get(back)+1);
			else map.put(back, 1);
			
			nowcnt = map.size();
			if(!map.containsKey(plus))nowcnt++;
			maxcnt = Math.max(nowcnt, maxcnt);

			frontidx++;
			backidx++;
			if(backidx==dish)backidx = 0;
			if(frontidx==dish)break;
		}
		System.out.println(maxcnt);
		
	}

}