CareTim

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.

해당 날짜의 특정 주식 가격을 나타내는 prices배열 이 제공됩니다 .prices[i]ith

특정 주식을 구매할 하루를 선택하고 해당 주식을 판매할 미래의 다른 날을 선택 하여 수익을 극대화하려고 합니다 .

이 거래에서 얻을 수 있는 최대 이익을 반환합니다 . 이익을 얻을 수 없으면 를 반환하십시오 0.

풀이

최초풀이 - 리스트에서 for문을 통해 값을 순회하며 뒤의 숫자와 비교하여 차액이 가장 큰 곳을 찾았다 .

def maxProfit(self, prices):
    result = 0
    for i in range(len(prices)): # 각 날짜의 가격을 순회하며 현재위치에서 뒤의 인덱스의 값을 계산 후 비교
        for j in range(i+1,len(prices)):
            if prices[j]- prices[i] > result:
                result =  prices[j]- prices[i]
    return result
    시간복잡도 n^2

시간초과가 떴다  ㅎㅎ.. 브루트포스로는 안되나보다..

생각을해보니 가장 차액이 큰 걸 찾기위해서 그냥 for문을 돌면서 최솟값과 최대값을 갱신하며 차액을 구하면된다는걸 깨달았다. 

[9,1,1,1,8] 이런식으로 숫자가 배열된다면 최대값을 9 최소값을 1로 판단해서 8을 반환하겠지..?

그냥 최솟값만 가지고가면서 각 숫자를 계산해주기만 하면 되는 간단한 문제가 아닐까? 

class Solution(object):
    def maxProfit(self, prices):
        result = 0  			# 최대이익값 
        min_value = prices[0]   # 최초에 첫번째 값을 가장 작은값으로 측정 
        for i in prices:    	#for문으로 각 날자별 가격 순회
            if i < min_value:   # 가장 작은 값 비교  작다면 작은 값 갱신 
                min_value = i
            if result< i- min_value: # 가장 작은 값과 현재 인덱스의 값을 비교 
                result = i- min_value
        return result
        
 #sudo
 result = 최고이익
 min_value = 현재까지 나온 값 중 제일 적은 값
 for 당일가격  in 각 날자 별 가격리스트: 
 	if 당일가격 < min_value (제일 적은 값):
    		제일 적은 값 = 당일 가격
    if 최고이익 < 당일가격 - 제일 적은 값:
    	최고이익 = 당일가격 - 제일 적은 값
retrun 제일 적은 값

맞다.. 그냥 제일 작은 값을 가지고 각 리스트를 돌며 비교해주니 솔했다 굳굳

class Solution:
    def maxProfit(self,prices):
        left = 0 #Buy
        right = 1 #Sell
        max_profit = 0
        while right < len(prices):
            currentProfit = prices[right] - prices[left] #our current Profit
            if prices[left] < prices[right]:
                max_profit =max(currentProfit,max_profit)
            else:
                left = right
            right += 1
        return max_profit

투포인터를 이용해서 문제를 푸는 방법 각 위치를 움직이며 최대이익값을 그리디하게 찾는다.

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

풀이

단순하게 슬라이싱을 통해서 두 리스트를 나눈 뒤 합치면 되겠다고라고 생각했지만 리트코드에서는 nums 내부에서 해결하길 원한다.. 백준을 풀때는 단순히 문제를 풀면 된다는 생각에 메모리 상관없이 사용했던거같은데 리트코드를 풀면서 새로운 부분을 깨닫게 된다.

처음에 단순하게 각 리스트를 k번쨰 인덱스부터 k를 인덱스를 합쳐서 넣자고 생각하고 문제를 풀었더니 틀렸다

로테이션으로 값이 한칸씩 움직이길 원하는데 원소의 개수만큼 더해주고 빼주는 방식으로하게되면 nums =[0] 또는 nums=[1,2]의 케이스에서 답안이 계속 틀렸다

최초의 코드

class Solution:
    def rotate(self,nums, k):
        len_num= len(nums)
        result = nums[-k:] + nums[:len_num-k]
        nums.clear()
        for i in result:
            nums.append(i)

k가 범위를 넘어설때 그냥 k를 총 원소의 개수로 나누고  k번째인덱스의 앞부분과 뒷부분을 나눠서 슬라이싱한 후 다시 합쳐서 넣어주면 되었다.

