[TIL_Carrotww] 87 - 23/01/16

📝Carrotww의 코딩 기록장

🧲 python algorithm interview

🔍 Leetcode 16 3Sum closest Medium

쉬워보였지만 조금씩 조건이 들어가서 살짝 까다로운 문제였다.
brute force로는 시간초과가 나며
처음에 조합으로 풀었지만 시간초과로 당연히 실패하였다.
그 다음 책에 나온대로 투 포인터 방식으로 풀이를 하며 풀었다.

from typing import List

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        nums.sort()

        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            left, right = i + 1, len(nums) - 1
            while left < right:
                temp = nums[i] + nums[left] + nums[right]
                if temp == 0:
                    result.append([nums[i], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left+1]:
                        left += 1
                    while left < right and nums[right] == nums[right-1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif temp < 0:
                    left += 1
                elif temp > 0:
                    right -= 1

        return result

🔍 Leetcode 42 Trapping Rain Water - Hard

어려웠다 이해하는데 한참 걸렸다.
stack 방식과 투포인터 방식이 있는데 두 방법 모두 좋은 것 같다.

• stack 방식

class Solution:
    def trap(self, height: List[int]) -> int:
        stack = []
        result = 0

        for i in range(len(height)):
            while stack and height[i] > height[stack[-1]]:
                before_index = stack.pop()

                if not stack:
                    break

                distance = i - stack[-1] -1
                waters = min(height[i], height[stack[-1]]) - height[before_index]

                result += distance * waters
            stack.append(i)
        return result

스택에 있는것을 하나씩 빼며 현재 index에서 이전 index는 pop으로 빼주어 그 사이값을 구해주는 방식이다.

• 투 포인터 풀이
  직관적이지만 떠올리기 너무 어렵다.
  한 달 후에 풀면 이 방법으로 풀 수 있을지 잘 모르겠다. 계속 보고 복습해야 할 것 같다.
  왼쪽 오른쪽에 가장 큰 값을 기억한 후 left와 right를 가운데로 이동시키며 지나온 길에 파인곳(?) 을 확인하는 것이다.
  left_max, right_max로 지나온 길을 저장, height[index] 와 비교하며 결과값에 더해주는 것이다.

풀이를 쓰며 계속 쳐다보니까 쉬워진거 같은 느낌이...

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

        result = 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:
                result += left_max - height[left]
                left += 1
            else:
                result += right_max - height[right]
                right -= 1
        return result

🧲 python algorithm

🔍 백준 1874 스택 수열 쉬움
스택 문제이다 파이썬 알고리즘 인터뷰 문제를 하나 더 풀었지만 쉬운거라 굳이 올리지는 않았다.
총 4문제가 목표인데 한두문제 막히면 빠듯한거같다.
유형별 문제도 2문제씩 풀어야하는데 앞에서 3문제 풀었기때문에 오늘은 하나만..ㅎ

• 풀이

import sys
n = int(sys.stdin.readline())

def Solution(n):
    stack, result = [], []
    cnt = 1
    for i in range(n):
        num = int(sys.stdin.readline())
        while cnt <= num:
            stack.append(cnt)
            result.append('+')
            cnt += 1
        if stack[-1] == num:
            stack.pop()
            result.append('-')
        else:
            return False
    return result

result = Solution(n)

if result:
    for i in result:
        print(i)
else:
    print('NO')