[백준알고리즘] 정렬 - 2628번 종이자르기 문제

첫번째 제출에서 틀렸었는데,

가로로는 자르지 않거나 세로로는 자르지 않았을 경우를 생각해놓지 않아서 90퍼쯤에서 런타임에러가 떴었다.

sort함수를 써서 정렬을 하긴 했는데 정렬 문제를 이렇게 풀어도 되나(?) -> ㄱㅊ

사실 풀때 첨엔 좀 막막했었다. 뭔가 쉬워보이는데 바로 쉽게 풀리진 않았던 문제..

가로로 잘랐을때 생기는 각 높이들, 세로로 잘랐을때 생가는 각 가로길이들을 구하고

(이것들을 모두 조합하면 잘랐을때 생기는 모든 사각형들이게 되므로)

각각 내림차순으로 정렬해서 가장 앞에 있는 값을 각각 구해(가장 큰 값) 그 두개를 곱해서 답을 구했다.

 

 

풀이코드

package baekjoonWeek5;

import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class BJ_2628 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int width = Integer.parseInt(st.nextToken());
        int height = Integer.parseInt(st.nextToken());
        int cut = Integer.parseInt(br.readLine());  //자르는 횟수
        ArrayList<Integer> widths = new ArrayList<>();
        ArrayList<Integer> heights = new ArrayList<>();
        ArrayList<Integer> xcuts = new ArrayList<>();
        ArrayList<Integer> ycuts = new ArrayList<>();

        for (int i = 0; i < cut; i++) {
            st = new StringTokenizer(br.readLine());
            int xOrY = Integer.parseInt(st.nextToken());
            int tmp = Integer.parseInt(st.nextToken());
            if (xOrY == 0) {
                xcuts.add(tmp);
            } else {
                ycuts.add(tmp);
            }
        }
        Collections.sort(xcuts);
        Collections.sort(ycuts);

        int xStart = 0; int yStart = 0;
        int tmp;
        for (int i = 0; i < xcuts.size(); i++) {
            tmp = xcuts.get(i);
            heights.add(tmp - xStart);
            xStart = tmp;
        }
        for (int i = 0; i < ycuts.size(); i++) {
            tmp = ycuts.get(i);
            widths.add(tmp - yStart);
            yStart = tmp;
        }

        //가로로는 자르지 않거나 세로로는 자르지 않거나 아예 자르지 않는 경우도 고려하자
        if (xStart == 0 || xStart != height) {
            heights.add(height - xStart);   //마지막 높이도 넣어준다
        }
        if (yStart == 0 || yStart != width) {
            widths.add(width - yStart);
        }
        Collections.sort(widths, Collections.reverseOrder());   //내림차순 정렬
        Collections.sort(heights, Collections.reverseOrder());
        
        bw.write(Integer.toString(widths.get(0) * heights.get(0)));
        bw.flush();
        bw.close();

    }



}