[문제 출처 : Codechef] 애인의 생일날이 되었습니다. 멋진 케잌을 선물해 줘야겠다고 생각한 이 사람은 숫자(0~9)로 이루어진 촛불을 받았습니다. 촛불에 불을 붙이던 그는 갑자기 궁금함이 생겼습니다.

“내가 가지고 있는 촛불들로 표현할 수 없는 가장 작은 자연수는 무엇일까?”

먼저, 자릿수가 많아질수록 숫자는 커지게 됩니다. 따라서 자릿수가 최소가 돼야 할 것입니다. 그러면 결과적으로 (가장 적은 개수의 초 + 1)개의 초로 만든 수가 가장 작은 자연수가 되겠죠?

그럼 어떻게 하면 list에서 최소값을 뽑아낼 수 있을까요? min함수를 사용하면 쉽게 얻을 수 있습니다.

>>> min([3,5,7,1])
1

그런데 우리는 개수만 필요한 것이 아니라, 해당 최소 값이 어떤 숫자의 초인지를 알아내는 것이 중요합니다. 특히나, tie(동점자)가 있을 경우, 가능한 작은 숫자의 초를 골라야 하겠죠? 이렇게 list에 존재하는 가장 첫 원소의 값의 index를 뽑아주는 함수가 .index()함수입니다.

>>> [3,5,7,1,1].index(1)
3

Index가 0부터 시작한다는 건 다들 아시죠? :)

마지막으로 구현하기 전에 명심하셔야 할 것이 있습니다. 자연수는 ‘0’이 아닌 수로 시작해야 하기 때문에, 만약에 ‘0’ 촛불이 가장 적은 개수일 경우는 문제가 생길 것입니다. 따라서 이 경우엔 ‘0’의 개수 + 1개의 0을 가지고 맨 앞에 0이 아닌 가장 작은 수인 1을 붙여주시면 될 것입니다.

또 하나 명심하셔야 할 것은, ‘0’의 개수가 최소값으로 tie가 될 경우, 이 경우는 0이 아닌 수의 초를 선택해 주셔야 합니다.(왜냐하면 ‘0’으로 수를 만들 경우 앞에 ‘1’을 붙여줘야 하기 때문에 오히려 수가 더 커지기 때문입니다.)

그럼 이제 이 모든 걸 고려해서 코드를 짜 보겠습니다.

def minAgeNotRepresented(candles):
    minNum = min(candles[1:]) #'0'을 제외한 '1'~'9'까지의 촛불 중 개수의 minimum을 뽑습니다.
    minInd = candles[1:].index(minNum) + 1 #가장 적은 개수를 가진 초가 어느 초인지 파악합니다.
    
    # 촛불 '0'의 경우 0으로 수가 시작할 수는 없으므로 가장 작은 수인 '1'을 붙이고 
    # '0'을 현재 가진 수 보다 하나 더 많게 해서 최소 양의 정수를 만듭니다.
    if minNum > candles[0]:
        return '1' + '0'*(candles[0]+1)
    
    # 만약 '0'이 아닌 다른 수의 촛불이 가장 적으면,
    # 그냥 그 촛불의 개수보다 하나 더 많은 개수로 만들어진 수가 최소가 됩니다.
    else:
        return str(minInd)*(minNum+1)

그럼 마지막으로 결과를 확인해 보겠습니다.

>>> print minAgeNotRepresented([2, 1, 1, 4, 0, 6, 3, 2, 2, 2])
4
>>> print minAgeNotRepresented([0, 1, 1, 1, 1, 1, 1, 1, 1, 1])
10
>>> print minAgeNotRepresented([2, 2, 1, 2, 1, 1, 3, 1, 1, 1])
22