[Greedy] 1700번 - 멀티탭

[백준] 1700번 - 멀티탭

📝 나의 풀이

문제를 보고, 가장 오랫동안 사용되지 않을 페이지를 교체하는
OPT 교체 알고리즘이 떠올랐다.

그리고 3가지 경우의 수를 나누어 생각하면 된다.

1. 사용할 전기용품이 이미 멀티탭에 꽂혀 있는 경우 → pass
2. 빈자리가 있는 경우 → 빈자리 사용 → pass
3. 빈자리가 없는 경우 → 가장 나중에 사용하는 전기용품과 교체

빈자리가 없는 경우엔
현재 스케줄링 시점에서 가장 나중에 사용하는 전기용품이 교체 대상이 되도록 하면 된다.

tapIndex : 교체 대상 멀티탭의 위치
maxLater : 가장 늦게 사용되는 전기용품의 시점
tmp : maxLater를 구하기 위한 변수로 해당 전기용품이 다음으로 사용될 때까지의 거리를 나타낸다.

public static int exchange(int index) {
		int tapIndex = 0;
		int maxLater = -1;
		for(int i = 0; i < tap.length; i++) {
			int tmp = 0;
			for(int j = index; j < scheduler.length; j++) {
            	
                //멀티탭에 꽂혀있는 전자용품이 스케줄러에 존재하면 for 반복문 탈출
				if(scheduler[j] == tap[i]) break; 
                
                //tap[i]에 꽂혀있는 전기용품이 스케줄러의 다음 항목에 있을 때까지 tmp를 증가시킨다.
				tmp++; 
			}
			
            // 현재까지의 최대 tmp를 가진 것과 비교하여 더 큰 tmp를 가지는 경우 갱신
			if(tmp > maxLater) {
				tapIndex = i;
				maxLater = tmp;
			}
		}
		
		return tapIndex;
	}

👩🏻‍💻 최종 코드

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

public class 멀티탭스케줄링_1700 {
	
	static int[] tap;
	static int[] scheduler;

	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 K = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        tap = new int[N];
        scheduler = new int[K];
        for(int i = 0; i < K; i++) {
        	scheduler[i] = Integer.parseInt(st.nextToken());
        }
        
        int count = 0;
        for(int i = 0; i < K; i++) {
        	int tmp = scheduler[i];
        	boolean pass = false;
        	
        	for(int j = 0; j < N; j++) {
        		
        		if(tap[j] == tmp) { // 사용할 전기용품이 이미 꽂혀 있는 경우
        			pass = true;
        			break;
        		}
        		else if(tap[j] == 0) { // 빈자리가 있는 경우
        			tap[j] = tmp;
        			pass = true;
        			break;
        		}
        		
        	}
        	
        	if(!pass) { // 빈자리가 없는 경우
        		int index = exchange(i + 1);
        		tap[index] = tmp;
        		count++;
        	}
        }
        
        System.out.println(count);
        
        
	}
	
	public static int exchange(int index) {
		int tapIndex = 0;
		int maxLater = -1;
		for(int i = 0; i < tap.length; i++) {
			int tmp = 0;
			for(int j = index; j < scheduler.length; j++) {
				if(scheduler[j] == tap[i]) break;
				tmp++;
			}
			
			if(tmp > maxLater) {
				tapIndex = i;
				maxLater = tmp;
			}
		}
		
		return tapIndex;
	}
	

}