leetcode - largest-number (삽입정렬의 특성)

처음 문제를 봤을 때, 맨 앞자리가 큰 것을 우선 앞에 가져와야겠다 라는 것은 단순하게 생각할 수 있는데, 그 다음을 비교하는 과정이 잘 안 그려졌다. 고민을 하다가, 그래 한 번에 다 해결하지 못한다면, 작게 시도할 수 있는 첫 작업이라도 먼저 해보자 싶었다.

그래서 우선 "앞자리가 큰 아이들부터 앞쪽에 다 모여!" 이런 식으로 해놓았다.

 

그러고 나니, 이제는 앞에 자리가 큰 친구들끼리는 서로 앞 뒤를 바꾸어 조합해보면서 더 큰 경우가 되도록 스왑해주면 되겠다고 생각했다.

그래서 결국 나는 두 번의 정렬을 사용하게 되었는데, 사실 문제를 푸는 데 첫 번째 정렬은 꼭 필요하지는 않다.

그래도 문제가 복잡하게 느껴지던 차에 조금 더 도움을 준 친구니까 나에게는 살짝 고마운 단계였다...!ㅎㅎㅎ 

 

그래도 불필요한 코드는 지우는게 낫겠다 싶어서 1차 정렬을 지우고 다시 돌려보았다.

이렇게 해보니까 (나한테는) 신기한 사실을 발견했는데,

1단계의 예비(?)적 정렬을 시키는 코드로 돌렸을 때가 더 빨랐다는 것..!

이 상황을 마주하고 나니까, 전에 나동빈님 영상에서 배웠던 사실이 기억이 났다.

삽입정렬은 필요시에만 스왑하기 때문에, 거의 정렬된 상태의 자료일 경우 그 속도가 더 빠르다는 것이었다.

심지어 "거의 정렬되어 있으면 퀵정렬보다도 삽입정렬이 빠를 수 있다"라고 했었는데,

정말 정렬된 상태에서 삽입정렬의 처리 속도가 빠르구나 싶었다.

삽입정렬의 특성을 조금 더 배우게 된 계기가 되었다:)

 

 

0. 문제

1. 코드

class Solution(object):
    def largestNumber(self, nums):

        # 0만 들어왔을 경우에 대한 예외 처리
        # ([0,0] -> output: "0" 이어야 한다고 함)
        if max(nums) == 0:
            return "0"

        # 일단 맨 앞자리 숫자가 큰것들을 앞쪽으로 둔다.
        str_nums = list(map(str, nums))
        str_nums.sort(key=lambda x: x[0], reverse=True)

        # 이제 삽입 정렬을 사용해서, 인접한 두 수를 바꾸어 조합했을 때 더 큰 수가 나오도록
        # 필요하다면 스왑해간다.
        for cur in range(1, len(str_nums)):
            # 두번째 수부터 비교 시작
            for delta in range(1, cur + 1):
                # 비교대상이 될 친구는 자기보다 바로 앞(delta = 1)일때부터 맨 첫 번째아이([0])까지 가야 하니까
                # (물론 그렇게 앞으로 비교대상이 진행한다면, 비교가 될 나도 계속 스왑으로 인해 하나씩 앞으로 가는 것이고)
                # 그러면 원래 나의 값은 [cmp +1]의 인덱스로 가리켜 볼 수 있음.
                cmp = cur - delta
                # <앞선 친구 - 나>를 조합해서 만든 수의 크기와, <나-앞서있던친구> 조합으로 만든 수의 크기를 비교해봄!
                # 만약 순서를 바꿔야 더 크다면, 바꾸기!
                if int(str_nums[cmp] + str_nums[cmp + 1]) < int(str_nums[cmp + 1] + str_nums[cmp]):
                    str_nums[cmp], str_nums[cmp + 1] = str_nums[cmp + 1], str_nums[cmp]
                else:
                    break

        # 하나의 문자열로 제출
        answer = "".join(map(str, str_nums))
        return answer