이후에 전의 문제에서 배운 [:] 현재 배열에서 원소를 조작하는 방법을 통해 문제를 풀었던게 생각나서 다른 배열을 추가하지 않고 인덱스 내에서 재조합되게 만들었다.

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        len_num= len(nums)
        k= k%len_num
        result = nums[-k:] + nums[:-k]
        nums.clear()
        for i in result:
            nums.append(i)
            
            


def rotate(nums, k):
    if len(nums)!=1 and k !=0:
        
        len_num= len(nums)
        k = k%len_num
        nums [:]= nums[-k:] + nums[:len_num-k]
        
        print(nums)

다른사람이 작성한 슬라이싱을 사용하지 않고 리스트를 추가하여 각 인덱스의 숫자를 넣어서 다시 새배열에 배치하는 방법 

class Solution:
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        a = [0] * len(nums)
        for i in range(len(nums)):
            a[(i+k)%len(nums)] = nums[i] #recycle

        for i in range(len(nums)):
            nums[i] = a[i]

class Solution(object):
    def majorityElement(self, nums):
        dict={}          #딕셔너리 생성 
        for n in nums:   # nums숫자 for문으로 순회 
            if n not in dict: # n이 딕셔너리안에 존재하지 않는다면 
                dict[n] = 1   # 키:값 생성
            else:
                dict[n]+=1    # 존재한다면 해당 키의 값 +1

        return (max(dict,key=dict.get))  # 딕셔너리의 값 중 가장 큰 값의 키 리턴​
        
        
#sudo 

  def majorityElement(self, nums):
        dict={}          #딕셔너리 생성 
        for n in nums:   # nums숫자 for문으로 순회 
            if n not in dict: # n이 딕셔너리안에 존재하지 않는다면 
                dict[n] = 1   # 키:값 생성
            else:
                dict[n]+=1    # 존재한다면 해당 키의 값 +1

        return (max(dict,key=dict.get))  # 딕셔너리의 값 중 가장 큰 값의 키 리턴​

조회수가 가장 높은 python 코드

