[Kotlin, S5] 백준 9196번 정수 직사각형

출처: unsplash.com

 

정수 직사각형(9196번)

Silver 5

#브루트포스 알고리즘 #정렬 #런타임 전의 전처리

 

문제 내용

 

 

문제 접근

문제에서의 직사각형의 크기를 판별하는 방법은 2가지이다.

1. 대각선이 더 긴 직사각형이 더 큰 직사각형이다.

2. 대각선의 길이가 같으면 높이가 더 높은 것이 더 큰 직사각형이다.

이 2가지 조건을 이용해 입력받는 직사각형보다 큰 직사각형 중 가장 작은 직사각형을 출력해야 한다.

 

문제 조건이 직사각형 값이 150을 넘지 않는다고 한다. 이러면 전체 탐색을 해도 상관없는 제한이다.

그래서 높이와 너비가 1부터 150까지의 직사각형들을 모두 뽑아서 정렬시키면 된다.

하지만 문제에 조건이 있다.

1. 너비(w)가 높이(h) 보다 커야 한다.

2. 직사각형만을 뽑아야 한다.

위 2가지의 조건을 코드로 구현해 보자.

 

우선 높이와 너비가 각 1부터 150까지 뽑을 수 있는 2중 반복을 해야 한다.

거기서 w(너비)는 높이보다 무조건 커야 한다. 또한 정사각형이 되면 안 된다.

val allSquare = mutableListOf<List<Int>>()
// 너비가 높이보다 커야 함.
for (h in 1 .. 150) {
    for (w in h .. 150) {
        if (h == w) continue
        allSquare.add(listOf(h, w))
    }
}

위 반복에서 w가 h보다 큰 직사각형들이 리스트에 담기게 된다.

하지만 리스트에 담긴 상태는 현재 문제 조건의 직사각형 크기 순으로 정렬된 게 아니다.

문제 조건에 맞게 정렬해 줘야 한다.

 

우선순위가 더 낮은 높이 순으로 정렬을 해준 다음에 우선순위가 높은 대각선 길이 기준으로 정렬을 해준다.

allSquare.sortBy { it[0] }
allSquare.sortBy { it[0] * it[0] + it[1] * it[1] }

이제 allSquare에는 문제 조건에 맞는 직사각형들이 작은 것에서 큰 순서대로 정렬되어 들어간다.

이 리스트에서 입력값이 들어 있는 리스트 index의 다음 값이 큰 직사각형 중 제일 작은 직사각형이 될 것이다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val allSquare = mutableListOf<List<Int>>()
    // 너비가 높이보다 커야 함.
    for (h in 1 .. 150) {
        for (w in h .. 150) {
            if (h == w) continue
            allSquare.add(listOf(h, w))
        }
    }
    allSquare.sortBy { it[0] }
    allSquare.sortBy { it[0] * it[0] + it[1] * it[1] }

    while (true) {
        val square = readLine().split(" ").map { it.toInt() }
        if (square == listOf(0, 0)) break

        val index = allSquare.indexOf(square)
        println(allSquare[index + 1].joinToString(" "))
    }
}

 

문제 풀이

allSquare을 1부터 150까지의 직사각형들을 모두 모아서 문제 조건에 맞게 정렬해 준다.

입력값이 0 0이 들어올 때까지 반복한다.

 

allSquare에서 입력값과 동일한 값이 들어 있는 index를 찾아 준다.

그리고 찾은 index의 다음 값을 출력한다.

 

 

문제 해결 과정

쓸데없이 효율적이게 풀려다가 시간낭비만 한 문제이다.

문제 제한이 작아서 단순하게 무지성 전체 탐색이 가능한 문제이다.

전체 탐색이 확실히 쉽게 구현할 수 있지만 문제 범위가 작을 때만 사용하도록 하자.