알고리즘
18242 (백준)
Y, X = map(int, input().split())
Ychar = []
for i in range(Y):
Ychar.append(input())
for x in range(X):
for y in range(Y - 2):
if Ychar[y][x] == "#":
c = 0
if Ychar[y][x] == Ychar[y + 2][x] and Ychar[y][x] != Ychar[y + 1][x]:
for x1 in range(x, X - 1):
if Ychar[y][x1 + 1] == "#":
c += 1
if c >= 1:
print("LEFT")
else:
print("RIGHT")
for y in range(Y):
for x in range(X - 2):
if Ychar[y][x] == "#":
c = 0
if Ychar[y][x] == Ychar[y][x + 2] and Ychar[y][x] != Ychar[y][x + 1]:
for y1 in range(y, Y - 1):
if Ychar[y1 + 1][x] == "#":
c += 1
if c >= 1:
print("UP")
else:
print("DOWN")
그렇게 어려운 코드는 아닌거같은데 푸는데 애를 먹어서 벨로그에 기록함. if Ychar[y][x1 + 1] == "#": 뒤에 else 관련되서 실수해서 시간이 꼬였다. 로직 제발좀 잘 생각합시다 ^.^
1. Two Sum (leetcode)
문제 풀이방식이 여러가지이다.
내가 해설지를 보지않고 푼것은 브루트 포스(무차별 대입)방식으로 매우 느리다. 책의 다른 여러 풀이를 확인해보면 in을 이용한 탐색, 딕셔너리를 이용한 키 조회, 투 포인터(실제론 이문제는 인덱스를 구해야하기에 이 방식으로는 풀순 없지만, 인덱스가 아닌 값을 구하는 문제는 확실히 빠르게 풀 수 있다.)
42. Trapping Rain Water (leetcode)
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
풀이법 자체가 안떠올랐다. 난이도가 높기도 했지만, 투포인터를 아직 제대로 활용하지 못해서이기도 한거같다. 가운데 어딘가에서 높이가 제일 높음으로 양쪽 끝에서부터 시작해서 기록된 최대높이 - 현재 높이를 더해가면서 가장 높은 곳까지 이동하는 패턴이다.
그리고, 투포인터를 이용하는 건 코드가 이해가는데 스택쌓기는 이해가 안가서 보류,,,,
15. 3Sum (leetcode)
시간초과.
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
result=[]
for inum,i in enumerate(nums):
for jnum,j in enumerate(nums):
if inum<jnum:
for knum, k in enumerate(nums):
if jnum<knum:
if i + j + k == 0:
result.append([i,j,k])
new_list = []
for v in result:
if v not in new_list:
new_list.append(v)
return (new_list)책의 설명에 따르면 브루트 포스로 풀면 O(n^3) 정도 걸리는데 이는 이번문제에서 요하는 시간제한에 충족시키지 못한다고 한다.
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
result=[]
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:
sum = nums[i]+nums[left]+nums[right]
if sum <0:
left +=1
elif sum>0:
right -=1
else:
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
return result
561. Array Partition I (leetcode)
def arrayPairSum(self, nums: List[int]) -> int:
nums.sort()
arr=[]
total=0
for i in range(0,len(nums),2):
arr.append(min(nums[i],nums[i+1]))
for i in arr:
total+=i
return total직접 작성한 코드이다. 근데 슬라이싱을 이용하면 훨씬 간결하게 만들 수 있다. 또한, 이것이 파이썬다운 방식이라고 한다. 대략 20ms정도 짧아진다.
def arrayPairSum(self, nums: List[int]) -> int:
return sum(sorted(nums)[::2])238. Product of Array Except Self (leetcode)
시간초과.
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
le=len(nums)
arr=[1 for _ in range(le)]
for i in range(le):
for j in range(le):
if i!=j:
arr[i]*=nums[j]
return arr책의 해설이 이해가 전혀안가서 인터넷에 다른 해설을 찾아봤다. 다른 로직이 이해하기 더 쉬웠다.
arr=[1, 1, 1, 1] 을 만들고 [1,2,3,4] 을
왼쪽, 오른쪽으로 한칸씩 밀면서 곱해주면 되는것같다.
nums= [1, 2, 3, 4]
arr = [1, 1, 1, 1]
nums= [1, 2, 3] (*)
nums= [1, 2] (*)
nums= [1] (*)
중간값= [1, 1, 2, 6] (left)
nums= [2, 3, 4] (*)
nums= [3, 4] (*)
nums= [4] (*)
중간값= [24, 12, 4 ,1] (right)
최종값= [24 ,12, 8, 6]
--> [1, 1, 2, 6] * [24, 12, 4 ,1] (행렬 곱 맞나? 그방식으로 계산)
def productExceptSelf(self, nums: List[int]) -> List[int]:
le=len(nums)
arr=[1 for _ in range(le)]
left,right=1, 1
for i in range(le):
arr[i] *= left
arr[-1-i] *= right
left *= nums[i]
right *= nums[-1-i]
return arr위 코드는 코드 위의 풀이를 가로 한줄 마다 계산하는 것이 아닌 세로 한줄(i값에 영향을 받고, 이 i는 리스트 맨 앞 요소 한칸씩을 전부 처리함으로.)씩 계산한다는 점에서 조금의 차이가 있다.
근데,,, 코드는 달라도 책이랑 로직은 같더라.....ㅎ 책 설명의 왼쪽의 곱셈 결과과 오른쪽의 곱셉 결과라는 것이 자기 자신을 제외하고 자기 위치에 있는 왼쪽 또는 오른쪽의 숫자들을 모두 곱하고 그 결과를 자기 위치에 새롭게 자리하라는 소리이다.
국어가 약한게 맞네...ㅠ
121. Best Time to Buy and Sell Stock (leet code)
def maxProfit(self, prices: List[int]) -> int:
profit=0
min_price=sys.maxsize
for price in prices:
min_price = min(min_price,price)
profit=max(profit, price - min_price)
return profit이 풀이가 카데인 알고리즘 이라는데 그런건 잘 모르겠고, 이 풀이가 O(n)이고, 원래생각했던 브루트 포스로 풀땐 O(n^2)이다.
sys 를 이용해 최댓값 또는 최소값 지정하기.
sys.maxsize를 이용하면 sys상에서의 최댓값을 구할 수 있다. 앞에-를 붙이면 반대로 최솟값을 구할 수 있다. 책에서 max, min 값을 구하는 문제를 풀때 -9999999나 9999999 를 이용하는 것을 지양해야한다고 한다. 테스트 케이스에 따라 더 크거나 더 작은 값이 나올 것을 염두해둬야해서다. 또한, float('inf')를 이용해 무한값을 지정하는 방법이 있다.
파알인 7장 배열 완료.
