Jungol[1828] - 냉장고

링크

 

JUNGOL | 냉장고 > 문제은행

문제설명

• 그리디

문제풀이

• 그리디

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main1828 {
    public static void main(String[] args) throws NumberFormatException, IOException {
        System.setIn(new FileInputStream("res/jungol/1828.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int[][] m= new int[N][2];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            m[i][0] = Integer.parseInt(st.nextToken());
            m[i][1] = Integer.parseInt(st.nextToken());
        }


        Arrays.sort(m, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                // TODO Auto-generated method stub
                if(o1[0] > o2[0])
                    return 1;
                else if (o1[0] == o2[0])
                    return 0;
                return -1;
            }
        });

        int max_temp=Integer.MIN_VALUE;
        int ans=0;
        for (int i = 0; i < N; i++) {
            if(m[i][1] <= max_temp) {    //냉장고 포함 가능
                max_temp=m[i][1];
            }
            else {
                if(m[i][0] <= max_temp) {    //냉장고 포함 가능

                }
                else {    //냉장고 포함 불가능
                    ans++;
                    max_temp=m[i][1];
                }
            }
        }
        System.out.println(ans);
    }
}

아쉬운점

• 처음에 온도를 범위로 index만들어서 포함하는 물건의 갯수가 가장 높은 온도를 정하고 pop하고 반복하는 방법
  • 구현해보려다가 복잡했음. 시간초과났을수도
  • 정렬하는 생각을 못했음.
• Comparator 쓰는 방법 몰라서 2차원배열 정렬 못했음
  • Overriding시, 1일 때 swap, 0일 때 그대로, -1일 때 그대로

잘한점

• 정렬 후->최선을 찾는다는 생각함.
• 최선의 온도를 찾는다 -> 나머지 가능한것들 중 최선의 온도를 찾는다.