[구름톤 챌린지, Java] 18일차, 중첩 점(누적합)

문제 링크

구름LEVEL

---

접근 방법

이 문제에 핵심

1. 길이가 N인 정사각형이 존재하며, 1 × 1 크기의 정사각형으로 구분되어있습니다.

2. 반직선 (y, x)를 그리며, 해당 반직선은 (y, x)의 칸을 지납니다.

3. 반직선의 방향은 상하좌우만 가능하며, 같은 칸을 지나는 평행한 반직선은 서로 만나지 않는다.

4. 좌우 반직선과 상하 반직선의 중첩점이 생기는 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 좌우 반직선의 대한 누적합을 구한 뒤, 상하 반직선을 기준으로 중첩점을 구합니다.

 

3. 구한 중첩점의 개수를 결과로 출력합니다.

 

 

구현

 

이 문제를 접근할 때 각각의 반직선의 정보를 완전 탐색으로 적용시키는 것은 비효율적이라고 판단하였습니다.

 

저는 정사각형 2차원 배열의 각 행을 누적합이 진행되도록 구성하였습니다.

 

아래와 같은 정사각형에서 반직선이 그려졌을 때

(1, 2) : R

(2, 2) : L

 

(L : 0, R : 1)	(L : 1, R : 0)
(L : 0, R : 0)	(L : 0, R : 0)

누적합을 적용시키기 위해서 위처럼 표현할 수 있습니다.

 

R(오른쪽)방향으로 누적합 진행

1	1
0	0

L(왼쪽) 방향으로 누적합 진행 

2	2
0	0

이제 상하 반직선이 추가되면

 

(2, 1), (2, 2)을 지나는 모든 좌우 반직선의 개수의 합입니다.

 

[2][1] = 0

[2][2] = 2

 

0 + 2 = 2

 

위와 같이 상하 반직선의 범위에 속한 누적합의 값을 모두 더한 값이 해당 반직선에서 발생하는 중첩점의 개수입니다.

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

N : 3

M : 6

 

좌우 반직선으로 이루어진 정사각형

좌우 반직선으로 이루어진 정사각형

1 1 D
3 3 U
2 2 D

 

2. 좌우 반직선의 대한 누적합을 구한 뒤, 상하 반직선을 기준으로 중첩점을 구합니다.

 

좌우 반직선을 누적합으로 표현하면

 

(L : 0, R : 0)	(L : 0, R : 0)	(L : 0, R : 0)
(L : 0, R : 0)	(L : 1, R : 1)	(L : 0, R : 0)
(L : 0, R : 0)	(L : 0, R : 0)	(L : 0, R : 0)

 

R(오른쪽)방향으로 누적합 진행

0	0	0
0	1	1
0	0	0

L(왼쪽) 방향으로 누적합 진행 

0	0	0
1	2	1
0	0	0

 

1 1 D : [1][1](0) + [2][1](1) + [3][1](0) = 1

2 2 D : [2][2](2) + [3][2](0) = 2
3 3 U : [3][3](0) + [2][3](1) + [1][3](0) = 1

 

1 + 2 + 1 = 4개

 

3. 구한 중첩점의 개수를 결과로 출력합니다.

 

 

중첨점 : 4개

 

4을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 통해 띄어쓰기 기준 입력값을 나누었습니다.
• 좌우 반직선에 입력을 기준으로 누적합 관련 정보를 설정하였습니다.
• 오른쪽, 왼쪽 순으로 누적합을 통한 정사각형 배열을 구성하였습니다.
• 상하 반직선을 추가하며, 누적합 배열의 범위만큼 모두 더해서 중첩점의 개수를 구합니다.
• 구한 중첩점의 개수를 결과로 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

 

결과코드

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

class Main {
    //누적합 관련 정보 클래스
    static class SumInfo{
        // l : 왼쪽 방향 합해야 할 값
        // r : 오른쪽 방향 합해야 할 값
        int l, r;

        public SumInfo(int l, int r) {
            this.l = l;
            this.r = r;
        }
    }
    //상하 반직선 정보 클래스
    static class UDInfo{
        //d : 방향값
        //상 : -1, 하 : 1
        int y, x, d;

        public UDInfo(int y, int x, int d) {
            this.y = y;
            this.x = x;
            this.d = d;
        }
    }
    public static void main(String[] args) throws Exception {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //입력값 저장
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        SumInfo[][] sum = new SumInfo[N+1][N+1];
        List<UDInfo> udInfos = new ArrayList<>();
        int[][] square = new int[N+1][N+1];
        //누적합 정보 배열 초기화
        for(int i=0;i<=N;i++){
            for(int j=0;j<=N;j++){
                sum[i][j] = new SumInfo(0, 0);
            }
        }
        //M개의 반직선 정보 처리
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine()," ");
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            String dir = st.nextToken();
            //'상' 반직선
            if(dir.equals("U")) {
                udInfos.add(new UDInfo(y, x, -1));	//상하 반직선 리스트 정보 추가
            }else if(dir.equals("D")) {		//'하' 반직선
                udInfos.add(new UDInfo(y, x, 1));	//상하 반직선 리스트 정보 추가
            }else if(dir.equals("L")) {		//'좌' 반직선
                sum[y][x].l++;		//누적합 왼쪽 값 + 1
            }else if(dir.equals("R")) {		//'우' 반직선
                sum[y][x].r++;		//누적합 오른쪽 값 + 1
            }
        }
        //R방향 누적합 구하기
        for(int i=1;i<=N;i++){
            square[i][1] += sum[i][1].r;
            for(int j=2;j<=N;j++){
                square[i][j] = square[i][j-1] + sum[i][j].r;
            }
        }
        //L방향 누적합 구하기
        for(int i=1;i<=N;i++){
            square[i][N] += sum[i][N].l;
            int val = sum[i][N].l;
            for(int j=N-1;j>0;j--){
                val += sum[i][j].l;
                square[i][j] += val;
            }
        }
        long result = 0;
        //상하 반직선을 지나는 누적합 값 더하기
        for(UDInfo val : udInfos){
            int y = val.y;
            int x = val.x;
            int dir = val.d;
            //상하 반직선이 지나는 값 더하기
            while(y > 0 && y <= N){
                result += square[y][x];
                y += dir;
            }
        }
        //중첩점의 개수 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}

 

---

느낀 점

 

문제를 처음 접근할 때에는 완전탐색으로 진행하는 것이 비효율적이라고 생각하였습니다.

 

상하, 좌우 직선끼리는 평행하기 때문에 누적합을 사용할 수 있다고 생각하였습니다.

 

시간복잡도를 계산했을 때 완전탐색보다 시간복잡도는 좋아졌지만, 공간 복잡도는 떨어지는 방법이라고 판단하였지만,

 

공간 복잡도가 크게 떨어지지 않다고 판단하여 누적합을 적용하였습니다.

 

하나의 문제를 풀더라도 더 나은 방법을 생각하는 재미가 있다는 것을 깨닫게 되면서 다른 문제를 풀면서도 더 나은 방법이 있는지 찾아보는 마음가짐을 깨닫게 되었습니다.