학습 주제
정렬법을 만들어 가장 큰 수 만들기

학습내용

코드 구현 후 복잡도까지 살펴보기

def solution(numberes):
    numbers = [str(x) for x in numbers]
    # lambda = x라는 원소가 주어지면 그 원소에 4를 곱하고,
    # 주어진 조건에 따라 4자리까지만 필요하므로,
    # [:4] 로 슬라이스 해줌. 이 슬라이스는 처음알았음.
    # 문자열 내 숫자는 앞자리부터 작은 순으로 오름차순 됨.
    numbers.sort(key = lambda x: (x * 4)[:4], reverse=True)
    answer = ''.join(numbers)
    return answer

그런데 정확성에서 11번째 케이스를 실패하였음. -> 제한사항 다시 확인
numbers의 원소는 0이상 1000이하. 00,000,0000은 0으로 리턴해야함.

def solution(numberes):
    numbers = [str(x) for x in numbers]
    # lambda = x라는 원소가 주어지면 그 원소에 4를 곱하고,
    # 주어진 조건에 따라 4자리까지만 필요하므로,
    # [:4] 로 슬라이스 해줌. 이 슬라이스는 처음알았음.
    # 문자열 내 숫자는 앞자리부터 작은 순으로 오름차순 됨.
    numbers.sort(key = lambda x: (x * 4)[:4], reverse=True)

        # 정확성 테스트 11 보완
    if numbers[0] == '0' :
        answer = '0'
    else:
        answer = ''.join(numbers)
    return answer

모든 테스트를 통과하는 것을 확인하였고, 이로써 우리는 마지막 케이스의 경우, 0, 0, 0 등 0만 주어진 경우였음을 알 수 있다. 일종의 예외적 처리로 보인다. 일전에 풀었던 답안에서

	answer = str(int(numbers))

형식이었는데, 왜 저렇게 다시 숫자로 만들고, 다시 문자열로 바꿔놨는지 이해를 못했었다. 저렇게 int로 하면 0000이 0으로 바뀌고, 이는 다시 문자열로 바꿈으로써 정답으로 만드는 작업이었다. 참 깔끔하게 풀었다고 생각한다.

복잡도

리스트 컴프리헨션: numbers의 n 수에 비례하는 복잡도 O(n)
전체를 지배하는 것은 정렬부: O(nlogn)
''.join: n수에 비례 O(n)

파이썬 내에 있는 sort 알고리즘은 굉장히 성능이 좋음.

but, 이 알고리즘은 정렬을 하지 않고선 문제를 풀 수 없음. 문제는 정렬을 해야지만 최적으로 풀 수 있는 문제이다. 결과적으로 이 문제를 지배하는 건 정렬이고, 최종 시간 복잡도는 O(nlogn)이 된다.

어려웠던 점

마지막 0, 0, 0 이거를 문제를 풀다가 막혔을 때 바로 생각해내기 어려웠다.