[코드트리/NOVICE MID] 겹치지 않는 사각형의 넓이 (JAVA)

🔺 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static final int OFFSET = 1000;
    static int[][] rect = new int[2001][2001];
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        // 1. 각 직사각형 영역에 대해 숫자 집어넣기 (x1, y1) (x2, y2)
        for(int i = 0 ; i < 3 ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
 
            // 직사각형 A, B 붙이기
            if(i < 2) {
                paint(i + 1, x1 + OFFSET, y1 + OFFSET, x2 + OFFSET, y2 + OFFSET);
            }
            // 직사각형 M 붙이기 (이미 1인 구간이라면, 0으로 바꾸기)
            else {
                paint(0, x1 + OFFSET, y1 + OFFSET, x2 + OFFSET, y2 + OFFSET);
            }
        }
 
        int cnt = 0;
        for(int i = 0 ; i < 2000 ; i++) {
            for(int j = 0 ; j < 2000 ; j++) {
                //System.out.print(rect[i][j] + " ");
                if(rect[i][j] != 0)
                    cnt++;
            }
            //System.out.println();
        }
        System.out.println(cnt);   
    }
 
    // 직사각형 붙이는 메소드
    private static void paint(int num, int x1, int y1, int x2, int y2) {
        for(int i = x1 ; i < x2 ; i++) {
            for(int j = y1 ; j < y2 ; j++) {
                rect[i][j] = num;
            }
        }
    }
}

 

 

🧩  해결 아이디어

• 사각형 칠하기

- 직사각형 A, B 구간의 값을 OFFSET하여 2차원 배열에 각자 1, 2로 붙인다. (범위 : (x1,y1) ~ (x2 - 1,  y2 - 1)까지)

- 직사각형 M을 붙인다. 이 때, M구간에 존재하는 값은 모두 0으로 바꾼다.

- 2차원 배열 내에서 0이 아닌 칸의 갯수를 구한다.

 

- 시간 복잡도 : O(R^2)

 

 

 

---

💬 느낀 점

담엔 더 빨리 풀자!

 

1회독	2회독	3회독	4회독	5회독
V