글 읽기 - [파이썬] 시간 복잡도 질문 드리고 싶습니다!

gsmin2020 2년 전 1

목표로 하는 채널 번호에서 +1, -1을 더해주며 만약 리모컨의 버튼을 눌러 갈 수 있는 채널이라면 "+" or "-"를 눌러야 하는 횟수를 더해주며 종료하고 마지막에는 "+" or "-"만 눌러서 갔을 때와 비교하여 최솟값을 답으로 출력하는 코드를 집합을 사용하여 짜봤습니다.

문제의 예제까지는 오랜 시간이 걸리지 않고 잘 출력 하는데 막상 답 제출만 하면 시간 초과가 시작부터 발생해서 단지 while문 반복 횟수때문에 일어난건지, 집합과 집합끼리의 연산을 수행하여 while 사이클 내부에서 시간을 많이 잡아먹는지 명확하게 알고 싶습니다...!

goal = int(input())
num_broken = int(input())

if (num_broken == 0):
    broken_lst = set()
else:
    broken_lst = set(input().split())

button_lst = set(i for i in range(10)) - broken_lst
res = 0

while True:
    a = goal + res
    b = goal - res
    goal_u = set(str(a))
    goal_d = set(str(abs(b)))

    if goal_u & button_lst == goal_u:
        res += len(str(a))
        break
    elif goal_d & button_lst == goal_d:
        res += len(str(b))
        break

    res += 1

print(min(res, abs(goal-100)))

bamgoesn 2년 전 1

이를 고친다고 무조건 정답이 나올지는 확인 안 해봤지만, 어딘가에 사소한 실수 하나를 하셨습니다.

아래 예시로 테스트해보세요.

bamgoesn 2년 전 1

아래 예제로도 테스트해보세요

100
10
0 1 2 3 4 5 6 7 8 9

정답
0

gsmin2020 2년 전 2

@bamgoesn

덕분에 다시 한 번 생각해 볼 수 있었습니다... 감사합니다!

< 수정사항 >

1. 버튼을 눌러서 갈 수 있는 채널이 없으면 무한 루프 도는 것을 수정하였습니다.

2. 목표 채널과 같은 채널 수만큼 떨어져 있는 두 채널이 나올 경우 버튼을 더 적게 눌러 갈 수 있는 채널을 선택했습니다.

ex) IN: 1555 OUT: 670

0 1 3 4 5 6 7 9

같은 거리 채널 2개: 888, 2222

여기선 888을 선택하고 667번 "+" 버튼을 누르는 것이 최선의 선택 667 + len(888) = 670

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[파이썬] 시간 복잡도 질문 드리고 싶습니다!

gsmin2020 2년 전 1

bamgoesn 2년 전 1

bamgoesn 2년 전 1

gsmin2020 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말