백준 2628번 종이자르기 JAVA

링크텍스트

설명

감이 안 잡혀서 구글링해 보니 리스트를 사용해 가로와 세로 최대 간격을 구하는 방식이었다.
자르는 점선의 위치가 무작위로 주어지기 때문에 그 사이의 최대 간격을 계산하려면 먼저 위치들을 정렬해야 한다.
시간복잡도: O(NLogN), 공간복잡도: O(N)

코드

import java.util.*;
import java.io.*;

class Main {
	public static void main (String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken()); 

		int [][] arr = new int[r][c];

		int n = Integer.parseInt(br.readLine());

		ArrayList<Integer> rowCuts = new ArrayList<>();
		ArrayList<Integer> colCuts = new ArrayList<>();

		rowCuts.add(0);
        rowCuts.add(c);
        colCuts.add(0);
        colCuts.add(r);

		for(int i=0;i<n;i++){
			st = new StringTokenizer(br.readLine());
			int type = Integer.parseInt(st.nextToken());
            int pos = Integer.parseInt(st.nextToken());

			if(type==0) rowCuts.add(pos);
			else colCuts.add(pos);
		}

		Collections.sort(rowCuts);
        Collections.sort(colCuts);

		int maxRow = Cut(rowCuts);
		int maxCol = Cut(colCuts);

		System.out.println(maxRow*maxCol);
	}

	public static int Cut(List<Integer> list){
		int max = 0;

		for(int i=1;i<list.size();i++){
			max = Math.max(max,list.get(i)-list.get(i-1));
		}
		return max;
	}
}

참고 글

https://hanyeop.tistory.com/337

https://read-me.tistory.com/entry/javabojs5-2628-%EC%A2%85%EC%9D%B4%EC%9E%90%EB%A5%B4%EA%B8%B0