굿

올바른 괄호 / 균형잡힌 괄호 2가지를 체크하는 함수를 각각 구현한 뒤 문제에서 설명하는 변환 과정 1 ~ 4를 구현 하면 됩니다.

이때 재귀 부분만 신경쓰면 큰 어려움은 없을 듯 합니다.

def isbalanced(s):
    flag = 0
    for c in s:
        if c == '(':
            flag += 1
        elif c == ')':
            flag -= 1
        
    if flag == 0: return True
    else: return False
    
def iscorrect(s):
    stack = []
    for c in s:
        if len(stack) == 0:
            stack.append(c)
        else:
            if c == '(':
                stack.append(c)
            elif c == ')':
                if len(stack) == 0 or stack.pop() != '(':
                    return False
    
    if len(stack) == 0: return True
    else: return False
    

def solution(p):
    answer = ""
    u = ""
    v = ""
    
    if len(p) == 0 or iscorrect(p): return p
    
    for i in range(2, len(p)+1, 2):
        if isbalanced(p[0:i]):
            u=p[0:i]
            v=p[i:len(p)]
            print(u, v)
            break
    
    if iscorrect(u):
        answer += u + solution(v)
    
    else:
        answer += '(' + solution(v) + ')'
        for c in u[1:-1]:
            if c == '(': answer += ')'
            else: answer += '('
    
    return answer

그냥 무식하게 1개 단위 ~ n-1개 단위 압축 경우의 수를 모두 계산하고 그 중 가장 작은 값은 반환하는 방법으로 해결했습니다.

좀 더 깔끔하게 해결한 코드가 있으면 정리해서 업데이트 하겠습니다..

import math

def solution(s):
    if len(s) == 1:
        return 1
    elif len(set([c for c in s])) == 1:
        count = len(s)
        return len(str(count)) + 1
    else:
        answer = len(s)

        for i in range(1, len(s)):
            idx = i
            length = 0
            prev = s[:i]
            count = 1

            for j in range(math.ceil(len(s) / i) - 1):
                curr = s[idx:idx+i]

                if prev != curr:
                    if count == 1:
                        length += i
                    else:
                        length += i + len(str(count))

                    count = 1
                else:
                    count += 1
                idx += i
                prev = curr

            if count == 1:
                length += len(curr)
            else:
                length += i + len(str(count))

            answer = min(answer, length)
        
    return answer

문제 풀이 및 해설 (Kakao Tech 블로그)

Problem)

Solution 1)

2중 for문을 사용해서 인덱스 i + j 값을 활용하여 리스트의 대각선 성분들끼리 묶을 수 있습니다. 예제의 경우 각 위치의 i + j 값은,

[[1, 2, 3],                [[0, 1, 2],

 [4, 5, 6],    ---->    [1, 2, 3],

 [7, 8, 9]]                [2, 3, 4]]

이와 같이 표현할 수 있기 때문에 O(n)의 복잡도로 모든 원소들을 대각선 묶음으로 저장해서 얻은 딕셔너리를 각 키 값의 성분들을 역순으로 출력하면 원하는 값을 얻을 수 있습니다.

d = {"0": [0], "1": [2, 4], "2": [3, 5, 7], "3": [6, 8], "4": [9]}

각 리스트들의 역순 reversed_d = {"0": [0], "1": [4, 2], "2": [7, 5, 3], "3": [8, 6], "4": [9]}

from collections import defaultdict

class Solution:
    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
        dic = defaultdict(list)
        I = len(nums)
        
        for i in range(I):
            for j in range(len(nums[i])):
                dic[i+j].append(nums[i][j])
                
        res = []
        
        for k in sorted(dic.keys()):
            res.extend(dic[k][::-1])
            
        return res

그런데 이러한 풀이법은 비슷한 유형의 문제를 접해보지 않은 사람이라면 그렇게 쉽게 생각해내기는 어려울 수도 있습니다. (제 경우에는 쉽게 이런 생각을 할 수 없었습니다...)

따라서 트리 구조를 적용한 다음과 같은 풀이법도 존재합니다.

Solution 2)

주어진 2차원 리스트을 트리 구조로 보고 BFS를 활용하면 원하는 결과를 얻을 수 있습니다.

주어진 리스트의 [0, 0]을 root node로 보고 [1, 0]을 left child, [0, 1]을 right child로 보면 우리는 주어진 리스트를 트리 구조로 변형 시켜서 생각할 수 있습니다.

이때 주의해야할 점은, 중복 child가 생길 수 있다는 것 입니다. 예를 들어 [1, 1]은 [1, 0]의 right child가 되는 동시에 [0, 1]의 left child가 될 수 있습니다. 따라서 우리는 이를 방지하기 위한 조건으로 가장 왼쪽에 있는 열 [:, 0]의 node들만 left child를 고려하게끔 만듭니다. 이렇게하면 node들 간의 중복된 child를 갖지 않게 됩니다.

class Solution:
    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
        ans = []
        m = len(nums)
        
        # [0, 0] root node를 가진 deque 생성
        queue = collections.deque([(0, 0)])
        
        while queue:
            row, col = queue.popleft()
            ans.append(nums[row][col])
            
            # 가장 좌측 열의 node(col == 0)만 left child를 고려
            if col == 0 and row + 1 < m:
                queue.append((row + 1, col))
                
            # right child
            if col + 1 < len(nums[row]):
                queue.append((row, col + 1))
            
        return ans

