1258번 - 행렬찾기

문제의 저작권은 SW Expert Academy에 있습니다.

1. 문제
    1-1. 링크
    1-2. 문제 해석
2. 코드
3. 실행시간

 

 

 

---

 

1. 문제

1-1. 링크

SW Expert Academy

 

1-2. 문제 해석

문제에서 주어지는 예제

 

문제는 간단하다(?)

주어지는 입력에서 사각형을 찾고 사각형의 가로 세로를 순서대로 출력하면 된다.

위 예제에서는 노란색 사각형(3x4), 파란색 사각형(2x3), 초록색 사각형(4x5)이 있다.

입력과 출력에 붙는 조건은 어렵지 않으니 문제에서 확인하면 되고

나는 저 사각형의 가로 세로 길이를 구하는 로직에 대해서 다뤄보려고 한다.

 

1. 문제를 다 풀고 다른 사람들의 답을 찾아보니 흔히들 푸는 방법은 아닌 것 같아요.
대표적인 풀이를 보고 싶어서 오신거라면 뒤로가기를 살포시 😢

2. 하지만 속도는 빠릅니다. 후후

 

 

• 불필요한 탐색을 줄이자.

노란색 사각형 뒤쪽으로는 탐색을 할 필요가 없다.

 

배열의 모든 인덱스를 다 방문하면서 사각형을 체크해도 되지만

나는 최대한 불필요한 탐색을 줄이고 싶었다.

지금 위 예제를 보면 노란색 사각형 뒤에는 더 이상 사각형이 없으므로 탐색을 하지 않아도 된다.

이런 경우에 노란색만 탐색할수는 없을까?🤔 라는 생각을 하게 됐다.

 

 

행을 하나 추가했다.

 

그래서 가로 방향에서 사각형에 해당하는 부분(= '0'이 아닌 부분)의 개수를 카운트하는 행을 하나 만들었다.

이렇게 하면 내가 몇 번째 인덱스까지만 탐색을 하면 되는지 알 수 있다.

사각형과 사각형 사이에 있는 '0'들은 스킵할 수 없고 무조건 탐색해야 하지만

맨 마지막 사각형의 끝부분과 배열의 끝 사이에 있는 '0'들은 이 방법으로 스킵이 가능하다.

 

 

• 한 번 탐색한 사각형은 다시 탐색하지 말자.

첫 번째 열을 탐색하는 중

 

예를 들어 (0, 1)을 방문하여 사각형의 가로와 세로 길이를 구했다고 치자.

 

 

두 번째 열을 탐색하는 중

 

그다음 두 번째 열을 탐색할 차례가 왔을 때

우리는 (1, 1), (1, 2), (1, 3), (1, 4)를 방문하며 이미 측정했던 사각형을 또다시 탐색하게 된다.

굉장히 불필요한 작업이다.

이를 해결할 방법이 없을까 생각해봤다. 🤔

 

1~9 사이의 숫자를 전부 -1로 바꿨다.

 

나는 사각형 안에 들어가는 1~9까지의 숫자가 무의미하다는 점을 이용했다.

각각 다른 숫자가 주어지길래 언제 써먹는 건가 싶었는데 아무런 의미가 없고

그냥 '0'이 아니면 사각형이라는 것을 나타낼 수 있었다. 그래서 일단 전부 -1로 바꿨다.

 

첫 번째 열을 탐색하는 중

 

그리고 탐색을 하다가 '-1'을 만나면 사각형의 왼쪽 상단 모서리를 만난 것으로 간주하여

가로길이와 세로 길이를 측정해 저장하고

왼쪽 변의 값을 전부 가로길이로 바꿨다.

 

두 번째 열을 탐색하는 중

 

이렇게 하면 두 번째 열을 탐색할 때 이미 측정한 사각형이라는 것을 알 수 있다.

가로의 길이를 저장해두었으므로 가로의 길이만큼 한 번에 인덱스를 건너뛴다.

즉, 사각형 다음의 인덱스부터 다시 탐색을 시작한다.

나는 이 방법으로 시간을 단축했다.

 

 

• 정렬하는 방법

	.
    .
    .
    public static void main(String[] args) throws Exception {		
		Comparator<Square> comparator = new Comparator<Square>() {

			@Override
			public int compare(Square o1, Square o2) {
				return o1.compareTo(o2);
			}
			
		};
        .
        .
        .
    }
}

class Square implements Comparable<Square>{
	int h;
	int w;
	
	public Square(int h, int w) {
		this.h = h;
		this.w = w;
	}

