[LeetCode] 503. Next Greater Element II

[문제 링크]

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

 

 

[문제]

정수 배열 nums가 원형 배열(circular array) 형태로 주어진다.

각 원소에 대해 오른쪽 방향으로 다음으로 큰 원소(next greater element)를 찾는다.

배열이 원형이므로, 배열의 끝에 도달하면 다시 처음부터 탐색할 수 있다.

만약 다음으로 큰 원소가 없다면 -1을 저장해야 한다.

결과를 동일한 크기의 배열로 반환하라.

[풀이 과정]

문제를 보았을때 조건을 보고 모든 것을 탐색하면 안 되겠다는 생각이 들었지만혹시나 하는 생각에 완전 탐색을 이용하여 풀었지만 예상과 같이 실패하였습니다.

 

 

처음 틀린 코드 (예상했던 시간 초과)

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        // 답을 적을 새로운 배열 
        int[] answer = new int[nums.length];

        // 처음부터 탐색
        for(int i = 0; i<nums.length; i++) {
            // 비교 대상
            int target = i;

            // 비교 대상의 index를 늘려가며 탐색
            while(nums[target] <= nums[i]) {
                target++;

                if(target == i) {
                    answer[i] = -1;
                    break;
                }

                // 원형 배열이기 때문에 마지막 인덱스를 넘을시 인덱스 0으로 초기화
                if(target == nums.length) {
                    target = 0;
                }

                if(nums[target] > nums[i]) {
                    answer[i] = nums[target];
                    break;
                }
            }
        }

        return answer;
    }
}

 

 

 

이후 계속 생각을 해봤지만 생각이 나질 않아 결국 풀이 방법을 보게 되었습니다.

Stack을 잘 응용하여 푸는 문제였습니다.

[코드]

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        Stack<Integer> stack = new Stack<>();
	    
        // 본인보다 큰게 없으면 -1로 해야하기 때문에 초기화
        for(int i = 0; i<n; i++) {
            answer[i] = -1;
        }

        for(int i = 0; i<n*2; i++) { // 원형 배열이기 때문에 다 확인하려면 두번 돌아야 함
            int num = nums[i%n];// 최대 index 넘지 않기 위해

            // 스택의 마지막 인덱스의 값이(nums[꺼낸 인덱스]) num보다 작으면
            // 본인보다 큰 값을 찾았기 때문에 pop하고 answer에 등록
            while(!stack.isEmpty() && nums[stack.peek()] < num) {
                answer[stack.pop()] = num;
            }
			
            // 모든 인덱스를 stack에 한 번만 push 하기 위해 둔 조건
            if(i < n) {
                stack.push(i);
            }
        }

        return answer;
    }
}

[회고]

Stack을 활용해야겠다라는 생각은 들었지만 결국 답을 구해내진 못했습니다.

코딩테스트가 많이 부족하다는걸 또 느낍니다.

포기하지 않고 계속 나아가겠습니다.

 

 

 

 

질문과 피드백은 언제나 환영입니다.

감사합니다.