[Seop's의 코드풀이] 백준 3649 로봇 프로젝트 - Python

이번에 풀어볼 문제는 백준 3649번 '로봇 프로젝트'라는 문제입니다.

문제는 다음과 같습니다.

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

3649번: 로봇 프로젝트

제한시간이 5초나 되는만큼 시간복잡도를 고려하지 않는다면 시간초과가 날 문제입니다.

저는 최대한 시간을 줄이기 위해 딕셔너리를 사용했습니다. 

딕셔너리를 사용한 이유는 특정 값을 찾고자 할때 key in dict 형식을 사용할 경우 O(1)이기 때문입니다.

2개의 딕셔너리를 활용하였는데 내부의 구조는 다음과 같이 설정했습니다.

 

이렇게 진행하면 정답을 구할 적에 Lego의 Value[key][0]에 해당하는 값이 Lego에 있다면 정답일 수 있습니다.

또한 정답이 많을경우 Answer[key][1]번째 값을 기준으로 내림차순으로 정렬한 후 정답을 출력하면 됩니다.

 

이번 문제를 풀면서 주의해야 할 점이 몇가지 있었습니다. 

1. 입력은 여러개의 케이스로 이루어져 있지만 몇가지인지 주어지지 않습니다. 즉 빈 입력이 들어올때 까지 반복해야 합니다.

2. 동일한 레고 조각 2개로 구멍을 매울 수 있을 가능성을 고려해야 합니다. 이것 때문에 Lego의 Value에 동일한 조각의 수를 저장했습니다.

Ex) 2cm의 구멍을 1cm 두개로 막을 수 있지만 1cm 조각이 2개 이상 있어야 합니다.

 

전체적인 코드는 다음과 같습니다. 질문과 피드백은 언제나 감사드립니다.

import sys
input = sys.stdin.readline

def soluction() :
    isInput = input().rstrip()
    if isInput == '' :
        return False
    x = int(isInput) * 10000000
    n = int(input())
        

    lego = dict()
    answer = dict()

    for _ in range(n) :
        k = int(input())
        if k not in lego :
            if x - k >= 0 :
                lego[k] = [x - k, 1]
        else :
            lego[k][1] += 1
    
    for k in lego.keys() :
        if lego[k][0] in lego :
            if k <= lego[k][0] :
                l1 = k
                l2 = lego[k][0]
            else :
                l1 = lego[k][0]
                l2 = k
            if int(x/2) == k :
                if lego[k][1] < 2 :
                    continue
            answer[l1] = [l2 , abs(l1- l2)]
    
    if len(answer) == 0 :
        print("danger")
    else :
        result = sorted(answer.items(), key= lambda x : -x[1][1])
        print("yes", result[0][0], result[0][1][0])
    return True

if __name__ == "__main__":
    isRun = True
    while isRun :
        isRun = soluction()