백준 22942 데이터 체커 - [알고리즘] [kotlin]

문제 내용

문제 분석

1. N개의 원 정보가 주어진다. (x좌표, 반지름)

2. 각 원은 x축 위에 있는 것이 보장된다.

3. 모든 원에 대해 서로 교점이 존재해서는 안된다.

 

아이디어

실패한 아이디어

논리 아이디어

1. 교점이 존재하는지에 대한 판단을 해야 한다.

2 y좌표는 모두 0 으로, 각 원의 x좌표와 반지름만으로 판단이 가능하다.

3. 임의의 두 원에 대해 교점이 존재하지 않으려면 다음 2가지 경우가 있다.

  a. 한 원이 다른 원에 포함되고, 내접하지 않는다.

  b. 두 원이 포함관계가 없고 외접을 포함한 교차점이 없다.

4. a의 경우 두 원의 "중심 사이의 거리" + "작은 원의 반지름"이 큰 원의 반지름보다 작아야 한다.

5. b의 경우 중심 사이의 거리가 각 반지름의 합보다 커야 한다.

 

시간 아이디어

6. N은 최대 200000이고 제한시간은 1초이다.

이때, BruteForce하게 모든 경우를 검사하면 제한시간을 통과하지 못할 것이다.

(약 O(N^2)이고, 1억번의 연산을 훌쩍 넘는다.)

7. 현재의 검사 방식으로는 평균적인 시간을 줄일 수는 있어도 worstCase의 시간 복잡도를 줄일 수 없기 떄문에 검사 방법을 바꾼다.

 

 

 

1. x축 위에만 원들이 있기 때문에 우리는 원의 시작점, 끝점을 알 수 있다.

 

2. 2000000 크기의 배열을 만들어 각 원들의 시작점 끝점을 기록할 수 있다.

// 이때 모든 원에 대해 각각 검사한다면 O(N^2)의 시간 복잡도를 갖기 때문에 각각 검사할 수 없다.

 

3. 만약 어떤 원들이 서로 외부에 있고 만나지 않는다면, 한 원이 열리고 닫힌 후에 다른 원이 열리게 된다.

또한 포함관계인 원이 있고 만나지 않는다면, 큰 원이 열린 후에 작은 원이 열리게 되지만 작은 원이 먼저 닫히게 된다.

즉, 닫히지 않은 원이 여러개 있을 때, 먼저 열린 원이 나중에 열린 원보다 먼저 닫히게 되면 교점이 2개 생긴다.

외접 또는 외접의 경우 같은 x좌표를 공유한다.

 

4. 각 원을 원의 번호, 시작점인지 끝점인지로 이루어진 정보(구조체)로 변환한다.

- 이때 베열에 바로 넣으며 같은 점이 있다면 외접, 내접으로 판단한다.

 

5. 괄호문제와 유사하게, stack을 이용한다.

- 시작점이 들어오면 push

- 끝점이 들어오면 가장 위에 있는 시작점과 같은 원인지 판단 후 pop

 

풀이

import java.util.LinkedList

fun main(){

    data class CircleInfo(val circleNum: Int = -1, val isStart: Boolean = false)

    fun getCircleInfos(): Array<CircleInfo>? {
        val br = System.`in`.bufferedReader()
        val n = br.readLine().toInt()
        // 같은 x좌표 검사 및 시작점, 끝점으로 정보 변환
        // 만약 내접, 외접 케이스가 있다면 null을 반환
        return Array(2020000){ CircleInfo() }.apply {
            for(i in 0 until n) {
                val info = br.readLine().split(' ').map { it.toInt() }
                // -좌표는 나타낼 수 없으므로 100만씩 더해서 표현한다.
                // 반지름도 고려하여 10000을 추가로 더한다.
                val start = info[0]-info[1] + 1010000
                val end = info[0]+info[1] + 1010000
                if(this[start].circleNum != -1) return null
                if(this[end].circleNum != -1) return null

                this[start] = CircleInfo(i, true)
                this[end] = CircleInfo(i, false)
            }
        }
    }

    // 시작, 끝점으로 변환된 배열을 받는다.
    // 외접, 내접의 경우가 있어 null이 반환된 경우 "No"를 출력하고 종료한다.
    val circleInfos = getCircleInfos() ?: run {
        println("NO")
        return
    }

    val stack = LinkedList<CircleInfo>()
    for( cInfo in circleInfos ) {
        if(cInfo.circleNum == -1) continue
        if(cInfo.isStart) {
            stack.addLast(cInfo)
        } else {
            val top = stack.removeLast()
            // 가장 최근에 열린 원과 매칭되지 않는 경우 교점이 2개 생긴 경우임
            if(top.circleNum != cInfo.circleNum) {
                println("NO")
                return
            }
            // 매칭되는 경우 계속 진행
        }
    }

    // 모든 검사를 통과한 경우 YES
    println("YES")
}