[백준] 2531번 '회전 초밥' - Java

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

---

문제

---

풀이

문제의 조건은 요약해서 "연속으로 k개를 먹었을 경우, 최대로 먹을 수 있는 초밥의 개수" 라고 할 수 있겠습니다.

 

그래서 제가 접근한 방식은 투 포인트를 이용하여 먹은 초밥을 확인하고, Map을 이용해서 먹은 초밥을 카운트하는 방식이었습니다.

 

public static int solution(int[] sushi, Map<Integer, Integer> eated, int n, int k, int c) {
		// 투 포인트 left와 right (k개 만큼 슬라이딩 윈도우)
        int left = 0, right = k-1;
		int ans = 0;
		
		// 첫 윈도우 설정 (0~k-1번째)
		for(int i=0; i<k ;i++) {
        	// map 갱신
			eated.put(sushi[i], eated.get(sushi[i]) + 1);
		}
        // 서비스 초밥에 대한 map 갱신
		if(eated.get(c) == 0) eated.put(c, 1);
		
		int cnt = 0; // 초밥 종류
		for(Integer key : eated.keySet()){
			if(eated.get(key) >= 1) {
				cnt ++; // map 확인 후 cnt 갱신
			}
		}
		if(ans < cnt) ans = cnt;
		
        // 첫 윈도우의 이후의 윈도우들 (n-1회 시행으로 설정했으나, 첫 시행 제외 n-2회이므로 n-2회 시행으로 변경해도 됨)
		for(int i=0; i<n; i++) {
			cnt = 0; // 매 회마다 초기화
			left ++;
			right ++;
			eated.put(sushi[left-1], eated.get(sushi[left-1]) - 1); // 윈도우에서 빠진 부분은 -1
			eated.put(sushi[right%n], eated.get(sushi[right%n]) + 1); // 윈도우에 추가되는 부분은 +1
			
			eated.put(c, eated.get(c) + 1); // 서비스 +1
			
			for(Integer key : eated.keySet()){
				if(eated.get(key) >= 1) {
					cnt ++;
				}
			}
			if(ans < cnt) ans = cnt;
		}
		return ans;
	}

 

 

밑은 전체 코드입니다.

 

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 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int n, d, k, c;
		n = Integer.valueOf(st.nextToken());
		d = Integer.valueOf(st.nextToken());
		k = Integer.valueOf(st.nextToken());
		c = Integer.valueOf(st.nextToken());
		
		int[] sushi = new int[n];
		Map<Integer, Integer> eated = new HashMap<Integer, Integer>();
		for(int i=1; i<=d; i++) eated.put(i, 0);
		for(int i=0; i<n; i++) {
			sushi[i] = Integer.valueOf(br.readLine());
		}
		
		int ans = solution(sushi, eated, n, k, c);
		System.out.println(ans);
	}
	
	public static int solution(int[] sushi, Map<Integer, Integer> eated, int n, int k, int c) {
		int left = 0, right = k-1;
		int ans = 0;
		
		
		for(int i=0; i<k ;i++) {
			eated.put(sushi[i], eated.get(sushi[i]) + 1);
		}
		if(eated.get(c) == 0) eated.put(c, 1);
		
		int cnt = 0;
		for(Integer key : eated.keySet()){
			if(eated.get(key) >= 1) {
				cnt ++;
			}
		}
		if(ans < cnt) ans = cnt;
		
		for(int i=0; i<n; i++) {
			cnt = 0;
			left ++;
			right ++;
			eated.put(sushi[left-1], eated.get(sushi[left-1]) - 1);
			eated.put(sushi[right%n], eated.get(sushi[right%n]) + 1);
			
			eated.put(c, eated.get(c) + 1);
			
			for(Integer key : eated.keySet()){
				if(eated.get(key) >= 1) {
					cnt ++;
				}
			}
			if(ans < cnt) ans = cnt;
		}
		return ans;
	}
}

 

 

원래의 생각

set을 이용해서 중복제거를 하려고 했으나, 계속해서 틀렸습니다 가 떴습니다. 그래서 왜인가 했더니 set의 내용을 remove했을 때에 원래 있던 초밥도 나가게 되는 문제였습니다.

 

하지만 반례들이 정상적으로 작동해서 왜인지를 한참 해매던 와중에 깨달았습니다..

 

만약 set을 사용하는 분들은 저와 같이 처리를 여러 번 하는 것을 꺼려서 중복처리를 알아서 하라고 썼을거에요.. 어차피 똑같은 처리 해야할 것 같으니 그냥 map이나 배열 쓰는 것도 괜찮을 것 같네요.

배열을 사용하지 않은 이유는 전체 인덱스를 왔다갔다 해야할 것 같아서 안 썼는데 음 쓰면 안 되려나요

아니면 큐를 이용하는 방법도 고려해보심이.. 저도 map에 있는 key값들 value가 1보다 큰지 작은지 확인했을 때 시간초과 안 나왔으니깐요 큐를 이용해서 하는것도 괜찮을것 같네요

 

삽질했을땐 연속된 k개가 아니라 다른 것들도 먹어도 됐던 건가?! 하면서.. 전체를 map에 집어넣고 c도 추가로 집어넣고 그런 시행착오를 겪었더랬죠..

 

밑은 set을 이용한 방법입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int n, d, k, c;
		n = Integer.valueOf(st.nextToken());
		d = Integer.valueOf(st.nextToken());
		k = Integer.valueOf(st.nextToken());
		c = Integer.valueOf(st.nextToken());
		
		int[] sushi = new int[n];
		int[] flavor = new int[d];
		for(int i=0; i<n; i++) {
			sushi[i] = Integer.valueOf(br.readLine());
			flavor[sushi[i]-1]++;
		}
		
		int ans = solution(sushi, flavor, n, k, c);
		System.out.println(ans);
	}
	
	public static int solution(int[] sushi, int[] flavor, int n, int k, int c) {
		int left = 0, right = k-1;
		int ans = 0;
		Set<Integer> set = new HashSet<>();
		for(int i=0; i<k ;i++) {
			set.add(sushi[i]);
		}
		set.add(c);
		if(ans < set.size()) ans = set.size();
		
		for(int i=0; i<n; i++) {
			left++;
			if(flavor[sushi[left-1]-1] <= 1) set.remove(sushi[left-1]);			
			
			right++;
			set.add(sushi[right%n]);
			set.add(c);
			
			if(ans < set.size()) ans = set.size();
		}
		return ans;
	}
}

---

회고

문제 이해를 잘 하자!! ㅜ