원티드 프리온보딩 1-1 알고리즘 (3)

wodnr_P·2023년 8월 24일

leetcode 알고리즘 원티드 원티드 프리온보딩 프리온보딩

LeetCode Top Interview 150

목록 보기

3/32

⭐️ LeetCode 알고리즘 풀이 (with Python)

# Best Time to Buy and Sell Stock

[Quetion]

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

[Example 1]

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

📌 접근법

처음 문제를 봤을 때 리스트 내의 최소 값을 찾고 최소 값을 제외한 그 이후의 값들 중 가장 큰 값과 차이를 구하면 되겠다는 생각으로 접근했다. 그래서 min(), max() 함수를 활용하여 코드를 작성해보았다.

# 실패한 시도
 class Solution(object):
     def maxProfit(self, prices):
         # 리스트 내 최소값 이후 값 중 가장 큰 값의 차이 구하는 것 
         # 최소값
         buy=min(prices)

		 # 만약 최소값 이후의 값이 0이면 0리턴
         if len(prices[prices.index(buy)+1:])==0:
             return 0
         # 최소값 이후의 값 중 가장 큰 값 
         sell=max(prices[prices.index(buy)+1:])

         return sell-buy

리스트 슬라이싱과 min(), max(), index() 함수를 활용했지만 리스트가 [2,4,1]일 경우 잘못된 값을 반환 했고, for문을 활용하여 리스트 요소 하나하나 값을 비교해봐야겠다고 생각을 바꾸었다.

 # 실패한 시도
 class Solution(object):
     def maxProfit(self, prices):
         j=1
       	 sell=0

       	 for i in range(len(prices)):
           	if j >= len(prices):
               	break

           	if prices[j-1] - prices[j] < 0:
               	for k in range(j,len(prices)):
                   	if sell > prices[j-1] - prices[k]:
                       	sell=prices[j-1] - prices[k]
           	j+=1
        
       	 return abs(sell)

하지만 for문을 사용하니 Time Over 상황이 발생하여 최종 테스트를 넘지 못했다. 그래도 for문 내의 연산과정을 줄이는 방향으로 수정을 해나갔다.

결국 중첩 for문을 통한 여러 시도 끝에 두개의 for문으로는 통과하기 힘들 것 같다는 판단을 내렸고, 처음 생각했던 대로 최소값, 최대값을 찾는 것을 다시 시도해보기로 했고, 여러 번의 시도 끝에 max와 min함수에 여러 값들을 담을 수 있다는 것을 알게 되어 다음과 같은 코드를 작성했다.

class Solution(object):
    def maxProfit(self, prices):
		# 없는 경우 0리턴
        if len(prices)==0:
            return 0
        
        # 가장 첫 값 정의
        buy=prices[0]
        sell=0

        for i in range(1,len(prices)):
        	# 첫 값과 다른 요소 중 가장 작은 값 반환
            buy=min(buy, prices[i])
            
            # 리스트 요소-가장 작은 값들, 그 값을 저장한 sell 들 중 가장 큰 값 반환
            sell=max(sell, prices[i]-buy)
        
        return sell

Runtime : 804ms
Memory : 22.6 MB

Runtime과 Memory 각각 상위 62%, 43%에 해당하는 수준의 코드였다. 리스트의 양이 매우 컸기 때문에 중첩 for문은 당연히 Time Over였고, 해당 코드도 겨우 통과한 것 같다.

📝 Best Time to Buy and Sell Stock 회고

여러 솔루션들을 찾아본 결과 현재 작성한 코드와 정말 유사한 코드가 있었다. 차이점은 리스트 내 요소가 없을 때 0을 리턴하는 조건이 없는 것과 for문의 범위 설정 뿐이었다. 현재 코드의 시간복잡도는 O(N), 공간 복잡도는 O(1)인 것도 확인 할 수 있었다.

그리고 비슷하지만 함수를 사용하지 않고 구현한 코드도 있었다. 어떤 차이점이 있는지 현재 코드를 조금만 수정하여 같은 접근 법으로 적용해보았다.

def maxProfit(self, prices):
        if len(prices)==0:
            return 0
            
        buy=prices[0]
        sell=0
        
        for i in range(1,len(prices)):
        	# 만약 리스트 첫 값이 prices[i] 보다 크면 buy를 prices[i]로 교체
            if buy > prices[i]:
                buy=prices[i]
            # 만약 (prices[i] - 주식을 구매한 가격)이 현재 저장한 판매금액 보다 크면 
            # 해당 값으로 교체 
            if sell<(prices[i]-buy):
                sell=prices[i]-buy 
        return sell

