IM

작지만 단단하게

Greedy기출문제 풀이

씨름 선수

  • 설명 : 현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습니다. 현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다. 현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다.

“A라는 지원자를 다른 모든 지원자와 일대일 비교해서 키와 몸무게 모두 A지원자 보다 높은(크고, 무겁다) 지원자가 존재하면 A지원자는 탈락하고, 그렇지 않으면 선발된다.”

N명의 지원자가 주어지면 위의 선발원칙으로 최대 몇 명의 선수를 선발할 수 있는지 알아내는 프로그램을 작성하세요.

  • 입력 : 첫째 줄에 지원자의 수 N(5<=N<=30,000)이 주어집니다. 두 번째 줄부터 N명의 흰돌 능력치와 검은돌 능력치 정보가 차례로 주어집니다. 각 선수의 흰돌능력치가 모두 다르고, 검은돌 능력치도 모두 다릅니다. 능력치 값은 1,000,000이하의 자연수입니다. 출력설명 첫째 줄에 씨름 선수로 뽑히는 최대 인원을 출력하세요.

  • 출력 : 첫째 줄에 바둑 선수로 뽑히는 최대 인원을 출력하세요.

  • 풀이 답안1 (개선전)

import java.util.*;

class People {
    int h;
    int w;
    public People(int h, int w) {
        this.h = h;
        this.w = w;
    }
}

public class Main {

    static List<People> list = new ArrayList<>();
    static int num;
    static int[][] grid;
    public void solution (int n) {
        if(n==num) {
            int answer = num;
            for(int i=0; i<num; i++){
                for(int j=0; j<num; j++){
                    if(grid[i][j]==1) {
                        answer--;
                        break;
                    }
                }
            }
            System.out.println(answer);
        } else {
            for(int i=0; i<num; i++){
                if(list.get(n).w<list.get(i).w && list.get(n).h<list.get(i).h) {
                    grid[n][i] = 1;
                    break;
                }
            }
            solution(n+1);
        }
    }

    public static void main(String[] args) {

        Main main = new Main();
        Scanner scan = new Scanner(System.in);
        num = scan.nextInt();
        for(int i=0; i<num; i++){
            int t_h = scan.nextInt();
            int t_w = scan.nextInt();
            list.add(new People(t_h, t_w));
        }
        grid = new int[num][num];
        main.solution(0);
    }
}
  • 정리
    • 처음에는 효율적인 방법이 떠오르지 않아 일단 정답이 출력될수있게 하드코딩해 2차 반복을 돌렸다.
    • 정답은 출력되었으나 효율적이지 못하다고 판단해 개선답안을 아래 구상

  • 풀이 답안1 (개선)

import java.util.*;

class People implements Comparable<People> {
    int h;
    int w;
    public People(int h, int w) {
        this.h = h;
        this.w = w;
    }
    @Override
    public int compareTo(People o) {
        return o.h-this.h;
    }
}

public class Main {

    static List<People> list = new ArrayList<>();
    static int max;
    public void solution (int num) {
        Collections.sort(list);

        max=list.get(0).w;
        int answer = 1;

        for(int i=1; i<num; i++) {
            if(list.get(i).w>max) {
                max = list.get(i).w;
                answer++;
            }
        }
        System.out.println(answer);
    }

    public static void main(String[] args) {

        Main main = new Main();
        Scanner scan = new Scanner(System.in);
        int num = scan.nextInt();
        for(int i=0; i<num; i++){
            int t_h = scan.nextInt();
            int t_w = scan.nextInt();
            list.add(new People(t_h, t_w));
        }
        main.solution(num);
    }
}
  • 정리
    • 키나 몸무게 둘 중에 하나라도 최대값을 가진 데이터보다 다른 큰 데이터를 가지고 있으면 되기에 우선 list를 compareTo를 이용해 키순으로 나열함
    • 키가 제일 큰 데이터는 그 자체로 조건을 충족하기에 답에 1을 미리 플러스해서 초기설정해두고, 몸무게의 현 최대값을 max로 설정해둠
    • 키순으로 정렬된 리스트를 반복문을 통해 1회전 하면서
    • 현재 max에 담겨진 값보다 몸무게가 크면 답을 1증가(이후 몸무게가 더 큰 데이터가 나오더라도 이미 그보다 키가 더 큼이 증명되기에, 나보다 키 큰 사람보다만 몸무게가 크면 됨)
    • 그리고 현재의 max를 내가 가진 max로 변경해줌
    • 루프를 최종까지 돌았을때 나온 정답을 출력하면 됨
  • 초기 풀이와 개선 풀이의 메모리 사용량은 27mb로 동일했으나 시간이 초기풀이는 168ms, 개선풀이는 131ms로 단축됨

Updated: