leetcode 75(구현), 14(구현), 1,167(2SUM), 15(3SUM)

75 https://leetcode.com/problems/sort-colors/

 

정렬을 구현하는 문제이다. 라이브러리 함수를 쓰면 안 되고, 되도록 constant한 공간만 사용하고 in-place로 입력으로 주어진 배열 자체를 바꾸라고 한다. counting sort로도 해보라고 한다. 

class Solution(object):
    def sortColors(self, n):
        n0,n1,n2 = 0,0,0
        for nn in n:
            if nn == 0:
                n0 += 1
            elif nn == 1:
                n1 += 1
            else:
                n2 += 1
        n[:n0] = [0]*n0
        n[n0:n0+n1] = [1]*n1
        n[n0+n1:n0+n1+n2] = [2]*n2

discussion에 있는 흥미로운 구현 방법들을 더 적어본다.

 

1. https://leetcode.com/problems/sort-colors/discuss/26472/Share-my-at-most-two-pass-constant-space-10-line-solution

0,1,2 3개의 숫자만 있으므로 0은 최대한 왼쪽으로, 2는 최대한 오른쪽으로, 1은 중간에 남겨놓는다. 그러면 알아서 정렬이 된다.

 

2. https://leetcode.com/problems/sort-colors/discuss/26500/Four-different-solutions

의 2번째 답.

직접 돌려보면 알겠지만 2를 최대한 오른쪽으로, 1을 그 다음, 0은 가장 왼쪽으로 밀려날 수 밖에 없도록 짜놨다.

 

 

14 https://leetcode.com/problems/longest-common-prefix/

가장 긴 prefix를 구하는 문제이다. 그냥 구현을 하면 되긴 하는데....

class Solution(object):
    def longestCommonPrefix(self, strs):
        if strs == ['']:
            return ''
        strs = map(list, strs)
        ret = ''
        while True:
            if any(not s for s in strs):
                break
            s = [s.pop(0) for s in strs]
            if len(set(s)) == 1:
                ret += s[0]
            else:
                break
        return ret

너무나도 깔끔하게 정리한 코드가 있다.

 

https://leetcode.com/problems/longest-common-prefix/discuss/354496/Python3-list(zip(*str))

 

1 https://leetcode.com/problems/two-sum/

167 https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

 

딕셔너리에 값을 저장 후 target-값이 딕셔너리에 있는지 판별하면 된다.

class Solution(object):
    def twoSum(self, nums, target):
        d = {n:i for i, n in enumerate(nums)}
        #print(d)
        for i, n in enumerate(nums):
            if target - n in d:
                return [i+1, d[target - n]+1]

15 https://leetcode.com/problems/3sum/

숫자를 한개씩 반복하면서 해당 숫자에 대해서 2 pointer로 합이 0이 되는 것들을 저장한다.

class Solution(object):
    def threeSum(self, nums):
        nums.sort()  # 순서상관없이 값만 찾아내는것이므로 정렬해서 찾는다.
        #print(nums)
        ret = []
        len_nums = len(nums)
        i = 0
        while i < len_nums:  # i는 고를 3개의 숫자중에 가장 왼쪽의 기준이 될 숫자..
            if i > 0 and nums[i-1] == nums[i]:  # i-1에서 이미 동일한 숫자를 대상으로 했으면 그냥 지나감. i == i+1로 코드를 바꿔서 돌려보거나 이 조건문을 없애보면 이해할수있다.
                i += 1
                continue
            l, r = i+1, len_nums-1  # 맨 왼쪽 i를 기준으로 그다음 l, r은 i이후의 숫자.
            while l < r:
                v = nums[i] + nums[l] + nums[r]
                if v == 0:  # 합이 0이면 
                    ret.append([nums[i], nums[l], nums[r]])  # 저장하고
                    while l < r and nums[l] == nums[l+1]:  # 같은 숫자가 안나올때까지 밀어줌
                        l += 1
                    while l < r and nums[r] == nums[r-1]:  # 같은 숫자가 안나올때까지 밀어줌.
                        r -= 1                            
                    l += 1  # 내부에 또다른 합이 0이나오는 세 숫자가 있을수있으므로 답이 나온 후에도 조여줌.
                    r -= 1
                elif v < 0:  # 0보다 작으면 작은 값을 더 크게,
                    l += 1
                else:  # 0보다 크면 큰 값을 더 작게.
                    r -= 1
            i += 1
        return ret