Runtime : 804ms ---> 748ms
Memory : 22.6 MB ---> 22.4 MB

의미는 이전에 작성한 코드와 그게 다르지 않다. 다만 함수를 활용하여 주식을 구매 가능한 최소값을 찾는 것이 아니라 조건에 해당하면 값을 초기화 해주는 것으로 구현한 것이다.

최대 판매 금액의 경우에도 max함수의 역할을 if문이 대신 해주고 있다. 조건에 해당하는 경우에만 값을 초기화 해주는 작업이 일어나기 때문에 이전 코드보다 56ms, 0.2MB 가량의 성능 개선 효과를 볼 수 있었다.

여러 코드들을 참고해보니 해당 문제의 경우 max(), min()함수를 활용하는 것 보다 수정된 코드 방법이 더 빠르다는 결론도 찾을 수 있었다. 여기서 더 개선을 하려면 변수명을 짧게 가져가서 메모리를 조금이나마 줄일 수 있을 것 같지만 숏코딩(?) 보다는 읽고 이해하기 쉬운 변수명이 나을 것 같아서 굳이 바꾸지는 않았다.

# Best Time to Buy and Sell Stock II

[Quetion]

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

[Example 1]

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

📌 접근법

이전 문제와 비슷한 문제 유형이지만 주식을 한 번만 살 수 있다는 조건에서 매일 주식을 사고 팔 수 있다는 조건으로 변경되었다는 것이 차이점이다.

그래서 굳이 최소값을 찾을 필요는 없다고 판단했고, 간단하게 생각해서 for문으로 리스트의 각 요소를 비교하여 다른 리스트에 저장하고 리스트 요소의 합을 반환하는 방법으로 시도해보았다.

class Solution(object):
    def maxProfit(self, prices):
        if len(prices)==0:
            return 0
        k = len(prices)
        sell=[]
        for i in range(k):
   			# i+1이 리스트 요소 개수를 벗어날 경우 반복문 탈출
            if i+1 == k:
                break
            # 만약 리스트 요소와 그 다음값을 비교하여 다음 값이 클 경우
            # 그 차이를 sell 리스트에 저장
            if prices[i] < prices[i+1]:
                sell.append(prices[i+1] - prices[i])
        # 리스트 내의 요소 합
        return sum(sell)

Runtime : 48ms
Memory : 14.18 MB

리스트의 개수대로 for문의 범위를 지정해주면 i+1의 경우, 인덱싱이 리스트의 범위를 벗어나기 때문에 if문을 통해 예외사항을 처리해주었다.

Memory는 상위 88% 정도로 비교적 높게 나왔지만 Runtime이 상위 25%로 비교적 느리게 나와서 아쉬웠다. 어떻게 하면 Runtime이 줄어 들 수 있을지 다른 솔루션들을 참고 해보았다.

📝 Best Time to Buy and Sell Stock II 회고

솔루션 기준 해당 코드와 정말 비슷한 코드가 있었다. 시간복잡도와 공간복잡도가 모두 O(N)이었다. 차이점은 for문의 범위를 다르게 줘서 if문을 한번 더 사용하지 않았다는 점이다. 그것을 제외하고는 같은 조건, append, sum 함수 사용한 점이 모두 같았다.

그리고 더 간단한 코드도 있었다. 리스트에 굳이 추가하지 않고, 정수형의 변수를 선언하여 해당 변수에 더해나가는 방법으로 구현한 코드였다. 만약 내가 작성한 코드에서 개선하려면 리스트에 저장하고 합을 구하는 과정을 변수 하나에 더해가는 과정으로 변경하여 공간 복잡도를 O(1)으로 개선할 수 있을 것 같다.

class Solution(object):
    def maxProfit(self, prices):
        if len(prices)==0:
            return 0
        k = len(prices)
        # 리스트가 아닌 변수로 할당
        sell=0
        # for문 범위에 -1을 해주어 if문 삭제
        for i in range(k-1):
            if prices[i] < prices[i+1]:
            	# append()가 아닌 sell에 더하기
                sell+=prices[i+1]-prices[i]
        return sell

Runtime : 47ms ---> 35ms
Memory : 14.18 MB ---> 14.5 MB

