[백준] 1700. 멀티탭 스케줄링 (JAVA)

🔌 멀티탭 스케줄링

 

이 문제를 보자마자 운영체제가 생각난다면 당신은 컴공 !

그치만 무슨 스케줄링 기법인지 그 이름은 기억나지 않는다면 찐 전공생 ! 

 

---

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

 

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

---

🔑 IDEA

운영체제의 page replacement 전략 중 optimal page replacement algorithm 이 있다.

Belady's algorithm으로도 알려진 이 알고리즘은,

앞으로 가장 오랫동안 사용되지 않을 페이지를 victim으로 정한다.

 

그러나 현실세계에서는 미래를 예측할 수 없기 때문에

프로세스가 앞으로 어떤 페이지를 사용할지에 대해서는 운영체제가 미리 알 수 없다.

따라서 이 방법은 현실세계에서는 구현이 불가능하지만, 

이 문제에서는 사용 순서가 미리 정해져있기 때문에 이 전략을 이용하여 해결하도록 한다.   

 

💡  나의 풀이

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

class Main {
	static int N;
	static int K;
	static int[] sequence;
	static List<Integer> inUse = new ArrayList<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		sequence = new int[K];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<K ;i++) {
			sequence[i] = Integer.parseInt(st.nextToken());
		}
		System.out.println(getOptimal());
	}

	private static int getOptimal() {
		int cnt = 0;
		for(int i=0; i<K; i++) {
			int cur = sequence[i];
			if(inUse.contains(cur)) continue;
			if(inUse.size() == N) {
				int targetIdx = -1;
				List<Integer> inQueue = new ArrayList<>();
				for(int j=i+1; j<K; j++) {
					int next = sequence[j];
					if(inQueue.size() == N) break;
					if(!inUse.contains(next)) continue;
					if(!inQueue.contains(next))
						inQueue.add(next);
				}
				if(inQueue.size() == N) {
					int last = inQueue.get(inQueue.size()-1);
					targetIdx = inUse.indexOf(last);
				}
				else {
					for(int j=0; j<N; j++) {
						if(inQueue.contains(inUse.get(j))) continue;
						targetIdx = j;
						break;
					}
				}
				cnt++;
				inUse.remove(targetIdx);
			}
			inUse.add(cur);
		}
		return cnt;
	}
}

 

 

---

 

1700번: 멀티탭 스케줄링