greentea31's Note

https://leetcode.com/problems/product-of-array-except-self/

풀이 과정

배열을 입력받고, 각 배열의 원소에 대해 자기 자신을 제외한 나머지 원소의 곱의 배열을 구하는 문제이다.

문제를 읽고 나서 바로 드는 생각이라면 배열의 전체 원소를 곱해놓고 저장한 뒤, 각 배열의 원소를 나누면서 저장하는 방법일 텐데 이 방법은 다음과 같은 2가지 문제 때문에 안된다.

1. 배열에 0이 포함되어 있는 경우

    [3, 3, 0, 3, 3]이 입력일 때의 정답은 [0, 0, 81, 0, 0]이어야 하는데 전체 원소의 곱을 구해놓고 각 원소로 나누면 3번째 원소를 처리하기가 곤란해진다. 0 / 0 을 처리할 수가 없기 때문이다.

2. 문제에서 나누기 연산을 금지한다고 조건을 걸었음

    나누기 말고 다른 방법으로 풀어주기를 문제에서 원하고 있다.

DP로 문제를 풀 때 흔히 사용되는 누적합 배열을 만들어서 이 문제를 해결할 수 있다. 이 문제의 경우엔 누적합이 아니라 누적곱이다.

길이가 n+1인 입력이 들어왔을 때, d[i] = 0부터 i-1번째까지의 누적곱, d2[i] = n부터 i+1번째까지의 누적곱이라고 하면, answer[i] = d[i] * d2[i]가 성립한다.

위의 식을 사용해서 문제를 해결하였다. 근데 문제에서 메모리 최적화를 후속 조치로 요구했기에, d[i], d2[i]를 선언하지 않고 출력을 위한 answer 리스트만 선언한 뒤 for문 2번 돌려서 문제를 해결하였다.

소스 코드

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        answer = [1 for _ in range(len(nums))]
        product = 1
        for i in range(1, len(nums)):
            product *= nums[i-1]
            answer[i] *= product
        product = 1
        for i in range(len(nums)-2, -1, -1):
            product *= nums[i+1]
            answer[i] *= product
        return answer

https://leetcode.com/problems/array-partition/

풀이 과정

배열을 입력 받고, 배열의 원소를 2개씩 짝지은 후, 짝에서 작은 값들의 합이 가질 수 있는 최대값을 출력하는 문제이다.

[1, 3, 2, 6, 4, 5]을 생각해보자. 1은 어떤 원소랑 짝지어지던 짝의 작은 값은 자신이 될 것이고, 합의 최대값을 만들기 위해서는 다른 수중 가장 작은 수인 2를 가져오는게 맞을 것이다.

3도 마찬가지다 1, 2가 이미 짝지어졌으니 6 4 5중 어떤 수랑 짝이 지어지던 짝의 작은 값은 자신이 될 것이고, 합의 최대값을 만들기 위해서는 남은 수중 가장 작은 4랑 묶이는게 맞을 것이다.

이런식으로 생각하다보면 그냥 배열을 오름차순 정렬한 다음에 앞에서 부터 2개씩 짝짓고, 짝의 작은 값을 다 더하면 합의 최대값이 될 것이라고 판단할 수 있다. 짝도 지을 필요가 없다. 정렬후 짝수번째 index의 원소의 합을 구해주면 된다.

소스 코드

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        answer = 0
        nums.sort()
        for i in range(0, len(nums), 2):
            answer += nums[i]
        return answer

좀 더 효율적이고 짧은 코드

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        return sum(sorted(nums)[::2])

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

풀이 과정

배열에서 합이 0을 이루는 3개의 원소를 출력하는 문제이다.

가장 간단하게 생각하면 완전 탐색으로 O(N^3)으로 풀 수 있을 것이다. 하지만 완전 탐색으로 풀이하면 Time Out으로 풀이에 실패한다. 더 빠르게 문제를 해결할 수 있는 효율적인 코드를 찾아야 한다.

정렬후 투 포인터 알고리즘을 사용하면 문제를 해결할 수 있다. 우선 정렬을 한 후, 각 배열의 원소를 축으로 한번씩 둔 다음, 축의 바로 다음 원소를 left 포인터, 배열의 마지막 원소를 right 포인터로 둔 뒤, 합이 0보다 작으면 left 포인터를 전진, 0보다 크면 right 포인터를 후진 시키는 식으로 O(N^2)만에 문제를 해결할 수 있다.

