[백준] 22942 데이터 체커 python

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

22942번: 데이터 체커

 

주어진 데이터가 조건에 맞는지 확인하면되는 문제이다.

처음 시도한건 브루트포스이다. 

추가할때 이미 추가된 원들과 비교하면서 들어갈수 있을때 추가하는 방식으로 풀었는데 시간초과가 났다.

'''
boj 22942
wrong answer
'''
# import sys; input = sys.stdin.readline
def check(cur, circles):
    x, r = cur
    for xx, rr in circles:
        # 동심원인데 반지름까지 같은 경우
        if x == xx and r == rr:
            return False

        # 한 점에서 만나는 경우
        d = abs(x - xx) # 중심 사이 거리
        if r + rr == d or abs(r - rr) == d:
            return False

        # 두 점에서 만나는 경우
        if abs(r - rr) < d < r + rr:
            return False

    return True

def main():
    N = int(input())
    circles = set()
    answer = "NO"
    for _ in range(N):
        x, r = map(int, input().split())

        # 1 check current circle
        chk = check((x, r), circles)
        # 2 break or save
        if not chk:
            break
        circles.add((x, r))
    else:
        answer = "YES"
    print(answer)


if __name__ == "__main__":
    main()

그래서 모든 원을 추가한뒤에 한번 체크하는 경우도 했는데 시간초과가 났다.

'''
boj 22942
wrong answer
'''
# import sys; input = sys.stdin.readline
from itertools import combinations

def check(circles):
    for (x, r), (xx, rr) in combinations(circles, 2):
        # 동심원인데 반지름까지 같은 경우
        if x == xx and r == rr:
            return False

        # 한 점에서 만나는 경우
        d = abs(x - xx) # 중심 사이 거리
        if r + rr == d or abs(r - rr) == d:
            return False

        # 두 점에서 만나는 경우
        if abs(r - rr) < d < r + rr:
            return False

    return True

def main():
    N = int(input())
    circles = [tuple(map(int, input().split())) for _ in range(N)]

    if check(circles):
        print("YES")
    else:
        print("NO")


if __name__ == "__main__":
    main()

브루트포스를 사용하면 O(N^2)이라서 1초가 넘게 된다.(푼지 한시간만에 알게되었다 )

 

그 다음은 스택을 사용한 풀이이다. 

모든 원을 추가할때 중심점이 아니라 중심점에서 반지름만큼 떨어진 값을 추가해야 스택을 사용할수 있었다.

(힌트를 보니 스택이 써있었고 스택방식을 어떻게 사용해야하는지 꽤 오랫동안 고민했다)

 

# import sys; input = sys.stdin.readline
from bisect import insort, bisect

def check(circles, start=None, end=None):
    if start is None: start = 0
    if end is None: end = len(circles)

    s = []
    for i in range(start, end):
        c = circles[i]
        if not s:
            s.append(c)
            continue
        ppos, pbra, pnum = s[-1]
        pos, bra, num = c
        if ppos == pos:
            return False
        if pnum == num:
            s.pop()
            continue

        if not bra:
            s.append(c)
        else:  # if bra == ']':
            return False

    return True


def main():
    N = int(input())
    circles = []
    answer = "YES"
    for i in range(N):
        x, r = map(int, input().split())
        circles.append((x - r, False, i))
        circles.append((x + r, True, i))
    circles.sort()

    if not check(circles):
        answer = "NO"
    print(answer)


if __name__ == "__main__":
    main()

 

여기가 설명을 잘해둔거같다.

https://ongveloper.tistory.com/420

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