백준 1700 멀티탭 스케줄링 Java

그리디 문제인 멀티탭 스케줄링이다. 정답률은 25퍼센트로 꽤 낮다.

나도 저 낮은 정답률에 상당 부분 기여를 했다..

 

문제는 간단하다.

N개의 멀티탭 구멍을 M개의 기계를 쓸 때

플러그를 빼는 최소의 횟수를 출력하면 된다.

 

그리디로 푸는 방법의 핵심은

가장 나중에 쓰는 용품을 빼는 것이다.

 

가장 나중에 쓰는 용품을 뺀다고 해서

가장 마지막에 쓰는 용품을 빼는 것이 아니다.

3 8

1 2 3 1 2 3 1 2이 주어졌다면

1 2 3으로 멀티탭이 가득 찼을 때

꽂혀 있는 것들 중 가장 마지막에 쓰는 2를 빼는 것이 아니라

가장 나중에 출현하는 3을 빼는 것이다.

 

풀이과정을 정리해보면

1. 멀티탭이 비어있으면 꽂는다.

2. 멀티탭에 이미 꽂혀있으면 그냥 넘긴다.

3. 멀티탭에 꽂힌 물건 중 다시는 사용하지 않는 것이 있다면 그것을 뺀다.

4. 다 사용하는 것들이라면 제일 나중에 출현하는 것을 뺀다.

 

3, 4번의 과정에서 정답에 +1을 해주면 그것이 최소 횟수가 된다.

 

가장 마지막에 쓰는 용품을 빼는 것으로 이해하고 코드를 짜 놓고

왜 틀리지를 연발하며 질문까지 올려서 겨우 해결했다..

가장 나중에 출현하는 용품을 뺀다는 그리디적인 생각도 떠올리는 사람들이 신기하다.

 

코드는 실력이 부족한 내가 작성한 거라 조금 더럽다.???

나는 ArrayList를 멀티탭으로 사용했지만 그냥 1차원 배열을 사용한다면

삭제하는 과정에서 더 효율적일 것이다.

 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Q1700 {
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int [] a = new int[m];
        int [] how = new int[101];//몇번 출현하는지 
        for(int i=0; i<m; i++) {
            a[i] = scan.nextInt();
            how[a[i]]++;
        }
        int ans = 0;
        List<Integer>list = new ArrayList<>();
        for(int i=0; i<m; i++) {
            how[a[i]]--; //출현 횟수 감소
            if(list.contains(a[i]))    continue; //이미 꽂혀있으면 continue
            if(list.size()>=n) { //빼야될 때 
                ans++;
                boolean ok = false; //삭제 여부
                for(int j=0; j<list.size(); j++) { //앞으로 사용하지 않는 수 찾기
                    if(how[list.get(j)] <= 0) { //출현 횟수가 0보다 작으면 앞으로 안나옴
                        list.remove(new Integer(list.get(j)));
                        ok = true; 
                        break;
                    }
                }
                if(!ok) { //앞으로 사용하지 않는 수가 없을 시 가장 나중에 출현하는 수를 지운다
                    boolean [] b = new boolean[n]; //나중에 지워지는 수를 체크할 배열
                    int check = n;
                    loop:{ 
                        for(int j=i+1; j < m; j++) { 
                            for(int k=0; k<n; k++) {
                                if(list.get(k) == a[j] && !b[k]) {
                                    b[k] = true;
                                    check --;
                                    if(check == 0) { //마지막으로 지워졌으면 지운다
                                        list.remove(new Integer(a[j]));
                                        break loop;
                                    }
                                    break;
                                }
                            }
                        }
                    }
                }
            }
            list.add(a[i]);
        }
        System.out.println(ans);
    }
}