백준 10774 - 저지 (자바 - 그리디)

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

10774번: 저지

 

* 문제 요약

학교 대표팀은 1 부터 번호가 매겨진 저지를 학생 선수들에게 배분하고자 한다.

저지의 사이즈는 S, M, L 중 하나이다.

각각의 선수들은 구체적인 저지의 번호와 선호하는 사이즈를 요구했다.

선수들은 만약 자신이 원했던 번호가 아니거나, 선호하는 사이즈보다 작은 사이즈의 옷을 받으면 불만이 생길것이다.

그들을 만족시키기 위해서는 요구하는 번호가 맞고 사이즈는 같거나 그 이상이어야 한다.

두 명의 학생들이 같은 저지를 받을 수는 없다.

조건을 만족하는 최대 학생 수를 구하는 프로그램을 작성하라.

 

* 입력

첫번째 줄은 저지의 수인 J 가 주어진다.

두번째 줄은 선수들의 수인 A 가 주어진다.

다음 J 줄에는 등번호 j 인 저지의 사이즈가 주어진다.(1 <= j <= J)

마지막 A 줄에는 선수들이 요구하는 사이즈와 번호가 입력된다.

 

테스트케이스의 50% 는 1 <= J <= 10^3, 1 <= A <= 10^3 를 만족하고,

나머지 50% 는 1 <= J <= 10^6, 1 <= A <= 10^6 를 만족한다.

 

* 출력

만족할 수 있는 최대의 선수의 수를 출력한다.

 

* 예시 

 

* 해결 과정

처음 풀 땐 해시맵까지 써 가며 복잡하게 풀었지만, 풀었던 그리디 알고리즘 문제를 하나하나 리뷰하며 그리디 알고리즘 풀이 노하우가 쌓인 지금은 코드 길이, 처리 시간, 사용된 메모리 크기 모두 간소화 시키며 다시 푸는데 성공한 문제이다.

 

가지고 있는 저지에 적혀있는 등번호는 배열의 인덱스로 처리해준다.

학생들이 가지고 있는 저지의 숫자보다 더 큰 값의 등번호를 요구할 수도 있기 때문에 저지 배열의 크기가 학생들이 원하는 등번호 숫자보다 더 큰지부터 확인한다.

 

처음엔 최대한 많은 학생들이 만족하는 경우를 구해야 했기에 반드시 학생들이 요구하는 사이즈를 기준으로 오름차순을 해서 요구하는 사이즈가 작은 학생들 먼저 저지를 나눠주는 방식으로 풀었었다.

문제 풀이 이후 다른 사람들의 코드를 확인해보니, 정렬을 해주지 않고 학생들의 입력순서 그대로 처리를 해주는 것을 확인할 수 있었다.

뒤의 일 따위 생각하지 않고 현재 상황 기준으로만 판단하는 그리디 알고리즘 방식의 풀이법 그 자체였다.

 

그를 보고 나 역시 학생들의 요구 사이즈 별로 정렬을 해주지 않고 입력받은 순서 그대로 처리를 해줬더니 오히려 코드 길이, 처리 시간, 사용된 메모리를 크게 줄이면서 통과 판정을 받을 수 있었다.

요구 사이즈 별로 정렬을 할 필요가 없어지니 기존에 정렬을 위해 만들었던 Student 객체가 필요 없어졌다.

 

기존에 정렬을 활용할 때는 Student 객체를 만들고 그 안에 size (요구 사이즈 - char), number (요구 등번호 - int) 변수를 만든 다음, size 기준으로 편하게 정렬하기 위해 Comparable 인터페이스를 구현시키면서 compareTo 메소드를 오버라이드해 정렬을 위한 로직을 직접 작성해주었었다.

정렬을 사용할 필요가 없어지면 위와 같이 객체를 만들어서 사용할 필요 또한 없어지기 때문에 객체를 만들기 위해 작성했던 class 코드와 해당 객체에 데이터를 적재해주는 코드를 삭제해주었고,

그와 동시에 본래 작성했었던 Arrays.sort() 메소드 또한 제거하니 코드 길이가 많이 줄어든 것은 물론 처리 시간, 사용된 메모리 또한 많이 줄일 수 있었다.

 

반복문 내부 로직은 간단하다. 그냥 학생들이 요구하는 등번호에 해당 하는 인덱스가 저지 배열에 존재할 경우, 사이즈를 비교해서 학생이 요구하는 사이즈보다 크거나 같으면 정답변수 result 를 1 늘리고, 그렇지 않다면 아무런 처리도 해주지 않고 넘어가면 된다.

다만 주의할 점은 사이즈를 비교할 때 S,M,L 알파벳이 사전순으로 L (76) -> M (77) -> S (83) 이기 때문에 사이즈의 크기 순서가 정반대가 되어버린다.

그렇기 때문에 각 값을 Z 로부터 뺄셈을 수행하며 아스키 코드 값을 반대로 역전시켜 주어야 한다.

이러한 연산이 귀찮으면 처음에 저지 사이즈를 입력받을 때 각 사이즈 별로 숫자를 지정해서 저장해준 다음, 그에 따라 조건문을 처리해주면 된다.

- 예시 : S -> 0 으로 지정, M -> 1 로 지정, L -> 2 로 지정

 

* 코드

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 jerseyCount = Integer.parseInt(br.readLine());
        int studentCount = Integer.parseInt(br.readLine());
        char[] jerseyArray = new char[jerseyCount + 1];

        jerseyArray[0] = 'Z';
        for (int i = 1; i < jerseyArray.length; i++) {
            jerseyArray[i] = br.readLine().charAt(0);
        }

        int result = 0;
        for (int i = 0; i < studentCount; i++) {
            String[] input = br.readLine().split(" ");
            char size = input[0].charAt(0);
            int number = Integer.parseInt(input[1]);

            if (number <= jerseyArray.length - 1) {
                if ('Z' - jerseyArray[number] >= 'Z' - size) {
                    result++;
                    jerseyArray[number] = 'Z';
                }
            }
        }

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

 

학생들의 입력 순서 그대로 저지를 나눠줄 수 있는지 없는지만 판단했다.

뒤에 나올 입력은 상관없이 현재 입력 상태를 기준으로 최적의 판단만을 하고 있기에 전체적으로 봤을 때 반드시 최적의 해에 가깝다고 보장할 수 없다.

그렇기 때문에 그리디 알고리즘 문제라고 볼 수 있다.