[TIL_Carrotww] 105 - 23/03/22

📝Carrotww의 코딩 기록장

🧲 python algorithm interview

🔍 leetcode 179 Largest Number - medium

• 삽입정렬을 이용한 풀이

class Solution:
    def largestNumber(self, nums: List[int]) -> str:

        def swap(a, b):
            if str(a) + str(b) < str(b) + str(a):
                return True
            return False

        i = 1
        while i < len(nums):
            j = i
            while j > 0 and swap(nums[j-1], nums[j]):
                nums[j], nums[j-1] = nums[j-1], nums[j]
                j -= 1
            i += 1

        return str(int(''.join(map(str, nums))))

• 더 빠르고 python을 이용한 풀이

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        temp = list(map(str, nums))

        temp.sort(key=lambda x:x*10, reverse=True)

        result = ''

        for i in temp:
            result+=str(i)

        if int(result) == 0:
            return "0"

        return result

python에서 문자열 대소 비교를 할때는 아스키코드로 하나하나 비교해가기 때문에 9199와 92를 비교하면 92가 더 크다고 나온다.
그 점을 이용하여 각 요소가 10의 9승인점을 이용하여 푼 것이다

🔍 Leetcode 56 Merge Intervals - medium

요즘 알고리즘 테스트를 많이 봤는데 이런 문제들이 1, 2번 문제로 자주 나오는것 같다

• 첫 번째 풀이

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        result = []
        intervals.sort(key=lambda x:x[0])

        result.append(intervals[0])
        pre_val = intervals[0][1]

        for i in range(1, len(intervals)):
            if pre_val >= intervals[i][0]:
                if pre_val >= intervals[i][1]:
                    pass
                else:
                    result[-1][1] = intervals[i][1]
                    pre_val = intervals[i][1]
            else:
                result.append(intervals[i])
                pre_val = intervals[i][1]

        return result

• 좀 더 깔끔한 풀이

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        result = []
        intervals.sort(key=lambda x:x[0])

        result.append(intervals[0])
        pre_val = intervals[0][1]

        for i in range(1, len(intervals)):
            if pre_val >= intervals[i][0]:
                result[-1][1] = max(pre_val, intervals[i][1])
                pre_val = result[-1][1]
            else:
                result.append(intervals[i])
                pre_val = intervals[i][1]

        return result

요즘 면접을 몇개 보느라 면접준비에 알고리즘을 풀긴 풀지만 예전만큼 많이 풀지는 못해
짜잘하게 푼것들은 못올렸었다.
이제 다시 꾸준히 풀어야겠다!