백준 2531 회전초밥(Silver1)

정답코드

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

//method 1: brute Force 접근    
public class Main {
	
	static int [] sushi;
	static int N,d,k,c,maximum;
	
	public static void main(String[] args) throws NumberFormatException, 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());  
		maximum = Integer.MIN_VALUE;
		
		
		sushi = new int[N];
		
		for(int i = 0; i < N; i++) {
			sushi[i] = Integer.parseInt(br.readLine());
		}

		bruteForce();
		System.out.println(maximum);
	}
	
	public static void bruteForce() {
		for(int i = 0; i < N; i++) {
			int cnt = 0; 
			boolean []visited = new boolean[d+1];
			//모든 인덱스에 대해서 연속해서 먹을 K만큼 비교 
			for(int j = 0; j < k; j++) {
					//저장한 초밥 인덱스를 넘어가는 경우 -> 앞과 뒤는 이어져있다
					if(!visited[sushi[(i+j)%N]]) {
					cnt++;
					visited[sushi[(i+j)%N]] = true;
				}
				
			}
			//만약 쿠폰에 저장되어있는 초밥을 먹지 않았을 때 cnt +1
			if (!visited[c])cnt++;
			maximum = Math.max(maximum,cnt);
		}
	}
	

전략

• 단순하게 생각해서 N개의 초밥에 대해서 연속해서 먹는 K개 만큼 배열을 순회하면서 초밥의 종류 카운트

• 주의1. 끝의 초밥과 앞의 초밥은 이어진다

• 주의2. 연속해서 K개의 초밥을 먹을 때 쿠폰에 해당하는 초밥을 1개 더 준다

N개의 초밥에 대해서 K개씩 순회하기 때문에 O(NK)의 시간복잡도가 나온다

N <30000 , K<3000 이므로 최대 90000000회의 연산이고 CPU가 1초당 1억회의 연산이 가능하다면 아슬아슬하게 통과하는 코드