소스 코드

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        
        for i, a in enumerate(nums):
            # same value as before so continue
            if i > 0 and a == nums[i-1]:
                continue
                
            l,r = i+1, len(nums)-1
            while l < r:
                threeSum = a + nums[l] + nums[r]
                if threeSum > 0:
                    r -=1
                elif threeSum < 0:
                    l+= 1
                else:
                    res.append([a,nums[l],nums[r]])
                    l += 1
                    while nums[l] == nums[l-1] and l<r:
                        l+= 1
        return res

https://leetcode.com/problems/longest-palindromic-substring/submissions/

풀이 과정

문자열 내에서 가장 긴 팰린드롬 부분 문자열을 구하는 문제이다.

팰린드롬 문자열은 뒤집어도 뒤집기 전의 문자열과 같은 문자열을 의미한다. DP로 풀 수 있는 잘 알려져 있는 문제이지만 O(N^2)로 부분 문자열을 확장해가며 해결하였다.

다음과 같은 알고리즘을 구현해 문제를 해결하였다.

소스 코드

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(i):
            left, right = i, i
            while left >= 0:
                if s[i] == s[left]:
                    left -= 1
                else:
                    break
            while right <= len(s) -1:
                if s[i] == s[right]:
                    right += 1
                else:
                    break
            
            while left >= 0 and right <= len(s) - 1:
                if s[left] == s[right]:
                    left -= 1
                    right += 1
                else:
                    break
            
            return s[left+1:right]
                
        answer = ''
        for i in range(len(s)):
            answer = max(answer, expand(i), key=len)
        return answer

https://leetcode.com/problems/most-common-word/

풀이 과정

문자열에서 금지되지 않은 단어 중에, 가장 많이 나온 단어를 출력하는 문제이다.

isalpha(), islower() 등의 파이썬 내장 함수로 알파벳, 소문자 처리를 문제 조건에 맞게 처리해준 후, collections 모듈의 Counter 객체를 사용하여 문자열 안에 나온 단어의 개수를 세주었다. 

Counter 사용법

a = [1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]이라고 하면,

b = collections.Counter(a) -> Counter({3: 5, 2: 4, 1: 2})

위와 같이 각 원소가 a에서 몇번 나왔는지 카운터 객체로 반환받을 수 있다.

c = b.most_common() -> [(3, 5), (2, 4), (1, 2)]

most_common() 함수를 통해 튜플을 포함한 리스트의 형태로 반환받을 수 있으므로 c[0][0]으로 접근해 a에서 가장 많이 나온 원소가 무엇인지 파악할 수 있다.

소스 코드

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        real_para = ""
        
        for letter in paragraph:
            if not letter.isalpha():
                letter = ' '
            else:
                letter = letter.lower()
            real_para += letter
        
        paragraph = real_para.split()
        paragraph = collections.Counter(paragraph)
        
        for word in paragraph.most_common():
            if word[0] not in banned:
                return word[0]

https://leetcode.com/problems/reorder-data-in-log-files/

풀이 과정

Letter-logs와 Digit-logs로 나누어 정렬하되, Letter-logs가 Digit-logs보다 앞에 와야 하고, Digit-logs는 입력받은 순서대로 정렬하고 Letter-logs는 사전적으로 정렬을 해야하는 문제이다.

logs의 원소들을 split(' ')으로 공백을 기준으로 쪼갠 후, Letter와 Digit을 분류해주었다.

lets.sort(key=lambda x: (x.split()[1:], x.split()[0]))으로 letter log를 사전식으로 정렬하고, [1], [2], [3]...의 모든 원소가 같으면 identifiers로 정렬하게끔 하였다. 

소스 코드

class Solution:
    def reorderLogFiles(self, logs: list[str]) -> list[str]:
        lets, digs = [], []

        for log in logs:
            if log.split(' ')[1].isdigit():
                digs.append(log)
            else:
                lets.append(log)

        lets.sort(key=lambda x: (x.split()[1:], x.split()[0]))
        return lets + digs

https://leetcode.com/problems/reverse-string/

풀이 과정

문자열 s를 뒤집는 문제이다.

크게 3가지 방법을 떠올릴 수 있다.

1. 내장 함수 사용

그냥 파이썬 내장 함수 써서 뒤집는 방법이다. s.reverse()를 사용하면 된다.

2. 투 포인터 사용

문자열의 시작과 끝에 포인터 2개를 두고 포인터의 인덱스에 해당하는 문자끼리 서로 바꿔가면서 왼쪽 포인터는 한칸 전진, 오른쪽 포인터는 한칸 후퇴하면서 계속 바꿔가면 된다. 이 방법대로 문제를 풀이하였다.

3. 문자열 슬라이싱