#1
def majorityElement1(self, nums):
    nums.sort()
    return nums[len(nums)//2]
    
    
    
#2
def majorityElement(self, nums: List[int]) -> int:
    majorityMap = Counter(nums)
    return max(majorityMap, key=majorityMap.get)

첫번째는 배열의 가장 큰 값은 중앙에 있기에 정렬 후 가운데 위치에 있는 수를 가져오는 방법이지만 예외케이스 발생

ex) arr = [2,2,5,5,1,1,10,10,11,11,11] sorted(arr)[len(arr)//2]는 11이 아닌 5를 반환

두번째는 counter 메소드를 사용해서  dict를 사용해서 만든 방법과 동일하게 사용 

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

풀이

처음에는 딕셔너리나 리스트를 통해서 방문리스트를 만든 후 카운트를 넘는다면 수를 제외하고 새로운 인덱스에 넣어서 

nums리스트를 모두 비우고 넣는 방식을 생각했었다.

하지만 문제에서 새로운 배열을 만드며 메모리를 사용하지말라는 조건 떄문에 다른 방법을 생각했다.

이전의 문제에서 투포인터로 문제를 풀었었고 다른 사람의 코드를 보며 좀 더 깔끔하게 짤 수 있다는 사실을 알고 

투포인터를 통해서 문제를 풀어봤다. 기존에 풀었던 코드는 위치 포인터와 새로운 값을 지정하는 변수등이 많아서 보기 지저분했는데  이번에 짠 코드는 좀 더 직관적인거 같다.  

포인터를 시작과 끝에 두지 않고 일정 기준에 충족하는 값인지 확인한 후 앞으로 증가해나가는 방식으로 푼건 처음인거같다. 

class Solution(object):
    def removeDuplicates(self, nums):
        cnt = 1 # 체크를 1번 인덱스부터 하는게아니라 0번인덱스부터 시작 [0] ,[1] 인덱스부터 체크하기에 미리 cnt=1로 지정
        index =0  #숫자를 넣어줄 포인터(인덱스포인터)
        for i in range(1,len(nums)): # for문으로 1번부터 원소 끝까지 체크
            if nums[i] != nums[index]: # 인덱스 포인터와 지금 현재 위치의 수가 다르다면 
                cnt=1       		  # 동일한 숫자가 아니라면 새로운 숫자, 횟수 1번 카운트
                index+=1              # 인덱스 번호 +1 (이미 전의 인덱스는 옳게 배치되어있음)
                nums[index]=nums[i]   # 인덱스포인터가 가르키는 위치에 현재 숫자로 변경
            elif nums[i] == nums[index] and cnt<2: # 두 포인터 인덱스 수가 같고 count된 수가 2 이내라면 
                cnt+=1				  # 같은 수 체크 횟수 증가
                index+=1			  # 인덱스포인터 +1 증가
                nums[index]=nums[i]   # 인덱스포인터의 위치의 숫자를 현재위치의 수로 변경
        return index+1                # index포인터가 끝나는 위치 체크 
 
 
 #sudo
 
 class Solution(object):
    def removeDuplicates(self, nums):
        cnt =  동일한 숫자가 나온 횟수
        index = nums에 지정해줄 인덱스의 위치 
        for i in range(배열의 두번째수부터 끝번수 ): 
        	if nums[i] != nums[index]: 두 수가 다르다면 index의 위치에 숫자를 변경
                cnt = 최초발견 카운트 1로 지정
                index+= 위치 +1 증가 ( 기존값이 옳은값인걸 확인가능)
                nums[index]=nums[i]   
            elif nums[i] == nums[index] and cnt<2:  # 두 수가 다르지만, 카운트가 한번이라면
                cnt+=1				  #위의 코드 반복 
                index+=1			  
                nums[index]=nums[i]   
                
        return index+1 #새로 배정된 수의 끝번 체크 , 인덱스를 넘어가는 원소는 버리는 원소

제일 투표를 많이 받은 python코드 

def removeDuplicates(self, nums):
    i = 0
    for n in nums:
        if i < 2 or n > nums[i-2]: #문제에서 동일한 수가 2개까지 가능하므로 3번째인덱스부터 체크,
        							#현재 위치에서 -2번쨰 숫자보다 크다면 
            nums[i] = n				
            i += 1
    return i

직관적이고 이해하기 쉬운코드인거같다. 

처음엔 투포인터 코드를 보고 이해하기어려워서 파이썬튜터도 돌려봤었는데 이젠 조금 코드를 금방 이해하는거같다.

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
• Return k.

풀이법

처음엔 set을 사용해서 그대로 제출하려했지만 문제에서 원하는 자료구조 타입이 아니라 반려됬다.

그래서 그냥 nums의 원소를 다 비워버리고 set시킨 원소들로 다시 채워주는 법을 생각했다.

class Solution(object):
    def removeDuplicates(self, nums):
        set_nums = set(nums)
        for __ in range(len(nums)):
            nums.pop()
        for i in set_nums:
            nums.append(i)
        nums.sort()



#sudo

    def removeDuplicates(self, nums):
        set_nums = set(nums) #nums의 수를 set로 중복제거한다.
        for __ in range(len(nums)): nums의 원소를 모두 pop으로 비워준다.
            nums.pop()
        for i in set_nums: #set시킨 원소를 다시 넣어준다.
            nums.append(i)
        nums.sort()

1.set을 이용해서 문제를 푼 다른 사람의 코드 

방법 1: 다음을 사용하여 제자리 정렬[:]
	def removeDuplicates(self, nums: List[int]) -> int:
		nums[:] = sorted(set(nums))
		return len(nums)
시간 복잡도: O(n)
공간 복잡도: O(1)

❌ 일반적인 오답:
	nums = sorted(set(nums))
	return len(nums)
 nums =  원래 목록의 요소를 대체하지 않습니다.
nums[:] = 요소를 제자리에 대체합니다.

간단히 말해서, 없이 [:], 우리는 이 문제가 요구하는 것과 반대되는 새로운 목록 객체를 생성하고 있습니다:
"다른 배열에 추가 공간을 할당하지 마십시오. O(1을 사용하여 그 자리에서 입력 배열을 수정하여 이를 수행해야 합니다. ) 추가 메모리."

[:]를 통해서 제자리에서 정렬 할 수 있다는 사실을 처음알았다. 

2. 투포인터를 사용한 다른 사람의 코드 

	def removeDuplicates(self, nums: List[int]) -> int:
		j = 0
		for i in range(1, len(nums)):
			if nums[j] != nums[i]:
				j += 1
				nums[j] = nums[i]
		return j + 1

이 문제도 동일하게 nums의 배열을 그대로 두고 내부에서 수를 바꿔줘야했다.

숫자를 delete로 지워줄까 생각했지만 투포인터로 사용하게되면 O(n)으로 풀 수 있겠다 생각이 들어서 투포인터를 사용해서 풀었다.

앞포인터의 숫자가 제거해야 할 val의 숫자와 동일하다면 뒷포인터와 앞포인터의 숫자를 교체 한 후 

뒷포인터의 위치를 -1 움직여준다.

다시 동일하게 시행한 후 숫자를 모두 교체한 후 교체된 횟수만큼 뒤에서 pop으로 숫자를 제거해준다. 

class Solution(object):
    def removeElement(self, nums, val):
        cnt = 0 #숫자의 카운트 
        move =0 
        num_count = len(nums)-1
        while move <= num_count:
            changeNum= nums[num_count]
            if nums[move]== val :
                nums[num_count] = nums[move] 
                nums[move] = changeNum
                num_count-=1 
                cnt+=1
            else:
                move+=1
        for __ in range(cnt):
            nums.pop()


#sudo
class Solution(object):
    def removeElement(self, nums, val):
        cnt = 교체횟수 
        move = 앞 포인터 
        num_count = 뒷 포인터
        while 포인터의 위치 <= nums의 갯수:  # move 포인터의 위치가 위치포인터를 넘어서거나 동일해지면 정지
            changeNum= nums[뒷 포인터]
            if nums[포인터의위치]== val : 
                nums[num_count] = nums[move]  # 앞포인터와 뒷 포인터의 숫자를 맞교환
                nums[move] = changeNum # 앞포인터와 뒷 포인터의 숫자를 맞교환
                num_count-=1  # 뒷 포인터 위치 -1 감소
                cnt+=1   # 교체한 횟수
            else:
                move+=1  # 앞포인터 위치 +1 증가
        for __ in range(cnt): # 교체한 횟수만큼 pop실행
            nums.pop()

투표를 제일 많이 받은 코드 

def removeElement(self, nums, val):
    i = 0
    for x in nums:
        if x != val:
            nums[i] = x
            i += 1
    return i

알고보니 그냥 nums의 리스트 안에 숫자를 넣어서 제출하면 되는 문제였다.. 영어이슈 .. 

LeetCode - 88. Merge Sorted Array

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        for __ in range(n):
            nums1.pop()
        for i in nums2:
            nums1.append(i)
        nums1.sort()
        
        
      
 #sudocode
  def merge(self, nums1, m, nums2, n):
        for __ in range(0을 제외시켜야할 수 ):
            nums1.pop()
        for i in nums2:(nums2의 원소를 nums1에 추가해준다)
            nums1.append(num2의 원소)
        nums1.sort() (합쳐진 nums1의 원소들을 sort()함수를 통해 오름차순 정렬
        
        
 시간복잡도
 O(m+n)

LeetCode에서 제일 많은 투표를 받은 해결방법

class Solution(object):
    def merge(self, nums1, m, nums2, n):
      for j in range(n):
          nums1[m+j] = nums2[j]
      nums1.sort()
      
      
접근법: 두 포인터
각각 m-1과 n-1로 초기화된 두 개의 포인터 i와 j로 시작할 수 있습니다. 
또한 m+n-1로 초기화된 또 다른 포인터 k를 갖게 되며, 
이는 더 큰 요소를 배치할 nums1의 위치를 ​​추적하는 데 사용됩니다. 
그런 다음 배열 i와 j의 끝부터 반복을 시작하고 이 위치의 요소를 비교할 수 있습니다.
nums1의 더 큰 요소를 k 위치에 배치하고 이에 따라 해당 포인터 i 또는 j를 감소시킵니다. 
nums2의 모든 요소를 ​​반복할 때까지 이 작업을 계속할 것입니다. 
nums1에 아직 요소가 남아 있으면 해당 요소가 이미 올바른 위치에 있으므로 아무것도 할 필요가 없습니다.

복잡성
시간 복잡도: O(m+n)
두 배열을 한 번 반복하므로 시간 복잡도는 O(m+n)입니다.

공간 복잡도: O(1)
추가 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다.