(Baekjoon) GreedyAlgorithm - (19) 멀티탭 스케줄링

https://www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링

 

초반에 내가 풀었던 코드이다.

package GreedyAlgorithm;

import java.util.Scanner;

public class _1700 {
    static int N;
    static int multi[];
    static int in[][];
    static int repeat=0;

    static boolean compare(int c,int t,int b){ 
        if(c == N) 
            return true;
        if(in[b][c] != multi[t]){
            return compare(c+1,t,b);
        }
        return false;
    }
    static void finder(int a,int b){
        int count=0;
        for (int i = a; i < multi.length; i++) {
            if(compare(0,i,b) == true){ 
                in[b][count] = multi[i];
                count++;
            }
            if (count == N){
                finder(i+1,b+1);
                break;
            }
        }
    }


    public static void main(String args[]){

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        int K = sc.nextInt();
        multi = new int[K];
        in = new int[(K/N)+1][N];
        for (int i = 0; i < K; i++) 
            multi[i] = sc.nextInt();
        finder(0,0);
        int sum=0;
        for (int i = 0; i < in.length-1; i++) {
            if(in[i+1][0] == 0) break;
            for (int j = 0; j < N; j++) {
                for (int j2 = 0; j2 < N; j2++) {
                    if(in[i][j] == in[i+1][j2]){
                        repeat++;
                    }
                }
            }
            
            int at=0;
            for (int j2 = 0; j2 < N; j2++) {
                if(in[i+1][j2] == 0){
                    at++;
                }        
            }    
            repeat = N - repeat -at;
            sum+=repeat;
            repeat=0;

        }
        System.out.println(sum);

        sc.close(); 
        

    }
}

3 20 4 1 2 3 4 가 있을경우에 같은 수를 제외하고 연속적인 수를 검색한후

 

1) 3 20 4

2) 1 2  3

3) 4

로 배열에 넣고 1 <-> 2번 비교 2 <-> 3번 비교하여서 틀린 부분만 더하는 방식이다.

 

나는 처음에 생각했을때 이러면 최솟값이 나오지 않을까 생각했지만 착오였다.

 

왜냐하면 다음과 같은 예외가 발생한다.

예를들어서 3 20 4 1 2 3 4 순서대로 진행을 할경우 내가 진행한 코드 할경우

 

3
3 20
3 20 4
3 1 4
3 1 2  
4   
: 3번

3
3 20
3 20 4
3 1  4
3 2  4
: 2번

 

나도 처음에는 위와 같은 경우를 고려했는데 예외 테스트를 너무 적게 했던것이 화근이 되었다.

그리고 코드가 너무 복잡했다. 재귀적으로 짜야했고 이상함을 느꼈지만 그래도 밀어붙혔다 ㅋㅋㅋ

그래서 처음에는 왜 틀린지도 이해가 안갔다. 이렇게 완벽하게 짯는데 틀렸다는게 ㅜㅜ

결론적으로는 생각한대로 코드는 잘만들었는데 생각이 틀렸었다.

 

결국은 다시 풀어야된다.

 

 

package GreedyAlgorithm;

import java.util.Scanner;

public class _1700 {
    static int N, K;
    static int multi[];
    static int in[];

    static boolean compare(int i) {
        for (int j = 0; j < N; j++)
            if (in[i] == multi[j])
                return true;
        return false;
    }

    static boolean use(int a, int i) {
        for (int j = 1; j <= 2 * (N - 1); j++) {
            if ((i + j) >= in.length)
                continue;
            if (multi[a] == in[i + j]) {
                // System.out.println("multi["+a+"] == in["+i+j+"]");
                return true;
            }
        }

        return false;
    }

    public static void main(String args[]){

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
        multi = new int[N]; // 멀티탭
        in = new int[K];
        int result=0;

        int count=0;
        int last = 0;

        for (int i = 0; i < K; i++)
            in[i] = sc.nextInt();
 

        for (int i = 0; i < K; i++) {
            if (compare(i) == false) {
                multi[count] = in[i];
                count++;
                last = i;
                if(count == N) break;
            }
        }

        for (int i = 0; i < multi.length; i++) {
            System.out.print(multi[i]+"");
        }
        
        
        

        for (int i = last; i < K; i++) {
            if(compare(i)==false){
                for(int j = 0; j < N; j++) {
                    if(j==N-1){
                        result++;
                        multi[j] = in[i];
                        System.out.println("out");
                        System.out.println("result : "+result + " multi : " +multi[0]+""+multi[1]+""+multi[2]); 
                        break;
                    } 
                    if(use(j,i)==false){ // j 멀티탭 i 들어올거
                        result++;
                        multi[j] = in[i];
                        System.out.println("result : "+result + " multi : " +multi[0]+""+multi[1]+""+multi[2]); 
                        break;
                    } 
                }
                 
            }
             

        }

        System.out.println(result);

        
        sc.close();

        

    }
}

 

 

