백준 23305 - 수강변경 (자바 - 그리디)

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

23305번: 수강변경

 

* 문제 요약

마일리지 수강신청 제도를 채택하고 있는 연세대는 수강 변경에서도 혁신적인 시스템을 도입하려고 한다.

특정 연도를 기점으로 수강 변경 기간동안에는 "수업 교환" 이 허용된다.

수업 교환은 두 사람이 서로 다른 수업을 교환하는 것으로, 두 사람 모두의 동의가 있어야만 수업 교환이 가능하다.

이때, 삼자 교환은 불가능하지만 두 사람이 수업을 교환하고, 교환한 사람 중 다른 사람이 그 수업을 또 다른 사람과 교환하는 것은 가능하다.

 

수강 변경이 시작되었다. 학생들이 수강하고 싶은 수업이 1개씩 주어지고, 교환하고 싶은 수업이 1개씩 주어질 때, 수업 교환이 끝나고 본인이 원하는 수업을 수강하지 못하는 인원의 최솟값을 구해보자.

 

* 입력

첫 줄에 학생의 수 N 이 주어진다. (1 <= N <= 1,000,000)

두 번째 줄에 정수 A1, A2, ... AN 이 주어진다. 여기서 Ai 는 i 번 학생이 현재 신청한 수업이며, 동시에 교환하고 싶은 수업의 번호를 의미한다. (1 <= Ai <= 1,000,000)

세 번째 줄에 정수 B1, B2, ... BN 이 주어진다. 여기서 Bi 는  i 번 학생이 교환을 통해 수강하고 싶은 수업의 번호를 의미한다.

모든 입력은 공백으로 구분되어 주어진다.

 

* 출력

모든 학생들이 최적의 방법을 사용해서 수업 교환을 완료했을 때, 원하는 수업을 수강하지 못하는 학생들의 수를 출력한다.

 

* 예시

 

* 해결 과정

처음엔 이중반복을 활용해서 시간초과 판정을 받았었다.

교환을 원하는 강의와 수강하길 원하는 강의를 데이터로 가지는 객체를 만들고 이를 배열로 만들어 순차탐색을 진행하되, 이중 반복으로 현재 바깥 반복문에서 탐색중인 객체에서 수강하기를 원하는 강의를 신청한 객체가 배열 내부에 존재하는지 확인해가며, 배열 내부에 수강하기를 원하는 강의를 신청한 객체가 있을 경우 서로 교환해주는 방식으로 코드를 작성했었다.

여기서 수강하기를 원하는 강의를 신청한 다른 객체가 이미 자신이 원하는 강의를 신청한 상태인 경우 교환이 되지 않도록 해줬다.

 

위와 같은 방식으로 코드를 작성해서 제출했더니 시작부터 시간초과 판정을 받았다.

 