Problem)

Solution)

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

Problem)

Solution)

쉬워 보이지만 제대로된 풀이법을 생각해 내는데 꾀 오랜 시간이 걸렸다..

계속해서 무식한 방법을 사용하다 보니까 시간 초과가 나서...

leetcode 사이트에 discussion에 좋은 설명이 있어서 참조하여 설명글을 정리하겠습니다.

기본 아이디어는 입력받은 리스트 값을 하나씩 단계별로 더해서 sum값을 구할 때, 이 sum값이 k만큼 증가하는 순간에 합이 k값인 subarray를 구할 수 있습니다. 무슨 의미인지 풀어서 설명하겠습니다.

리스트 [1, 2, 1, 3]과 k = 3이 주어진다면, 단계별 sum값들은 [1, 3, 4, 7]이 됩니다. 이때, 1 -> 4인 순간과 4 -> 7인 순간을 통해서 우리는 합이 3인 subarray가 2개 있다는 것을 알 수 있습니다.

하지만, 실제 리스트 [1, 2, 1, 3]에서 합이 3인 subarray는 [1,2], [2,1], [3]으로 총 3개가 됩니다. 위의 계산에서 [3]을 빠뜨렸다는 것을 알 수 있습니다. 따라서 단계별 합 값이 k가 되는(위의 예제에서는 [3]) 경우를 포함하기 위해서 우리는 합계에 0을 추가하여 고려해야 합니다.

따라서, [0, 1, 3, 4, 7]을 순서대로 계산했을 때, 0 -> 3, 1 -> 4, 4 -> 7 총 3개의 subarray가 있다는 것을 알 수 있습니다.

import collections

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # 리스트 값의 합 카운트 사전
        sums_list = collections.Counter()
        # k와 같은 합 값이 존재할 경우를 위해
        sums_list[0] = 1
        
        # 리스트 값의 합
        sums = 0
        
        # 결과값
        answer = 0
        
        for num in nums:
            # 리스트 값을 하나씩 더하며 이때까지의 합 값 구하기
            sums += num
            
            # 만약 이전에 sums값 중 (sums-k)와 같은 값이 존재 했다면,
            # 합이 k인 subarray가 존재한다는 의미
            answer += sums_list[sums-k]
            
            sums_list[sums] += 1

        return answer

Problem)

Solution)

이전에 풀었던 "Container With Most Water"와 거의 유사한 문제입니다. 길이 n의 배열이 주어지고 배열의 각 값은 위 그림에 보이는 것 같이 'bar'의 길이를 나타냅니다. 이때, 비가 와서 물이 가득 찼을 때의 물의 양을 구하면 됩니다.

풀이법은 n 길이의 배열을 for loop으로 돌리면서 각 단계마다 중심 기둥이 되는 위치의 좌측에서 가장 높은 기둥을 "left", 그리고 우측에서 가장 높은 기둥 "right"라고 정의 합니다. 이때, left와 right중 작은 기둥의 높이 만큼 빗물이 찰 수 있게 되고 따라서 얻은 작은 기둥의 높이에서 중심 기중의 높이의 차이가 실제로 해당 공간에 빗물이 찰 수 있는 공간이 됩니다.

설명이 조금 복잡해 보이는데 아래 python code를 보시면 더욱 쉽게 이해되실 것 같습니다.

(1)

class Solution:
    def trap(self, height: List[int]) -> int:
        if height:
            water = 0
            
            for i in range(1, len(height) - 1):
                left = max(height[:i])
                right = max(height[i+1:])
                min_bar = min(left, right)
                
                if min_bar > height[i]:
                    water += min_bar - height[i]
            return water
        else:
            return 0

위의 솔루션 (1)에서 시간 복잡도를 신경써서 아래와 같은 코드를 완성할 수 있습니다.

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        volume = 0
        left, right = 0, len(height) - 1
        left_max, right_max = height[left], height[right]

        while left < right:
            left_max, right_max = max(height[left], left_max), max(height[right], right_max)

            if left_max <= right_max:
                volume += left_max - height[left]
                left += 1
            else:
                volume += right_max - height[right]
                right -= 1
        return volume

Problem)

Solution)

먼저 제 첫번째 솔루션 입니다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for idx, value in enumerate(nums):
            if (target - value) in nums:
                if nums.index(target - value) != idx:
                    return [idx, nums.index(target - value)]

그보다 x20 빠른 솔루션 입니다.

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

시간과 메모리 효율성을 항상 고려하는 습관을 길러야겠다

Problem)

정말 간단한 문자열 뒤집기 문제 입니다. 문제의 핵심은  in-place로 추가 메모리를 사용하지 않고 해결하라는 조건입니다.

Solution)

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        left, right = 0, len(s) - 1
        
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

left와 right로 처음과 끝의 인덱스를 설정하고 서로 맞바꾸는 방법으로 문자열을 뒤집을 수 있습니다.

* 추가적으로 python에서 제공하는 reverse()를 사용하여 정말 간단하게도 해결 가능합니다.

class Solution:
    def reverseString(self, s: List[str]) -> None:
        s.reverse()

아래 결과를 보시면 첫 번째가 reverse()를 사용한 방법으로 조금 더 빠른 runtime을 보여줍니다.