[LeetCode] 496 - Next Greater Element 1

문제

 

위 문제는 nums1 리스트와 nums2 배열이 주어지는데, nums1의 원소는 모두 nums2에 들어있고, nums1의 각 원소에 대해 nums2 안에서의 다음 큰 수를 찾는 문제이다. 

 

조건

nums1에 있는 모든 숫자는 nums2에 있고(포함), nums1 과 nums2에 있는 숫자는 모두 고유하다(중복 X)

 

풀이(1)

처음 문제를 보고 생각해보았을때는 for문을 이중으로 돌리면 되지 않을까 ? 하고 먼저 풀어보았다. nums1의 각 숫자에 대해 nums2에서 그 숫자의 위치를 찾고 그 위치에서부터 뒤로 가면서 처음으로 나오는 더 큰수를 찾는 코드를 사용하였다. 

 

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
    res = []
    for i in nums1:
        # nums2에서 i의 인덱스 탐색
        index = nums2.index(x)
        
        # i 오른쪽부터 다음 큰 수 탐색
        next_greater = -1
        for j in range(index + 1, len(nums2)) :
            if nums2[j] > i : # 오른쪽에서 더 큰 수를 찾았을 시에 
                next_greater = nums2[j]
                break 
        
        res.append(next_greater) # 나온 값을 결과 리스트에 append
    return res

 

 

 

풀이(2) - Stack버전

위의 풀이를 생각하던 중, 그 바로 전의 이중 반복문을 사용하는 풀이는 시간적으로 보았을때 O(n²)나 걸릴 것 같고, stack을 사용하면 더 시간을 줄일 수 있지 않을까 ?라고 생각해 고민을 조금 더 해봤을 때, 다음과 같은 풀이를 생각했다.

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:

        stack = [] #더 큰수를 찾지 못한 숫자 저장
        greater = {} #키:값으로 형식으로 저장하기 위해 딕셔너리 사용

		#nums2에 있는 값들에 대한 다음 큰 수 매칭, 딕셔너리에 추가
        for i in nums2 : 
            while stack and i > stack[-1] : #스택에 있는 수보다 크면 : 
                prev_num = stack.pop() 
                greater[prev_num] = i
            stack.append(i)
        
  #stack에서 보다 큰 수가 있는 숫자는 이미 매칭 완료,
  #그렇다면 현재 여기 들어있는 수는 매칭이 안된 수이므로 -1로 매칭
        while stack : 
        	prev_num = stack.pop()
            greater[prev_num] = -1
        
        #res 리스트를 선언해서 nums1에 맞는 값 list에 순서대로 추가
        res = []
        for i in nums1 : 
          res.append(greater[i])
        
    	return res

 

 

풀이 알고리즘 : 

 

stack을 선언해 아직 더 큰 수를 찾지 못한 숫자를 저장

-> stack 맨 위에 있는 숫자보다 클 경우에, greater 딕셔너리를 선언해 숫자 - 값 형태로 저장

-> 매칭이 되지 않은 숫자들은 보다 오른쪽에 더 큰 수가 없는 경우이기 때문에 -1을 매칭

-> 이후에 nums1 ⊂ nums2 인 관계이기 때문에 반복문을 사용해서 res 리스트에 결과값을 추가하여 반환 

 

 

언뜻 보면 이중 반복문 문제로 생각할 수 있지만, 스택을 사용하면 더 효율적으로 문제 풀이가 가능한 문제였다.