오늘은 프로그래머스의 뒤에 있는 큰 수 찾기라는 문제를 풀어 보았다.
문제 설명은 다음과 같다.
문제 설명
정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.
정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.
제한사항
- 4 ≤ numbers의 길이 ≤ 1,000,000
- 1 ≤ numbers[i] ≤ 1,000,000
위 문제는 다음 큰 숫자를 찾는 문제이다.
문제를 보고 처음으로 생각한 풀이는 정수 배열을 보고 해당 숫자와 뒤에 나머지 숫자를 비교해서 큰 숫자가 나오면 그 값을 정답 배열에 써주는 풀이였다.
테스트를 쉽게 통과하고 정답이 나오나 했는데 20 ~ 23번 4문제가 시간초과가 떠서 다른 풀이를 생각해보기로 했다.
다음으로 생각한 풀이는 스택을 사용한 풀이이다.
스택에 정수 배열의 맨 뒤의 값을 저장하고 정수 배열의 마지막 바로 전부터 시작해서 스택의 숫자와 비교하여 스택에 해당 숫자보다 큰 수가 나올때 까지 스택을 pop하고 큰 수가 나왔다면 그 수를 정답 배열에 써주는 방법이다.
그리고 해당 숫자는 stack에 넣어준다.
이렇게 풀이를 해보니 정답을 받을 수 있었다.
풀이 코드는 다음과 같다.
import java.util.*;
class Solution {
public int[] solution(int[] numbers) {
int[] answer = new int[numbers.length];
for (int i = 0; i < numbers.length; i++) {
answer[i] = -1;
}
Stack<Integer> stack = new Stack<>();
stack.add(numbers[numbers.length - 1]);
for (int i = numbers.length - 2; i >= 0; i--) {
int num = -1;
while(!stack.isEmpty()) {
if (stack.peek() > numbers[i]) {
num = stack.peek();
break;
}
stack.pop();
}
answer[i] = num;
stack.push(numbers[i]);
}
return answer;
}
}우선 numbers의 길이만큼 answer 배열을 선언 후 -1로 초기화를 시켜준다.
그리고 스택을 선언 후 스택에 numbers의 맨 마지막 값을 push해준다.
numbers의 맨끝의 바로 앞 부터 맨 앞까지 반복문을 돌려주는데 이 반복문 내부에서는 스택을 채워주면서 정답을 써줄 것이다.
반복문 안의 로직을 보면 우선 num 변수를 -1로 초기화를 시켜준다.
이유는 스택에 다음 큰 값이 존재하지 않으면 -1을 정답 배열에 써주기 위함이다.
그리고 스택이 빌 때까지 반복문을 돌려준다.
이 안에서는 스택에 현재 값보다 큰 값이 있으면 num에 저장하고 반복문을 종료하고 아니라면 맨 위의 값을 계속 pop 시켜서 제거해준다.
이렇게 pop을 해서 이후의 값을 없애도 되는 이유는 현재 값보다 작은 값은 나중에 현재 값을 스택에 담아주게 되면 필요가 없어지기 때문에 상관이 없다.
반복문이 종료 후 이후의 다음 큰 값을 찾았다면 num에는 그 값이 들어가 있을 것이고, 찾지 못했다면 num에는 그대로 -1이 존재할 것이다.
이 값을 정답 배열에 써주고 스택에 현재 값을 push하는 것을 반복해준다.
반복문 종료 후 answer를 반환하면 정답을 받을 수 있다.
