프로그래머스 뒤에 있는 큰수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/154539?language=java

프로그래머스

- 문제는 간단하다. 배열의 모든 원소를 탐색하는데 각원소의 가장 가까운 원소중에, 가장 큰 원소를 answer[] 배열에 넣어서 반환하면 끝.

- 완전탐색으로 문제를 해결하면 마지막 4문제에서 시간초과가 나는데 최적화가 필요하다.

- Stack을 사용해서 뒤에서부터 단일 순회 방식을 사용하면 O(n) 시간 복잡도에 끝낼 수 있다.

 

* 핵심 코드만 공유하겠다.

	for (int i = size - 1; i >= 0; i--) {
        // 스택의 탑이 현재 숫자보다 작거나 같으면 제거
        while (!stack.isEmpty() && stack.peek() <= numbers[i]) {
            stack.pop();
        }

        // 스택이 비어있으면 더 큰 숫자가 없음
        if (stack.isEmpty()) {
            answer[i] = -1;
        } else {
            // 스택의 탑이 현재 숫자보다 큰 첫 번째 숫자
            answer[i] = stack.peek();
        }

        // 현재 숫자를 스택에 푸시
        stack.push(numbers[i]);
    }

 

1) 배열 뒷쪽부터 차례대로 순회한다.

2) while() 루프에서 stack이 비어있는지 확인과 스택 제일 윗 부분과 현재 numbers 배열을 확인하여

스택에 있는 값이 더 크지않다면 pop() 한다. 즉 현재 numbers 배열에 있는 값보다 큰 값이 나올때까지 pop 하는것.

3) while() 루프에서 큰값이 없어서 모두 pop() 했다면 더 큰 수가 없다는 의미로 -1 할당해주고, 아니면 큰 값을 찾았다는 의미로 stack의 제일 위에 값을 할당한다.

4) 현재 numbers 값을 stack에 넣고 다음 루프를 실행함.

 

요약하면 stack의 제일 윗 값과 현재 numbers를 비교하는데, stack의 값이 클때까지 pop() 하고 stack의 값의 유무에 따라서 -1과 첫 번째 숫자를 할당하는 것.

 

나중에 한번더 풀어봐야할 문제이다.