s = s[::-1]로 뒤집어서 할당해주면 될 것 같지만 문제에서 공간복잡도를 O(1)로 제한하였다. s[:] = s[::-1] 같은 트릭을 사용하여 이 방법으로도 문제를 해결 할 수 있다.

소스 코드

class Solution:
    def reverseString(self, s: List[str]) -> None:
        left, right = 0, len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

https://leetcode.com/problems/valid-palindrome/

풀이 과정

문자열 s가 팰린드롬인지 확인해주는 기능을 구현하면 된다.

팰린드롬이란 문자열을 뒤집어도 똑같은 문자열을 말한다. 예를 들면 기러기, 토마토, 스위스, 인도인, 별똥별, 우영우, 역삼역 등의 단어는 모두 팰린드롬을 만족하는 단어이다.

문제의 조건에 맞게 대문자는 소문자로 바꿔주고, 알파벳이 아닌 문자는 문자열에서 전부 무시해준 다음, 문자열 s와 s[::-1]을 비교해 같으면 팰린드롬 문자열이라고 판단하였다.

굳이 s와 동일한 원소를 가진 s'를 선언해서 s'.reverse()로 뒤집은 다음 s == s'인지 비교할 필요 없이 문자열 슬라이싱으로 더 빠르게 해결할 수 있다.

소스 코드

class Solution:
    def isPalindrome(self, s: str) -> bool:
        chars = []
        for char in s:
            if char.isalnum():
                char = char.lower()
                chars.append(char)
        if chars == chars[::-1]:
            return True
        else:
            return False

https://leetcode.com/problems/trapping-rain-water/

풀이 과정

다음과 같은 input이 들어올 때, 고이는 물의 총부피를 구하는 문제이다.

가장 높은 바닥을 기준으로 왼쪽 영역과 오른쪽 영역으로 나눠서 생각하면 풀이 방법이 빠르게 떠오른다.

왼쪽 영역은 왼쪽에서부터, 오른쪽 영역은 오른쪽에서 부터 읽어 나가면서, 여태 나왔던 바닥의 최대 높이를 저장하고, 바닥의 최대 높이 - 현재 바닥의 높이만큼 물이 고일 것이므로 그만큼을 정답 변수에 더해주면 된다.

소스 코드

class Solution:
    def trap(self, height: List[int]) -> int:
        left_max, right_max = 0, 0
        max_height_index, max_height = 0, 0
        answer = 0
        
        for i in enumerate(height):
            if max_height < i[1]:
                max_height_index, max_height = i[0], i[1]
                
        for i in range(0, max_height_index):
            if left_max < height[i]:
                left_max = height[i]
            else:
                answer += left_max - height[i]
        
        for i in range(len(height)-1, max_height_index, -1):
            if right_max < height[i]:
                right_max = height[i]
            else:
                answer += right_max - height[i]
        
        return answer

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

풀이 과정

합이 target이 되는 배열 값을 가리키는 인덱스 2개를 구하라는 문제이다.

완전 탐색을 돌려서 O(N^2)로 답을 구할 수 있다. 그런데 후속 조치로 O(N^2) 보다 적은 시간 복잡도를 가진 알고리즘으로 해결할 수 있냐는 질문이 달려있다.

1. 투 포인터로 풀기

입력된 리스트에 enumerate로 index 붙여주고, x:x[1]에 대해 정렬시킨 뒤, 포인터를 배열의 시작, 끝부분에 위치시키고 포인터에 해당하는 배열의 합이 타겟보다 작으면 left += 1, 아니면 right -= 1 시켜가면서 답을 구했다.

정렬이 O(NlogN)이고 투포인터로 배열 탐색이 O(N) 걸리니 알고리즘의 시간 복잡도는 O(NlogN)이다. 105ms의 실행시간을 가지는 효율적 방법이다.

2. 딕셔너리로 풀기

딕셔너리[값] = 인덱스를 저장해나가면서, 타겟 - 값을 키로 갖는 밸류가 딕셔너리에 존재하는지 살펴본다. 배열을 1회만 탐색하면 되므로 O(N)인데 실행시간이 112ms가 나와 투 포인터보다 의미 있게 빠르진 않았다.

소스 코드

투 포인터

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        left, right = 0, len(nums) - 1
        s_nums = sorted(enumerate(nums), key=lambda x:x[1])
        
        while (left < right):
            sum = s_nums[left][1] + s_nums[right][1]
            if sum == target:
                return [s_nums[left][0], s_nums[right][0]]
                break
            elif sum < target:
                left += 1
            else:
                right -=1

딕셔너리

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {}
        for i, num in enumerate(nums):
            if target - num in dic:
                return [dic[target - num], i]
            dic[num] = i