[Kotlin, S4] 백준 2358번 평행선

출처: unsplash.com

 

평행선(2358번)

Silver 4

#자료 구조 #정렬 #해시를 사용한 집합과 맵

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

 

문제 내용

 

 

문제 접근

2개 이상의 점을 지나는 선분에서 x축 또는 y축에 평행한 선분의 개수를 세는 문제.

선분의 구성이 2개 이상의 점을 지날 수도 있고, 한 좌표에 점이 여러 개가 있을 수도 있다.

// 선분의 구성에 2개 이상의 점이 쓰이는 경우
4
1 0
2 0
3 0
4 0

정답: 1

// 한 좌표에 여러 점이 있는 경우
2
1 1
1 1

정답: 2

첫 번째 case가 이해하기 어려웠다.

문제를 처음 읽었을 때는 2개 이상의 점을 지나는 선분이라는 것을 못 보고 2개의 점을 지나는 선분이라고 생각해서 왜 1개가 나오는지 헷갈렸다.

case 1의 경우에는 점 4개를 연결한 y축과 평행한 선분 1개만 존재하게 된다.

case 2의 경우에는 좌표가 1개이지만 2개의 점이 있기 때문에 무한대의 경우가 생기게 된다.

무한대의 경우들 중에서 x, y축과 평행하는 경우가 1가지씩 존재하기 때문에 정답이 2이다.

 

case들을 보고 x 또는 y 값이 같은 애들을 묶으면 되지 않을까 하고 생각이 들었다.

묶은 좌표들의 개수가 2개보다 많으면 선분을 구성할 수 있기 때문에 2개 이상인 경우에만 카운트를 늘려주는 방식으로 이용했다.

 

 

문제 해결 코드

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val points = readLine().toInt()
    val xMap = mutableMapOf<Int, Int>()
    val yMap = mutableMapOf<Int, Int>()

    for (i in 0 until points) {
        val (coordinateX, coordinateY) = readLine().split(" ").map { it.toInt() }

        if (!xMap.containsKey(coordinateX)) xMap[coordinateX] = 1
        else xMap[coordinateX] = xMap[coordinateX]!! + 1

        if (!yMap.containsKey(coordinateY)) yMap[coordinateY] = 1
        else yMap[coordinateY] = yMap[coordinateY]!! + 1
    }

    var answer = 0
    for (x in xMap) {
        if (x.value >= 2) answer++
    }

    for (y in yMap) {
        if (y.value >= 2) answer++
    }
    println(answer)
}

 

문제 풀이

입력된 같은 x 또는 y좌표가 몇 개인지 확인할 map을 생성해 주었다.

입력값에서 x, y좌표값이 같은 좌표가 2개 이상 있으면 평행선의 개수(answer)를 늘려 준다.

 

문제 접근의 case들은 다음과 같이 map이 구성되게 된다.

case 1

case 2

case 1의 경우는 각 x의 개수가 2개가 넘지 않기 때문에 선을 연결할 수 없다.

case 2의 경우는 x, y의 개수가 2개이기 때문에 평행선을 구성할 수 있다.

 

 

문제 해결 과정

문제를 처음 봤을 때는 별생각 없이 구현했는데, 반례를 찾아보려고 게시판에 들어가니까 과거에 이 문제에 불만이 상당했던 것 같다.

게시판에서 점 여러 개를 이을 수 있는 것과 한 좌표에 점이 여러 개 올 수 있다는 것을 알게 되고 코드를 처음부터 다시 짜게 되었다.

게시판을 보고 문제를 다시 자세히 읽고 나서 해결할 수 있었다.

아이디어를 떠올리지 못하면 silver 4 이상의 난이도를 가질 수 있는 문제 같다.