[스위프트][백준 22942][💛골드 4] 데이터 체커 (스택)

🧞‍♂️ 난이도

💛 골드 4

🧞‍♂️ 문제

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

🧞‍♂️ 풀이 방법

정렬 과 스택을 이용해서 풀 수 있습니다.

이 문제는 그림을 그려보면 정렬 아이디어가 떠오를 수 있습니다.

문제에서 주어진 테스트 케이스를 그림으로 그려보면 다음과 같습니다.

이때 각 원이x축과 만나는 양쪽 교점들을 배열에 담아서 정렬 시키면 다음과 같습니다.

[1번 원 시작점(1), 2번 원 시작점(2), 2번 원 끝점(4), 3번 원 시작점(5), 3번 원 끝점(7), 1번 원 끝점(9), 4번 원 시작점(13), 4번 원 끝점(15)]

“YES” 조건이라면 정렬을 해도 원끼리 교점이 생기지않는다는걸 발견할 수 있습니다.

여기서부터 우리가 잘 아는 괄호 짝 맞추기 문제처럼 스택을 이용해서 해결할 수 있습니다.

1. 모든 점들에 대해서 하나씩 스택에 넣고
2. 열린 괄호와 닫힌 괄호의 짝을 맞추듯이 원의 시작점과 끝점의 짝을 맞춰가며 스택에서 꺼내면 됩니다.
3. 단, “YES”의 조건이 충족되려면 스택의 마지막 원소는 항상 특정 원의 시작 점일텐데, 그 다음으로 들어오는 점이 다른 원의 끝나는 점이라면 그건 원들이 교차가 됐다는 뜻이므로 이때 “NO” 를 출력하면 됩니다.

🧞‍♂️ 스위프트 코드

import Foundation

struct Point {
    let x: Int
    let id: Int
    let side: String // "Left" or "Right" ( 원의 시작점 또는 끝점)
}

func solution(_ points: [Point]) {
    var stack: [Point] = []

    for point in points {
        if !stack.isEmpty {
            if stack.last!.id == point.id { // 짝이 맞춰졌기 때문에 pop()
                stack.removeLast()
                continue
            } else if point.side == "R" { // 다른 원의 끝 점이면 교점이 생겼다는 뜻
                print("NO")
                exit(0)
            }
        }
        stack.append(point)
    }

    print("YES")
}

let N = Int(readLine()!)!
var points: [Point] = []

for i in 0..<N {
    let XR = readLine()!.split(separator: " ").compactMap { Int($0) }

    points.append(Point(x: XR[0] - XR[1], id: i, side: "L"))
    points.append(Point(x: XR[0] + XR[1], id: i, side: "R"))
}
points.sort(by: {
    $0.x < $1.x
})

solution(points)

---

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기