위와같이 멀티탭 갯수에 따라서 2*(n-1)의 갯수만큼 뒤에까지 미래를 예측해보는것으로 풀어봤다.

초반에 테스트케이스로 실험해보았을때 맞는것 같았지만 결국 또 틀렸다.

답에 거의 근접했지만 한개이상 또는 한개 이하의 차이로 계속 틀렸다.

계산해보니까 위와 같은 과정으로 나온 결과로 풀경우 

 

어쩔땐 답이 나오고 어쩔땐 답이 안나오는 경우가 있었다.

위처럼 풀면은 답이 있는경우도 있지만 답이 아닌경우도 있다는말이다.

 

예를들어서

3 20
1 2 3 4 4 3 5 8 9 19 20 1 2 3 20 4 1 2 3 4

를 넣을경우 위와 같이 진행된다. 그런데

result 7부터 직접풀어보면 

20 2 3 -> 1 2 3 -> 1 2 20 -> 1 2 4 -> 1 3 4  ==>  4번 이지만

위의 결과는 5번이나 풀이한다.

 

이말인즉슨 푸는방법에서부터 이미 틀렸다는것이다.

 

아무리 생각해봐도답이 나오지않아서 결국 해법을 찾아봤다.

 

너무허무했다.... 그냥 노가다로 다 검색하는거였다...

 

이거 그냥 노가다가 다 검색할꺼면 무엇하러 그리디 알고리즘에 넣었는지 의문이다...

 

무슨 비법이 있는것이 아니다...

 

multi탭에 꽂혀있는것중 가장 마지막에 등장하거나 등장안하는거에다가 삽입하면된다.

 

초반에 풀때 고작 이런 문제이겠어? 하고 넘겼던 그 생각이 정답이라니 정말 너무 허무해서 허탈하다.

 

너무 허무 했지만

그래도 6일동안 내내 고민한 의미는 문제탐구과정을 발전시킨거라 긍정적으로 생각해본다. ㅠㅠㅠ

 

 

알고리즘은 다시 말해서

 

1. 멀티탭이 비어있는가?

2. 이미 멀티탭에 같은수가 있는가?

3. 둘다 아니라면 가장 늦게 나오는 수가 무엇인지 파악후 그 수에다가 집어넣기..

 

이건 그리디 알고리즘이라기 보다는 노가다 알고리즘 같다. 이게 왜 탐욕알고리즘인지 모르겠다.

무엇을 탐욕한것인가 단순노동을 탐욕했나?

 

package GreedyAlgorithm;

import java.util.Scanner;

public class _1700 {
    static int N, K;
    static int multi[];
    static int in[];
    static boolean m[];
    static int result = 0;

    static boolean compare(int i) { // 멀티탭안에 들어갈수가 이미 있는가
        for (int j = 0; j < N; j++)
            if (in[i] == multi[j])
                return true;
        return false;
    }

    static int empty(int j) {
        for (int i = 0; i < N; i++) {
            if (m[i] == false) { // 비어있다면
                return i;
            }
        }
        return -1; // 비어있는곳이 없다면
    }

    static int future(int i) {
        int count = 0;
        int max = 0;
        int multi_max = 0;
        for (int j = 0; j < N; j++) {
            for (int j2 = i + 1; j2 < K; j2++) {
                if (multi[j] == in[j2])
                    break;

                count++;
            }
            if (max < count) {
                max = count;
                multi_max = j;
            }
            // System.out.println("multi["+j+"] = "+multi_max + " count = "+ count);

            count = 0;
        }
        return multi_max;

    }

    public static void main(String args[]) {

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
        multi = new int[N]; // 멀티탭
        m = new boolean[N];
        in = new int[K];

        for (int i = 0; i < K; i++)
            in[i] = sc.nextInt();
        for (int i = 0; i < N; i++)
            m[i] = false;

        // 같은수가 있는가
        // 비어있는가
        // 둘다 아니라면 후에 가장 뒤에 나오는것을 먼저 뽑기

        for (int i = 0; i < K; i++) {
            if (compare(i) == true) { // 같은수가 있다면
                continue;
            } else { // 같은수가 없다면
                int e;
                if ((e = empty(i)) != -1) { // 빈공간있다면
                    multi[e] = in[i];
                    m[e] = true;
                } else { // 빈공간없다면
                    multi[future(i)] = in[i]; // 가장 뒤에 나오는것을 먼저 뽑기
                    result++;

                }
            }
            // for (int j = 0; j < multi.length; j++) {
            // System.out.print(multi[j] + " ");
            // }
            // System.out.println();
        }

        System.out.println(result);

    }
}

 

 

 

 

 

백준문제풀이Github : 

https://github.com/sdk0213/baekjoon-study

sdk0213/baekjoon-study