[Kotlin, S5] 백준 32344번 유물 발굴

출처: unsplash.com

 

유물 발굴(32344번)

Silver 5

#구현 #기하학

https://www.acmicpc.net/problem/32344

 

문제 내용

 

 

문제 접근

운동장에 a번 유물이 w, h 위치에 묻혀 있다.

a번 유물 조각들의 위치 정보를 이용해 a번 유물의 예상 크기를 직사각형으로 정의한다.

직사각형의 넓이가 가장 큰 유물의 번호와 그 넓이를 출력한다.

만약 넓이가 동일하다면 유물 번호가 더 작은 게 더 우선이다.

 

유물의 예상 크기 직사각형을 구하는 방법은 아래와 같다.

예를 들어 4개의 위치에 유물이 있을 때

점 a, b, c, d가 유물의 위치라고 하면 유물의 예상 크기는 사각형 efgh와 같다.

위 사진으로 가장 큰 x축(d)과 가장 작은 x축(a), 그리고 가장 큰 y축(c)과 가장 작은 y축(b)의 값을 이용해 위 도형의 넓이를 구할  수 있게 된다.

 

결론은 (x값의 최댓값 -  x값의 최솟값 + 1) * (y값의 최댓값 - y값의 최솟값 + 1)의 공식으로 유물의 예상 크기를 구할 수 있다.

 

 

문제 해결 코드

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (r, c) = readLine().split(" ").map { it.toInt() }
    val relicCnt = readLine().toInt()
    val relics = mutableMapOf<Int, MutableList<List<Int>>>()

    for (i in 0 until relicCnt) {
        val (relicsNumber, w, h) = readLine().split(" ").map { it.toInt() }

        if (!relics.containsKey(relicsNumber)) {
            relics[relicsNumber] = mutableListOf(listOf(w, h))
        } else {
            relics[relicsNumber]?.add(listOf(w, h))
        }
    }

    var answer = Pair(0, 0L)
    for (relic in relics) {
        val area = getArea(relic.value)
        if (answer.second < area) {
            answer = Pair(relic.key, area)
        } else if (answer.second == area && answer.first > relic.key) {
            answer = Pair(relic.key, area)
        }
    }

    println("${answer.first} ${answer.second}")
}

private fun getArea(relicLocation: MutableList<List<Int>>): Long {
    var wMax = 0
    var wMin = Int.MAX_VALUE

    var hMax = 0
    var hMin = Int.MAX_VALUE

    for (location in relicLocation) {
        if (location[0] > wMax) wMax = location[0]
        if (location[0] < wMin) wMin = location[0]

        if (location[1] > hMax) hMax = location[1]
        if (location[1] < hMin) hMin = location[1]
    }

    return (wMax - wMin + 1) * (hMax - hMin + 1).toLong()
}

 

문제 풀이

유물 번호에 따른 유물 조각의 위치를 저장하기 위해 mutableMap을 이용해 주었다.

map에 데이터를 추가하고, map의 데이터들을 이용해 각 유물의 예상 크기를 구해서 가장 큰 값을 출력한다.

만약 값이 같다면 유물 번호가 더 작은 것으로 바뀐다.

 

 

문제 해결 과정

귀찮은 구현 문제이다.

최솟값과 최댓값을 이용해 유물의 예상 크기를 구하는 아이디어를 떠올리는 데 생각이 좀 필요하다.

 

그리고 유물의 예상 크기가 Int 범위를 넘어갈 수 있다. 이를 유의해야 한다.

또한 유물의 예상 크기가 같은 경우에는 더 작은 번호인 유물이 더 우선으로 출력돼야 한다.

이를 까먹지 말자.