백준 22942 데이터 체커 Kotlin (스택)

문제 출처 : https://www.acmicpc.net/problem/22942

22942번: 데이터 체커

문제

원 이동하기 2 문제를 만들고 만든 데이터가 문제의 조건에 맞는지 확인하는 코드를 작성해야한다.

해당 문제의 데이터는 아래 조건들을 만족해야한다.

1. 모든 원의 중심 좌표는 x축 위에 존재해야 한다.
2.  N개의 원 중 임의의 두 원을 선택했을 때, 교점이 존재하지 않아야 한다. 즉, 하나의 원이 다른 원 안에 존재하거나 외부에 존재한다.

데이터 형식은 원의 개수 N이랑 각 원의 중심 x좌표, 원의 반지름 r만 주어진다. 따라서, 2번 조건을 만족하는지만 확인하면 된다.

주어진 데이터가 해당 조건을 만족하는지 확인해보자.

입력

첫 번째 줄에는 원의 개수 N이 주어진다.

두 번째 줄부터 N+1번째 줄까지 원의 중심 x좌표, 원의 반지름 r이 공백으로 구분되어 주어진다.

출력

데이터가 조건에 맞는다면 YES, 조건에 만족하지 않는다면 NO를 출력한다.

제한

•  2≤N≤200,000
•  −1,000,000≤x≤1,000,000
•  1≤r≤10,000
•  x,r은 정수

힌트

알고리즘 분류

• 자료 구조
• 정렬
• 기하학
• 스위핑
• 스택

시간 제한

• Java 8: 2 초
• Python 3: 2 초
• PyPy3: 2 초
• Java 8 (OpenJDK): 2 초
• Java 11: 2 초
• Kotlin (JVM): 2 초
• Java 15: 2 초

풀이

2021.07.04 - [알고리즘 문제 풀이/프로그래머스] - 프로그래머스 괄호 회전하기 kotlin (스택)

2021.06.21 - [알고리즘 문제 풀이/프로그래머스] - 프로그래머스 짝지어 제거하기 c++(스택)

 

스택 문제로 잘 알려진 괄호 문제, 짝지어 제거하기 문제 등으로 풀 수 있다.

스택 문제는 대부분 결이 비슷하다.

 

이 문제는 주어진 x,r을 이용해서 start, end를 여는 괄호, 닫는 괄호로 생각하면 된다.

대신 하나의 원마다 넘버링을 해서 다른 원들과 구분해 준다.

모든 원의 중심은 x축에 있으니 y는 0으로 동일하다. 따라서 x-r이 원의 맨 왼쪽 점, x+r이 원의 맨 오른쪽 점이 된다.

x-r, open, 원 번호

x+r, close, 원 번호 

형태로 모두 저장한 후, 점들의 좌표(x)를 기준으로 오름차순 정렬한다.

이후 스택에 넣으면서 같은 원이 들어오면 pop,

다른 원이 들어오는데 이전 원이 open 상태이고, 들어올 원이 close 상태이면 두 원이 겹치는 구간이 발생하므로 NO를 출력한다.

이러한 스택 풀이는 정답을 푸는 과정에 O(N)의 시간 복잡도라는 점이 이점인데, 이 문제에선 앞에 x좌표를 정렬하기 때문에 O(NlogN) + O(N), 최종적으로 O(NlogN)이라 볼 수 있다.

코드

import java.util.*
val br = System.`in`.bufferedReader()

data class Node(val x : Int, val isOpen : Boolean, val num : Int)

fun main() = with(System.out.bufferedWriter()){

    val n = br.readLine().toInt()
    val arr = Array(n*2){Node(0,false,0)}
    var idx=0
    for(i in 0 until n){
        val tk = StringTokenizer(br.readLine())
        val x = tk.nextToken().toInt()
        val r = tk.nextToken().toInt()
        arr[idx++] = Node(x-r,true,i)
        arr[idx++] = Node(x+r,false,i)
    }
    arr.sortBy { it.x }

    val stk = Stack<Node>()

    for(next in arr){

        if(stk.empty()){
            stk.push(next)
        }
        else{
            val cur = stk.lastElement()
            if(cur.num == next.num){
                stk.pop()
            }
            else{
                if(cur.isOpen && !next.isOpen){
                    write("NO")
                    close()
                    return
                }
                stk.push(next)
            }
        }
    }
    write("YES")

    close()
}