JAVA - 백준 알고리즘 - 1700 멀티탭 스케줄링

이 문제는 그리디 알고리즘을 이용해 푸는 문제이다.

 

처음 생각하기로는 앞으로 꽂아야 할 용품의 수가 많으면 오래 남아 있도록 해야 정답이 나올 것이라 생각했다.

 

하지만 그렇게 풀이를 작성했더니 몇몇 테스트 케이스를 통과하지 못했다.

 

다시 생각한 결과 멀티탭에 꽂혀 있는 용품들 중 가장 나중에 사용될 것을 먼저 뽑도록 바꾸었다.

 

너무 오랫동안 문제를 풀고 추가하다보니 코드가 많이 복잡해졌다.

 

최적화를 하면 코드를 많이 줄일수 있을 거 같지만 지금 당장은 이 코드를 수정하고 싶은 생각이 들지 않는다.

 

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

public class Main {

	static int N, K, count, min, change, temp ,temp1;
	static int[] arr, con, number, last;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String str = br.readLine();

		StringTokenizer st = new StringTokenizer(str, " ");

		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		str = br.readLine();
		st = new StringTokenizer(str, " ");
		arr = new int[K];
		con = new int[N];
		number = new int[K + 1];
		last = new int[K+1];
		min = 0;
		temp1 = N;
		change = 0;
		for (int i = 0; K > i; ++i) {
			arr[i] = Integer.parseInt(st.nextToken());
			number[arr[i]]++;
		}
		
		a:
		for (int i = 0; K > i; ++i) {	// 콘센트에서 빈 곳에 꼽기 + 이미 있으면 넘기기
			for (int j = 0; N > j; ++j) {
				if(con[N-1]!=0) break a;
				if (con[j] == 0) {
					con[j] = arr[i];
					number[arr[i]]--;
					break;
				} else if(con[j] == arr[i]) {
					number[arr[i]]--;
					temp1++;
					break;
				}
			}
		}
		
		for (int i = temp1 ; K > i; ++i) {
			for (int j = 0; N > j; ++j) {
				if (con[j] == arr[i]) {
					temp = 0;
					min = 0;
					for( int q = 0 ; K >= q ; ++q) {
						last[q] = 0;
					}
					number[arr[i]]--;
					break;
				} else {
					++temp;
				}
			}
			if (temp > 0) {
				getlast(i);
				for (int j = 0; N > j; ++j) {
					if (number[con[j]] == 0) {
						change = j;
						break;
					} else {
						if( min <= last[con[j]] ) {
							min = last[con[j]];
							change = j;
						}
						
					}
				}

				con[change] = arr[i];
				count++;
				number[arr[i]]--;
				min = 0;
				
				for( int q = 0 ; K >= q ; ++q) {
					last[q] = 0;
				}

			}
		}
		System.out.print(count);
	}
	
	public static void getlast(int a) {
		
		for(int i=a; K>i;++i) {
			if(last[arr[i]] == 0) {
			last[arr[i]] = i;
			}
		}
		
	}

}