	@Override
	public int compareTo(Square s) {
		int thisArea = this.h * this.w;
		int area = s.h * s.w;
		
		if(thisArea != area) { // 넓이가 다르다면
			return thisArea - area; // 넓이 기준으로 정렬
		}
		
		return this.h - s.h; // 넓이가 같다면 높이로 정렬
	}
}

문제에서 요구하는 정렬 순은 이클립스에서 제공하는 사전 순이나 값의 크기순 등이 아니기 때문에

직접 정렬 규칙을 만들어주어야 한다.

나는 Comparable을 implements 해서 규칙을 정해주었고

comparator를 생성해 PriorityQueue에게 넘겨주었다.

 

Comparable, comparator, PriorityQueue이 무엇인지에 대해 적는 것은
포스팅의 범주를 벗어나는 것 같아서 생략...
모르시는 분들은 검색해보셔야 합니다 ㅠㅠ

 

 

2. 코드

package algorithm;

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

public class Day14_1258_행렬찾기 {
	static PriorityQueue<Square> pq;
	static int[][] store;
	static int N;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		int testCase = Integer.parseInt(br.readLine());

		Comparator<Square> comparator = new Comparator<Square>() {

			@Override
			public int compare(Square o1, Square o2) {
				return o1.compareTo(o2);
			}

		};

		for (int tc = 1; tc <= testCase; tc++) {
			N = Integer.parseInt(br.readLine());
			store = new int[N][N + 1]; // 가로의 합을 저장하려고 +1 함
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 1; j < N + 1; j++) {
					int num = Integer.parseInt(st.nextToken());
					if (num != 0) {
						store[i][0]++; // 가로의 총합 +1
						store[i][j] = -1; // 문제에서 주어진 숫자는 쓸모 없드라..
					}
				}
			}

			pq = new PriorityQueue<Square>(comparator);
			for (int i = 0; i < N; i++) {
				int cnt = 0;
				for (int j = 1; j < N + 1; j++) {
					if (cnt >= store[i][0]) { // 뒤쪽으로는 다 0이라서 조사할 가치가 없는 경우
						break;
					} else if (store[i][j] > 0) { // 0보다 큰 경우: 이미 조사를 마친 사각형인 경우
						cnt += store[i][j]; // 카운트하고
						j += store[i][j]; // 점프
					} else if (store[i][j] == -1) { // 사각형 발견!
						measure(i, j);
						cnt += store[i][j]; // 카운트하고
						j += store[i][j]; // 점프
					}
				}
			}

			// 순서 구하기
			sb.append("#").append(tc).append(" ").append(pq.size()).append(" ");
			while (!pq.isEmpty()) {
				Square s = pq.poll();
				sb.append(s.h).append(" ").append(s.w).append(" ");
			}
			sb.append("\n");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	public static void measure(int i, int j) {
		int h = 0, w = 0;

		// 세로길이 측정
		int y = i, x = j;
		while (y < N && store[y][x] != 0) {
			h++;
			y++;
		}

		y = i;
		x = j;
		// 가로길이 측정
		while (x < N + 1 && store[y][x] != 0) {
			w++;
			x++;
		}

		// 사각형 크기 저장
		pq.add(new Square(h, w));

		// 사각형의 첫 행에 건너뛸 칸수를 저장해둠
		for (y = i; y < i + h; y++) {
			store[y][j] = w;
		}
	}

}

class Square implements Comparable<Square> {
	int h;
	int w;

	public Square(int h, int w) {
		this.h = h;
		this.w = w;
	}

	@Override
	public int compareTo(Square s) {
		int thisArea = this.h * this.w;
		int area = s.h * s.w;

		if (thisArea != area) {
			return thisArea - area;
		}

		return this.h - s.h;
	}
}

다소 코드가 길고 복잡한 감이 있긴 하다.

 

 

3. 실행시간

앗싸 1등!!!

 

반에서 1등을 했다 😋

근데 순위에 집착하는 건 나밖에 없을지도...

나 혼자만의 싸움일지도...

 

싸피 전체 순위는 764명 중 43등 정도 되는 것 같다.

 

 

 

 

---

💡 느낀 점

• 조건이 조금 더 까다로웠으면 이 방법으로는 못 풀었을 것 같다. 운이 좋았는 듯
• 문제 카테고리는 DP인데 내가 푼 방법은 그냥 가지치기를 많이 한 느낌? 출제자의 의도에 맞는 Best 답은 아닐 것 같다.

---