[4코3파] 1명의 스위프트 개발자가 도망가고 4명의 코틀린 개발자, 3명의 파이썬 개발자의 코딩 테스트 스터디 : 4코3파
START :
[3코1파] 2023.01.04~ (294일차)
[4코1파] 2023.01.13~ (286일차)
[4코3파] 2023.10.01 ~ (24일차)
Today :
2023.10.24 [294일차]
Leetcode Two Pointers 문제
뭔가 기초도 잘 모르면서 중상급 문제를 자꾸 깔짝이고 있는 듯한 느낌이 들어서,
밑바닥 돌이 잘 놔져있는지 돌다리도 두드려보고 건너기 위하여
leetcode tree 문제 복습겸 Two Pointers 문제 다시 풀기
+코딩 인터뷰 189가지 프로그래밍 문제와 해법 완전분석 책이랑 같이 보기
[1] 125. Valid Palindrome
문제 설명
주어진 문자가 Palindrome (회문) 일 경우 True, 아니면 False
Palindrome은 문자열을 뒤집었을때도 (reverse) 원래의 문자열과 같은 것
예 ) 기러기, 토마토, 우영우
문제 풀이 방법
지금으로부터 바야흐로 23년 1월 17일에 내가 풀었던 풀이를 보면
냅다 re라이브러리로 정규표현식으로 갈겨서 풀어서 통과했다고 좋아했던 모습이 있다.
ㅋ 이러니까 실력이 안늘었지...
제약사항에서 아스키 어쩌고가 있길래, 이건 아스키코드를 이용해야겠구나 싶었다.
일단 나의 미천한 실력으로 푸는건 일단 문자열의 대소를 구분하지 않는다고 했으므로,
문자열을 소문자로 다 바꿔 준다음에, 숫자 문자열이 나오면 문자열에 추가, 나머지 영문자들 추가 그리고 나머지들은 제거 해서 새로운 문자열을 만들어 줬다.
그리고 슬라이싱해서 (reverse) 해서 문자열 비교함 ㅋ
문자열 s의 길이를 n이라고 하면 문자열을 한번 순회 해야하므로 o(n),
수정된 문자열을 한 번 더 리버스하기 위해 O(n) 으로 시간복잡도는 O(n)가 나오고,
재구성한 문자열을 저장하므로 공간복잡도도 O(n) 인 코드이다.
class Solution:
def isPalindrome(self, s: str) -> bool:
s = s.lower()
tmp = ''
for string in s:
if string in '0123456789':
tmp += string
if 97 <= ord(string) <= 122:
tmp += string
return tmp == tmp[::-1]
이를 좀 더 다듬으면 python의 isalnum() 함수를 사용해서, 문자열과 숫자열만 새로운 문자열로 만드는 함수를 사용한다음 슬라이싱으로 확인하는 법도 있다
class Solution:
def isPalindrome(self, s: str) ->bool:
newStr = ''
for c in s:
if c.isalnum():
newStr += c.lower()
return newStr == newStr[::-1]하지만 이방법 또한 새로운 메모리를 필요로한다.
이 문제의 카테고리는 Two Pointer, 나는 Two Pointer를 쓰지 않았음..
Two Pointer로 푸는 방법은
일단 위의 텍스트가, a-z, A-Z, 0-9 등 숫자나 문자인지 확인하는 함수를 만들고 이를 이용한다.
위의 함수는 문자의 아스키코드를 이용해서 조건에 맞으면 true, false를 return 한다.
left, right로 주어진 문자열에서 처음과 맨 끝을 left, right 로 두고
left,right를 위의 조건에 맞춰서 띄어쓰기 및 특문이면 left, right를 움직이고
조건에 맞는 문자열이라면 문자열 기준 왼쪽과 오른쪽 인덱스에 문자가 같은지 확인한다.
그러니까 서치를 하면서 동시에 왼,오를 보면서 정 가운데 문자열 까지 오면서 확인 하는 그런 알고리즘이다.
내 코드
시간복잡도는 O(n), 공간복잡도는 O(1)
class Solution:
def isPalindrome(self, s: str) ->bool:
l, r = 0, len(s)-1
while l<r:
while l<r and not self.alphaNum(s[l]):
l+=1
while l<r and not self.alphaNum(s[r]):
r -=1
if s[l].lower() != s[r].lower():
return False
l,r = l+1, r-1
return True
def alphaNum(self, c):
return (ord('A') <= ord(c) <= ord('Z') or ord('a') <= ord(c) <= ord('z') or ord('0') <= ord(c) <= ord('9'))
[2] 167. Two Sum II - Input Array Is Sorted
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
문제 설명
오름차순으로 정렬되어 있는 정수 배열 numbers에서 두 원소의 합이 target이 되는 배열의 두 인덱스를 return 한다
1<= index1 < index2 < len(numbers 로, 첫번째 원소의 인덱스는 0이 아니라 1임 !
문제 풀이 방법
자료구조를 추가해서 시간복잡도 O(n), 공간복잡도 O(n) 으로 푼다면
hash map 하나를 추가해서 답을 찾아나가는 방법도 있다.
numbers 배열을 순회하면서, 해당 target과 배열의 원소를 뺀 값을 키로 현재의 인덱스+1을 value로 저장한다. 순회하면서 해당 key가 hash map 안의 key로 있으면, hash map의 value(합이 되는 이전의 인덱스)와 현재 인덱스에 +1을 해서 return 해서 찾을 수 있음
class Solution:
def twoSum(self, numbers: list[int], target: int) -> list[int]:
numSet = {}
for i in range(len(numbers)):
if numbers[i] in numSet:
return [numSet[numbers[i]], i+1]
numSet[target-numbers[i]] = i+1
two pointer를 사용한다면 O(n), O(1)로 풀 수 있다.
left, right를 각각 포인터로 두고, 정수배열의 왼쪽과 오른쪽 인덱스의 합을 target과 비교해서, target이 크다면 right를 왼쪽으로 움직이고(-1), target 보다 합이 작다면 left를 오른쪽으로 (+1) 움직이면서 찾으면 된다.
target의 합과 같은 두 원소를 찾았으면 각 인덱스에 +1을 해서 return 하는 법 잊지 말기!
내 코드
class Solution:
def twoSum(self, numbers: list[int], target: int) -> list[int]:
l,r = 0, len(numbers)-1
while l<r:
curSum = numbers[l]+numbers[r]
if curSum > target:
r -=1
elif curSum < target:
l +=1
else:
return [l+1, r+1]
return
[3] 15. 3Sum
문제 설명
정수 배열 nums가 주어질 때, 각기 다른 세 개의 원소의 합이 0이 되는 원소의 인덱스들을 return 한다.
문제 풀이 방법
2 sum 을 어제 풀어서 그런지 3 sum 의 경우에는 세 개의 합 중 하나만 현재 인덱스에 고정하고 나머지 두개를 two pointer 로 핸들링하면 된다고는 인지했다.
구현할때 문제가 발생했는데 중복된 값이 있을 경우, 주어진 nums의 index를 넘기는 것과 left, right 의 좌표도 넘기는 코드를 잘 짜지 못했음
solution에서 while 문을 통해서 조건을 체크하고 left 좌표를 옮겨가고,
enumerate 를 통해서 nums의 index와 num 값에 대하여 뒷 인덱스의 값과 비교해서 넘기는 continue를 통해서 핸들링해야 하는 것 잊지말자고
내 코드
시간복잡도는 O(n^2), 공간복잡도는 O(n)
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
ans = []
nums.sort()
for i,n in enumerate(nums):
if i>0 and nums[i-1] ==n:
continue
l,r = i+1, len(nums)-1
while l<r:
curSum = n + nums[l]+nums[r]
if curSum > 0:
r-=1
elif curSum <0:
l+=1
else:
ans.append([n, nums[l], nums[r]])
l+=1
r-=1
while l<r and nums[l-1]==nums[l]:
l+=1
return ans
[4] 11. Container With Most Water
문제 설명
문제 풀이 방법
brute force로 maximum area를 찾으면 TLE 발생..
class Solution:
def maxArea(self, height: List[int]) -> int:
ans = 0
for l in range(len(height)):
for r in range(l+1, len(height)):
area = (r-l) * min(height[l],height[r])
ans = max(area, ans)
return ans
two pointer로 푸는데, 처음엔 height 배열을 enumerate로 돌면서 left, right로 체크하려고 했는데 그럴 필요가 없었다.
그냥 heigth 배열의 첫 번째, 마지막 번째를 left, right 두개의 포인터로 두고, 두 포인터의 각각 위치하는 높이를 비교했을 때, 더 낮은 쪽에 기준을 두고 왼쪽 혹은 오른쪽으로 이동하면된다.
최대 넓이를 구하고자 한다면, 높이가 높아야하기 때문에 높은 높이 인 경우에는 고정시키고 왼쪽 오른쪽으로 움직이면서 전체 면적을 비교하는 것이다.
그리고 여기서 높이는 아무리 어느 한 점의 높이가 높다고 하더라도, 한 높이가 낮으면 물이 넘치기 때문에, 면적을 구할때, 두 높이 중 최소 높이를 높이로, 그리고 밑 면적은 두 인덱스의 차이로 해서 구하면 된다.
시간 복잡도 O(n), 공간복잡도 O(1) 으로 구할 수 있는 것이다
내 코드
class Solution:
def maxArea(self, height: List[int]) -> int:
maxArea = 0
l,r = 0, len(height)-1
while l<r:
area = (r-l) * min(height[l], height[r])
maxArea = max(maxArea, area)
if height[l] < height[r]:
l+=1
else:
r-=1
return maxArea
[5] Trapping Rain Water
문제 설명
양의 정수가 담긴 height 배열이 주어지는데, 해당 배열의 원소는 높이를 나타낸다.
각 height 배열에 물을 떨어트린다면 담길 수 있는 최대 면적의 합을 구해서 return 하라.
문제 풀이 방법
시간복잡도 O(n), 공간복잡도 O(n) 으로 푸는 방법은
height 배열의 현재 인덱스를 기준으로 좌, 우 최대 높이들을 산정하고, 물이 담길 수 있는 것은
좌,우 높이에서 낮은 높이에서 현재 나의 높이를 뺀 값이므로
현재 hight 기준 maxLeft, maxRight를 구하고 그 둘의 min(maxLeft, maxRight)를 구한 뒤에 현재의 높이를 빼주면 물에 담기는 water 이므로 이를 다 더해주는 방법으로 풀면된다.
현재 인덱스에서 담길수 있는 물은 현재 인덱스 기준으로 왼쪽 기준 가장 높은 높이와, 오른쪽 기준 가장 높은 높이 중 낮은 높이만큼 담을 수 있으며 현재 바의 높이를 빼준 값이다
즉 min(height[left], height[right]) - height[i] 가 담을 수 있는 물인거다!
그래서 현재 인덱스 기준으로 물의 양을 배열에 담고 이를 sum 한다.
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
if n <=2:
return 0
leftMax, rightMax = [0]*n, [0]*n
leftMax[0] = height[0]
rightMax[n-1] = height[n-1]
for i in range(1, n):
leftMax[i] = max(leftMax[i-1], height[i])
for i in range(n-2, -1, -1):
rightMax[i] = max(rightMax[i+1], height[i])
water = 0
for i in range(n):
water += max(min(leftMax[i], rightMax[i]) - height[i], 0)
return water내 코드
더 나아가서
시간복잡도 O(1), 공간복잡도 O(1) 로 푸는 방법인데,
maxLeft, maxRight 와 현재 인덱스로부터 양 사이드를 다 보고 물값을 저장해나가면서 푼다.
위에서 O(n), O(1)은 leftMax, rightMax를 배열에 따로 저장하고,
순회하면서 연산하는 식이었지만, 이건 따로 자료구조를 생성하지 않는다.
class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0
l, r = 0, len(height) - 1
leftMax, rightMax = height[l], height[r]
res = 0
while l < r:
if leftMax < rightMax:
l += 1
leftMax = max(leftMax, height[l])
res += leftMax - height[l]
else:
r -= 1
rightMax = max(rightMax, height[r])
res += rightMax - height[r]
return res
여담
hard 문제도 찬찬히 보면 된다!
천천히 꼼꼼히 다시보고 또 다시보자