Runtime이 기존 코드에 비해 12ms 정도는 줄어드는 것으로 확인했다. 다만 Memory는 비슷한 양상을 보인다. 해당 문제에서는 변수에 더하는 방법과 리스트에 추가하여 값들을 합하는 방법은 비슷한 성능을 가지고 있다고 판단 할 수 있었다.

다른 사람들의 솔루션들을 참고해보니 비슷한 방법으로 접근하는 사람들도 많고, 생각지도 못한 방법으로 접근하는 사람들도 많다는 것을 느꼈다. for문 하나와 조건문 하나인 것을 보았을 때 return에 for문과 if문 한 줄로 작성하여 메모리를 조금 더 개선해 볼 수는 있을 것 같다.

하지만 그렇게 구현하는게 좋은 코드인지는 사실 잘 모르겠다. 읽기 쉽고 이해하기 쉬운 코드가 더 좋다고 생각한다.

# Jump Game

[Quetion]

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

[Example 1]

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

📌 접근법

문제의 핵심은 마지막 인덱스에 도달할 수 있느냐를 판별하는 걸로 이해했다.

처음 시도한 방법은 0번째 값으로 다음 인덱스를 탐색해서 리스트에 저장하고 그 값에서 마지막 값을 빼면 마지막 인덱스에 도달 했다는 뜻이므로 True를 반환하도록 구현의 방법으로 접근했다.

하지만 생각처럼 되지 않았고, 다른 테스트 케이스에 막혀 접근 자체가 잘못되었다고 판단했다.

# 실패한 시도
class Solution(object):
    def canJump(self, nums):
        count=len(nums)
        result=0
        i=0
        j=nums
        # 예외사항 처리
        if nums[0]==0:
            return True
		
        # 예외사항 처리
        if nums[j[0]]==0:
            return False
        
        while nums:
            if i > count:
                break
            if i >= 0:
                result+=nums[i]
                i+=nums[i]
        if result-nums[-1]+1 == count:
            return True
        else:
            return False

그래서 아예 방법을 바꾸어서 for문으로 리스트의 값만큼 리스트의 왼쪽 부터 삭제해나가는 방법으로 시도해보았으나 해답이 나오지 않아서 결국 이전에 보았던 알고리즘 책을 참고하여 어떤 유형인지 파악해보려고 했다.

문제에서는 가장 최적의 점프 길이를 나타내고 있어서 그리디 알고리즘을 기준으로 생각해보았다. 최적의 값은 리스트 길이에서 1을 뺀 값으로 정의하고, 반복문은 역순으로 리스트 끝에서 부터 처음 값을 탐색하도록 구현해보았다.

class Solution(object):
    def canJump(self, nums):
        best=len(nums)-1
        
        for i in range(best,-1,-1):
            if best-i <= nums[i]:
                best = i
        
        if best == 0:
            return True
        else:
            return False

Runtime : 343ms
Memory : 14.3 MB

📝 Jump Game 회고

책을 보기 전까지는 구현의 방법으로만 시도하여 어떻게 접근해야할지 갈피를 못잡은 느낌이었다. 역순으로 생각한 아이디어도 처음부터 그랬던 것은 아니고, 정방향으로 생각했을 때의 코드에 오류가 발생하여 여러번 시도하다가 역순으로 반복해보자는 아이디어를 얻었다.

아직 문제를 보고 어떤 알고리즘을 적용해야할지 판단하는 것이 많이 부족한 것 같아서 많은 노력이 필요할 것 같다.

여러 솔루션들을 참고해보니 그리디 알고리즘으로 접근하는 방법도 많았고, BFS로 접근하는 방법도 있었다. 그리고 max() 함수를 이용해서 시간복잡도 O(n), 공간복잡도 O(1)로 구현한 단순한 코드도 있었다.

현재 코드도 시간복잡도 O(n), 공간복잡도 O(1)를 지니고 있어서 비슷한 성능을 낼 수 있을거라 생각하며 다른 코드들을 본 결과 for문을 탈출한 이후의 if문은 따로 없어도 될 것 같다고 판단해서 불필요한 코드를 지우는 방향으로 개선해보았다.

class Solution(object):
    def canJump(self, nums):
        best=len(nums)-1
        
        for i in range(best,-1,-1):
            if best-i <= nums[i]:
                best = i
        # if-else 구문 제거 및 간소화
        return best==0