* 시간초과 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int count = Integer.parseInt(br.readLine());

        SignUp[] signUps = new SignUp[count];
        String[] input1 = br.readLine().split(" ");
        String[] input2 = br.readLine().split(" ");
        for (int i = 0; i < count; i++) {
            signUps[i] = new SignUp(Integer.parseInt(input1[i]), Integer.parseInt(input2[i]));
        }

        int result = count;
        for (int i = 0; i < count; i++) {
            SignUp signUp = signUps[i];

            if (signUp.change == signUp.want) {
                result--;
            } else {
                for (int j = 0; j < count; j++) {
                    if (i != j) {
                        if (signUps[j].change == signUp.want && signUps[j].change != signUps[j].want) {
                            int temp = signUp.change;
                            signUp.change = signUps[j].change;
                            signUps[j].change = temp;
                            signUps[i] = signUp;
                            result--;
                            break;
                        }
                    }
                }
            }
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

class SignUp {
    int change;
    int want;

    public SignUp(int change, int want) {
        this.change = change;
        this.want = want;
    }
}

 

코드를 제출하기 전 부터 시간초과가 나올거라는 예감이 들기는 했다.

학생들의 숫자가 최대 1,000,000 까지 갈 수 있는데 이렇게 되면 이중반복을 수행했을 때 최악의 경우 1,000,000 * 1,000,000 회 만큼이나 탐색을 하게 될 수 있기 때문이다.

즉, 최악의 경우 시간복잡도가 O(n^2) 이 되버린다.

 

시간복잡도를 줄이기 위해 그리디 알고리즘 문제라는 것에 착안하여 다른 방식을 생각해보았다.

그 결과 그냥 좀 더 간단하게 수강하기를 원하는 강의가 신청한 강의 내부에서 몇개나 되는지 확인해보자는 생각이 들었다.

결국 원하는 강의를 못 듣는인원을 최소화 시키려면 다른 학생들이 원하는 강의를 신청한 학생들이 그만큼 많아야 한다.

그리고 교환횟수가 한정되어 있는건 아니기 때문에 필요하다면 얼마든지 교환도 가능하다.

어차피 교환횟수는 자유이고, 한 번 교환하면 다시는 교환불가라는 룰도 없기 때문에 그냥 원하는 강의가 있으면 있는대로 다 배정해주는 방식으로 풀면된다.

전체의 최적해가 아니라 매 순간마다의 상황에 따라서 최적의 판단을 하면 되므로 한번의 교환으로 다른 학생이 원하는 강의를 못 듣는 경우까지 생각해줄 필요는 없다.

 

로직은 아래와 같은 방식으로 작성했다.

해시맵으로 신청한 강의를 저장해준다. 키값은 신청한 강의 숫자, 밸류값은 해당 강의가 신청된 갯수이다.

그 다음엔 원하는 강의를 입력받아서 처음부터 순차탐색을 진행하며 해시맵에 있는지만 봐준다.

뒷 사람이 똑같이 그 강의를 원하든 아니든 상관없이 그 순간순간에 원하는 강의가 신청한 강의 해시맵에 있는지만 확인하고 처리해준다.

 

만약 원하는 강의가 신청한 강의 해시맵에 존재하는 경우 해당 키 값의 밸류를 1 감소시키고, 만약 밸류가 0 이 되면 해당 강의 키값을 해시맵에서 삭제해준다.

만약 원하는 강의가 신청한 강의 해시맵에 존재하지 않는 경우 정답 변수값을 1 증가시켜준다.

순차 탐색이 끝나면 정답 변수 result 를 출력시켜준다.

 

이렇게 하면 해시맵에 데이터를 추가해주는것 까지 시간복잡도로 고려해서 계산해도 O(2n) 정도 밖에 되지 않는다.

 

코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int count = Integer.parseInt(br.readLine());

        String[] input = br.readLine().split(" ");
        HashMap<Integer, Integer> changeMap = new HashMap<>();

        for (int i = 0; i < input.length; i++) {
            int change = Integer.parseInt(input[i]);

            if (changeMap.containsKey(change)) {
                changeMap.put(change, changeMap.get(change) + 1);
            } else {
                changeMap.put(change, 1);
            }
        }

        int result = 0;

        input = br.readLine().split(" ");
        for (int i = 0; i < count; i++) {
            int change = Integer.parseInt(input[i]);

            if (changeMap.containsKey(change)) {
                int value = changeMap.get(change);
                value -= 1;
                if (value > 0) {
                    changeMap.put(change, value);
                } else {
                    changeMap.remove(change);
                }
            } else {
                result++;
            }
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

그리고 아래는 내가 작성한 코드보다 처리시간이 좀 더 빠르고 메모리도 덜 사용한 다른 통과자의 코드이다.

해시맵이 아니라 배열을 사용한 점이 매우 인상적이었다.

처음 배열을 만들 때 배열의 크기를 1,000,000 으로 잡아준것을 볼 수 있는데, 이렇게 하면 저 1,000,000 이라는 숫자의 크기만 보고 메모리를 너무 많이 먹게 되지 않을까 싶어 해시맵을 곧 잘 써왔는데 오히려 해시맵보다 메모리를 많이 먹지 않는 것을 보고 꽤 놀랐던것 같다.

해시맵을 활용하면 내부의 해싱함수로 각 키값의 주소를 지정해줄 때, 이 주소값이 서로 충돌하는 것을 방지하기 위해 공간을 좀 더 확보해서 사용한다는건 알고 있었는데, 이때 확보하게 되는 메모리 공간이 생각보다 훨씬 많은 것 같다.

 

* 배열을 사용한 사람의 코드

import java.io.*;
import java.util.*;
import static java.lang.Integer.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int studentN = parseInt(br.readLine());
        int[] give = new int[1_000_001];

        String[] inputs = br.readLine().split(" ");
        for(int i = 0; i < studentN; i++)
            give[parseInt(inputs[i])]++;

        int counter = studentN;
        inputs = br.readLine().split(" ");
        for(int i = 0; i < studentN; i++){
            int target = parseInt(inputs[i]);
            if(give[target] > 0){
                give[target]--;
                counter--;
            }
        }
        
        bw.write(String.valueOf(counter));
        bw.flush();
        bw.close();
    }
}

 

수강을 원하는 강의의 데이터를 입력받았을 때 따로 정렬과 같은 일을 수행하지 않고 입력받은 순서 그대로 현재 신청한 강의 중에 해당 강의가 존재하는지만 확인하고 그 수업과 교환을 해주고 있다.

뒤의 입력이 어떻게 될지는 고려하지 않은 체 교환할 수 있는 경우 교환해주는 식으로 매 단계의 상황마다 최적의 로직을 수행하는 그리디 알고리즘 문제라고 할 수 있다.