[LeetCode]Next Greater Element I

https://leetcode.com/problems/next-greater-element-i/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

nums1과 nums2 리스트가 주어집니다. nums1 리스트는 nums2 리스트의 subset입니다. nums1의 숫자가 nums2에서 위치한 곳보다 뒤에서 큰 숫자를 발견하면 그 숫자를, 아니라면 -1을 리턴하는 문제입니다.

 

처음 시도한 답안

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        next_greater_dict = {}
        stack = []

        for num2 in nums2:
            while stack and stack[-1] < num2:
                num = stack.pop()
                next_greater_dict[num] = num2

            stack.append(num2)

        for idx, num1 in enumerate(nums1):
            if num1 in next_greater_dict:
                nums1[idx] = next_greater_dict[num1]
            else:
                nums1[idx] = -1

        return nums1

접근 방법

1. 스택과 해시 테이블을 이용하는 문제입니다.
2. next_greater_dict에는 key에는 숫자 value에는 발견한 큰 값을 기록합니다. stack은 이전에 등장한 값들보다 큰 값을 발견했는지 유무를 체크하는데 사용됩니다.
3. nums2 리스트를 순회합니다.
   1. 스택에 값이 있고 스택의 마지막 값이 현재 등장한 숫자보다 큰 동안 순회합니다.
      1. 스택에서 pop하고 pop한 값을 키로 등장한 숫자를 value로 하여 큰 숫자에 대한 정보를 기록합니다.
   2. 스택에 등장한 숫자를 추가합니다.
4. nums1을 순회하면서 next_greater_dict에 값이 있다면 value값 없다면 -1로 지정합니다.

만약 스택에 남아있는 값이 있다면 해당 숫자보다 큰 숫자를 찾지 못했거나 nums1에는 존재하지 않는 숫자라는 뜻입니다. 큰 숫자를 찾은 숫자들은 모두 next_greater_dict에 기록되어 있으므로 스택에 남아있는 값은 무시해도 상관없습니다.