2628. 종이자르기 (JAVA)

[백준] 2628. 종이자르기

⏰ time

40분

📌 Algorithm

구현, 정렬

⏲️Time Complexity

212ms

📍 Logic

• 가로로 자르는 넘버, 세로로 자르는 넘버를 각각의 리스트에 넣는다.

            if (dir == 0) {
                wList.add(num);
            } else if (dir == 1) {
                hList.add(num);
            }

• 전체 길이를 추가하고, 내림차순으로 정렬한다.
• 이때 '가로로 자르는 넘버'는 세로 길이에 영향을 주므로, wList에 h를 추가해야 한다. (반대도 마찬가지)

        wList.add(h);
        wList.add(0);
        hList.add(w);
        hList.add(0);

        Collections.sort(wList, Collections.reverseOrder());
        Collections.sort(hList, Collections.reverseOrder());

• 각 요소들 사이 간격을 구하고, 그 중 max값을 추출한다.

        int hLength = 0;
        int maxHLength = 0;
        for (int i = 0; i < wLastIndex; i++) {
            hLength = wList.get(i) - wList.get(i + 1);
            if (maxHLength < hLength) {
                maxHLength = hLength;
            }
        }

• max 가로값, 세로값을 곱하여 출력한다.

✒️ Review

• wList에 h를 추가해야 하는데, 반대로 w를 추가했었다. 금방 고쳤다.

📡Link

• https://www.acmicpc.net/problem/2628

 

 

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int w = sc.nextInt();
        int h = sc.nextInt();
        int N = sc.nextInt();
  
        ArrayList<Integer> wList = new ArrayList<>(); //가로로 자르는 선, 즉 세로길이에 영향
        ArrayList<Integer> hList = new ArrayList<>(); //세로로 자르는 선, 즉 가로길이에 영향

        for (int i = 0; i < N; i++) { // 가로, 세로 컷넘버 분류
            int dir = sc.nextInt();
            int num = sc.nextInt();

            if (dir == 0) {
                wList.add(num);
            } else if (dir == 1) {
                hList.add(num);
            }
        }
        
        wList.add(h);
        wList.add(0);
        hList.add(w);
        hList.add(0);

        Collections.sort(wList, Collections.reverseOrder());
        Collections.sort(hList, Collections.reverseOrder());

        int wLastIndex = wList.size() - 1;
        int hLastIndex = hList.size() - 1;

        int hLength = 0;
        int maxHLength = 0;
        for (int i = 0; i < wLastIndex; i++) {
            hLength = wList.get(i) - wList.get(i + 1);
            if (maxHLength < hLength) {
                maxHLength = hLength;
            }
        }
        int wLength = 0;
        int maxWLength = 0;
        for (int i = 0; i < hLastIndex; i++) {
            wLength = hList.get(i) - hList.get(i + 1);
            if (maxWLength < wLength) {
                maxWLength = wLength;
            }
        }

        System.out.println(maxWLength*maxHLength);
    }
}