[백준 BOJ/Silver I] 2531번 : 회전 초밥

 

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

2531번: 회전 초밥

 

- 먹을 수 있는 서로 다른 초밥의 가짓수를 구해야하기 때문에 같은 번호가 들어가지 않도록 중복을 제거해주기 위해 HashSet을 사용하여 먹은 초밥을 추가해주었다.

- k개의 초밥을 담은 후 쿠폰에 적힌 c 초밥이 포함되어 있지 않다면 하나는 무료 증정되므로 담은 초밥 개수에 +1을 해주어야한다

 

- 중복이 있어서 sushi 사이즈가 k가 되지 않았더라도 사실상 k개를 담아서 먹은건 맞기 때문에 이때도 c 초밥을 무료 증정해주어야하는지 여부를 꼭 확인해주어야한다 이게 없으면 틀린다!

if(sushi.size() == k) { // 중복없이 k개 담은 경우
	if(!sushi.contains(c)) { 
		result = k + 1; // c 초밥 포함하고 있지않으면 c 증정
	} else {
		result = k;
	}
}
else { // 중복 있어서 사이즈가 k 안되는 경우
	if(!sushi.contains(c)) { 
		result = sushi.size() + 1; // c 초밥 포함하고 있지않으면 c 증정
	} else {
		result = sushi.size();
	}
}

 

 

 

 

아래는 최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 = Integer.parseInt(st.nextToken()); // 접시의 수
		int d = Integer.parseInt(st.nextToken()); // 초밥의 가짓수
		int k = Integer.parseInt(st.nextToken()); // 연속해서 먹는 접시의 수
		int c = Integer.parseInt(st.nextToken()); // 쿠폰 번호
		int[] belt = new int[N+k-1]; // 회전 초밥인걸 생각해서 마지막 인덱스도 k개만큼 짝 지을 수 있도록 더 늘려줌
		Set<Integer> sushi = new HashSet<Integer>(); // 같은 번호인 경우 안 넣으려고 HashSet 사용
		int result;
		int max = -1;
		
		for(int i = 0; i < N; i++) {
			belt[i] = Integer.parseInt(br.readLine());
		}
		int index = 0;
		for(int i = N; i < N+k-1; i++) {
			belt[i] = belt[index];
			index++;
		}
//		for(int i = 0; i < N+k-1; i++) {
//			System.out.println(belt[i]);
//		}
		
		for(int i = 0; i < N; i++) {
			result = 0;
			for(int j = i; j < i + k; j++) {
				sushi.add(belt[j]);
			}
			
			if(sushi.size() == k) { // 초밥 k개 담는거 만족
				if(!sushi.contains(c)) { 
					result = k + 1; // c 초밥 포함하고 있지않으면 c 증정
				} else {
					result = k;
				}
			}
			else { // k개 안되는 경우
				if(!sushi.contains(c)) { 
					result = sushi.size() + 1; // c 초밥 포함하고 있지않으면 c 증정
				} else {
					result = sushi.size();
				}
			}
			max = Math.max(max, result);
			sushi.clear();
		}
		
		System.out.println(max);
	}

}

 

- int[] belt = new int[N+k-1]; ← belt 배열을 더 늘려준 이유는 마지막 인덱스도 k개만큼 담아서 확인해보기 위함이었다 회전초밥이기 때문에!!

 

 

통과는 했지만 성능이 지이이이이ㅣㄴ짜 안좋다 간신히 통과한 느낌😐😐

처음부터 끝까지 모든 인덱스를 돌며 k개씩 끊어서 하나하나 확인해주니 당연히 그럴수밖에 없을거같다

그리고 sushi 사이즈가 k개 될떄 안될때 나눠서 같은 로직을 반복해주는거도 굉장히 비효율적인거같고,,

 

 

 

그래서 다른 방법으로 다시 풀어보려고 했는데 아예 문제는 같으면서 범위가 크게 주어진 문제가 있었다

 

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

15961번: 회전 초밥

확인을 위해 같은 코드로 제출해봤더니 당연히 시간 초과

그래서 1940번을 다시 풀기보다는 15961번을 시간 초과나지 않게 통과하는걸 목표로 풀어보려고한다

슬라이딩 윈도우, 투 포인터 방법으로 풀어야하는듯!

 

 

↓

 

https://fruits2lim.tistory.com/entry/%EB%B0%B1%EC%A4%80-BOJGold-IV-15961%EB%B2%88-%ED%9A%8C%EC%A0%84-%EC%B4%88%EB%B0%A5

[백준 BOJ/Gold IV] 15961번 : 회전 초밥

 

풀었다!!!