백준 1107 리모컨

문제

리모컨

리모컨 버튼 클릭 최소 횟수를 구하자

난이도 : Gold5

---

풀이

1. 부서진 키를 제외하고 사용 가능한 모든 키를 구함
2. 1에서 구한 키를 클릭하는 횟수를 구해 최소값 계산

---

코드

import sys


def main():
    N = int(sys.stdin.readline())
    M = int(sys.stdin.readline())
    if M != 0:  # M이 존재할 때만 broken 인자 받을 수 있음
        broken = list(sys.stdin.readline().split())
    else:
        return abs(N-100) if 98 <= N <= 103 else len(str(N))  # 98 ~ 103은 +, - 키로 이동하는 것이 더 적은 횟수
    
    if M == 10:  # 모든 키가 부서졌을 때
        return abs(N-100)  # +, - 키만 동작하므로 N에서 뺀 값 return

    numbers = [str(i) for i in range(0, 1000000)]
    candidates = [i for i in numbers if not any(j in i for j in broken)]  # 사용 못하는 숫자가 포함되지 않은 숫자만 추출

    clicks = [abs(int(i)-N) for i in candidates]  # 전체에서 target 값을 다 뺌
    min_ = min(clicks)  # + 또는 - 클릭 횟수의 최솟값
    min_index = clicks.index(min_)
    num_len = len(candidates[min_index])  # 채널을 누르는 클릭 횟수
    opt = min_ + num_len

    if abs(N-100) > opt:
        return opt
    else:
        return abs(N-100)


print(main())

        

---

결과

통과는 됐지만 메모리 할당과 시간이 상당히 크게 소요됐다. 좀 더 효율적으로 알고리즘을 짤 필요가 있다고 느꼈다.

any 함수

인자로 받은 반복 객체가 하나라도 참이면 True, 모두 거짓이면 False 반환

• any(j in i for j in broken)

  • broken 리스트 내 모든 요소 j에 대해 j in i 를 수행해 하나라도 True면 True