Skip to content

Latest commit

 

History

History
40 lines (33 loc) · 2.58 KB

풀이_LC496.md

File metadata and controls

40 lines (33 loc) · 2.58 KB

😛 496. Next Greater Element I

  • Date : 2021.10.03(일)
  • Time : 30분

Problem

  • The next greater element of some element x in an array is the first greater element that is to the right of x in the same array. You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2. For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1. Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Constraints

  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 10^4
  • All integers in nums1 and nums2 are unique.
  • All the integers of nums1 also appear in nums2.

Example

  • Input: nums1 = [2,4], nums2 = [1,2,3,4]
  • Output: [3,-1]
  • Explanation: The next greater element for each value of nums1 is as follows:
    • 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
    • 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.

풀이

    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nextNumber = {}
        for i in range(len(nums2)):
            for j in range(i + 1, len(nums2)):
                if nums2[j] > nums2[i]:
                    nextNumber[nums2[i]] = nums2[j]
                    break
        for i in range(len(nums1)):
            nums1[i] = nextNumber.get(nums1[i], -1)
        return nums1

: 이 문제는 num1의 숫자의 인덱스를 num2에서 찾은 후 nums2에서 그 인덱스 뒤에 num1의 숫자보다 큰 값이 있다면 가장 가까운 큰 값을 찾아서 입력하고, 없다면 -1을 입력하는 방법이다. 이 해설을 그대로 풀 수도 있지만 조금 다른 방식으로 풀어봤다. 먼저 nums2에서 각 원소마다 검사를 통해 그 뒤에 더 큰 숫자가 뭔지 확인해두는 방식이다. 이게 첫번째 for문의 알고리즘이다. nums2의 원소를 하나 기준으로 잡고 그 원소의 인덱스보다 큰 nums2 원소들을 검사해주었다. 만약 뒤에 더 큰 값이 존재한다면 그 값을 딕셔너리에 저장 후 break 문으로 for문을 종료해주었다. 이렇게 첫번째 for문을 다 돈다면 (예시로 Example에 있는 숫자를 이용) nextNumber = {1:2, 2:3, 3:4} 이라는 값이 존재할 것 이다. 이제 두번째 for문을 통해 값이 있다면 가져와주고 아니라면 -1을 가져와주면 된다.