[백준] 알고리즘 분류(그리디 알고리즘,JAVA)1700번, 멀티탭 스케줄링

문제 링크

1700번: 멀티탭 스케줄링

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 멀티탭에는 N개의 플러그를 동시에 꽂을 수 있습니다.

2. K번 전기 용품들을 순서대로 사용할 때 플러그를 빼는 최소 횟수를 결과로 출력합니다.

3. 전기용품 이름은 K번 이하의 자연수로 이루어집니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 전기 용품 순서를 이용하여 OPT(페이지 교체 알고리즘)를 진행합니다.

 

3. 페이지가 교체된 횟수를 결과로 출력합니다. 

 

 

OPT(Optimal)

 

페이지 교체를 진행할 때, 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 방법입니다.

 

예를 들어

 

페이지 사용 순서 : 3 → 2 → 4 → 1 → 3 → 2

 

 

3

2

4

 

페이지 1를 사용하기 위해 교체할 때, 앞으로 오랫동안 사용하지 않을 페이지 탐색!

페이지 2 : 3(1 → 3 → 2)

페이지 3:  2(1 → 3)

페이지 4 : X(이후 사용하지 않음)

 

페이지 4 ⇒ 페이지 1 교체 진행!

 

3

2

1

 

이 문제에서는 전기 용품들을 각 페이지로 생각하고 진행하시면 됩니다.

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

N : 2

K : 7

 

전기용품 사용 순서

 

2

3

2

3

1

2

7

 

2. 전기 용품 순서를 이용하여 OPT(페이지 교체 알고리즘)를 진행합니다.

 

전기 용품 순서 정리.

 

1	2	3	4	5	6	7
{ 4 }	{0, 2, 5}	{1, 3}				{ 6 }

 

전기용품 멀티탭에 꽂기 시작!

 

2 → 3 → 2 → 3 → 1 → 2 → 7

 

2

3

 

현재 전기 용품

 

1	2	3	4	5	6	7
{ 4 }	{0, 2, 5}	{1, 3}				{ 6 }

 

2 → 3 → 2 → 3 → 1 → 2 → 7

멀티탭 모두 꽂혀있기 때문에 교체가 발생!

전기용품 2 : 2(1 → 2 → 7)

전기용품 3 : X(더 이상 사용하지 않음)

전기용품 3 ⇒ 전기용품 1 교체 진행!

 

2

1

 

현재 전기 용품

 

1	2	3	4	5	6	7
{ 4 }	{0, 2, 5}	{1, 3}				{ 6 }

 

2 → 3 → 2 → 3 → 1 → 2 → 7

이미 멀티탭이 꽂혀있기 때문에 교체발생 X

 

2

1

 

현재 전기 용품

 

1	2	3	4	5	6	7
{ 4 }	{0, 2, 5}	{1, 3}				{ 6 }

 

2 → 3 → 2 → 3 → 1 → 2 → 7

멀티탭 모두 꽂혀있기 때문에 교체가 발생!

전기용품 2 : X(더 이상 사용하지 않음)

전기용품 1 : X(더 이상 사용하지 않음)

전기용품 2 ⇒ 전기용품 7 교체 진행!

 

7

1

 

현재 전기 용품

 

1	2	3	4	5	6	7
{ 4 }	{0, 2, 5}	{1, 3}				{ 6 }

 

 

3. 페이지가 교체된 횟수를 결과로 출력합니다. 

전기용품 3 ⇒ 전기용품 1 교체 진행!

전기용품 2 ⇒ 전기용품 7 교체 진행!

 

2를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 전기용품의 정보를 띄어쓰기 기준 나누었습니다.
• 멀티탭에 N개의 전기용품 플러그가 연결되도록 합니다.
• 플러그를 교체할 때는 다음에 사용되지 않는 전기용품이 존재하면 항상 우선적으로 교체합니다.
• 플러그를 교체할 때는 다음에 사용되는 거리에 따라 교체하도록 하였습니다.
• 플러그를 교체한 횟수를 결과로 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

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

public class Main{

    static int N,K, answer = 0;
    //전기 용품 순서 저장 리스트
    static ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    //멀티탭 관련 리스트
    static ArrayList<Integer> cur = new ArrayList<>();
    static int[] num, index;	//입력값 및 현재 전기 용품 순서 Index 저장 배열
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        num = new int[K];
        index = new int[K+1];
        st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<=K;i++){
            list.add(new ArrayList<>());
            index[i] = -1;	//index -1로 초기화
        }
        //입력값 및 순서 저장
        for(int i=0;i<K;i++){
            num[i] = Integer.parseInt(st.nextToken());
            list.get(num[i]).add(i);
        }
        //멀티탭 비어있는 공간 없을 때까지 모두 꽂기
        int id = 0;
        while (id < K && cur.size() != N) {
            index[num[id]]++;
            if (!cur.contains(num[id]))
                cur.add(num[id]);
            id++;
        }
        //전기용품 순서대로 탐색
        for(int i=id;i<K;i++){
            index[num[i]]++;
            if(cur.contains(num[i]))	//현재 멀티탭에 존재하는 전기용품일 때
                continue;

            boolean check = false;
            int max = -1;
            int tempIndex = -1;
            //멀티탭에 존재하지 않는 전기용품일 때 멀티탭 탐색
            for(int j=0;j<N;j++){
                int curNum = cur.get(j);
                //더이상 사용하지 않는 전기용품일 때
                if(list.get(curNum).size() <= index[curNum]+1){
                    check = true;
                    cur.set(j, num[i]);	//플러그 교체
                    break;
                }else{	//다음에도 사용하는 전기용품일 때
                    //다음 순서까지의 거리
                    int temp = list.get(curNum).get(index[curNum]+1) - i;
                    //거리 최대값 구하기
                    if(max < temp){
                        tempIndex = j;
                        max = temp;
                    }
                }
            }
            //거리 최대값인 전기용품 변경
            if(!check)
                cur.set(tempIndex, num[i]);
            answer++;	//교체 횟수 증가
        }
        bw.write(answer + "");	//교체 횟수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}