[뒤에 있는 큰 수 찾기] 코딩테스트 연습 > 연습문제 > 뒤에 있는 큰 수 찾기
틱톡라이트 초대링크 https://lite.tiktok.com/t/ZSjqX7SfC/
[기간 한정] 보는 재미로, 버는 재미로! 영상만 봐도, 좋아요만 눌러도, 검색만 해도, 포인트가 차
www.tiktok.com
※ 주의 : 문제풀이 방법은 다양합니다. 참고만 해주세요 ※
[문제설명]
정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.
정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.
제한사항
- 4 ≤ numbers의 길이 ≤ 1,000,000
- 1 ≤ numbers[i] ≤ 1,000,000
입출력 예
입출력 예 설명
입출력 예 #1
2의 뒷 큰수는 3입니다. 첫 번째 3의 뒷 큰수는 5입니다. 두 번째 3 또한 마찬가지입니다. 5는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [3, 5, 5, -1]이 됩니다.
입출력 예 #2
9는 뒷 큰수가 없으므로 -1입니다. 1의 뒷 큰수는 5이며, 5와 3의 뒷 큰수는 6입니다. 6과 2는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [-1, 5, 6, 6, -1, -1]이 됩니다.
[간단설명]
현재 위치를 기준으로, 뒤에 있는 숫자중에서 가장 근접한 큰수를 찾는 문제
[접근방법]
1. 스택을 만든다.
2. numbers 배열을 뒤에서 부터 앞으로 뒤진다.
3. 바로 뒤에 숫자가 큰수면, 스택에 넣고 정답을 저장한다.
4. 바로 뒤에 숫자가 큰수가 아니면, 스택을 뒤진다.
5. 스택에 있으면, 정답 저장
6. 스택에 없으면, -1 저장
7. 정답 리턴
[주의사항]
- 이중 for문을 돌게되면, 시간초과가 난다.
ㄴ> 스택(Stack)을 사용하자
[소스공개]
import java.util.*;
class Solution {
public int[] solution(int[] numbers) {
// 변수선언
int size = numbers.length; // 배열 길이
int[] answer = new int[size]; // 정답 배열
int idx = size-1; // 정답 배열의 인덱스
answer[idx--]=-1; // 마지막 인덱스는 -1 넣고 시작(비교할 대상이 없으므로)
// 스택
Stack<Integer> stack = new Stack<>();
// 뒤에서부터 반복
for(int i=size-2;i>=0;i--){
if(numbers[i+1]>numbers[i]){ // 뒤에값이 현재값보다 크면
stack.push(numbers[i+1]);
answer[idx--] = numbers[i+1];
continue;
}else{
// 큰수찾기 플래그
boolean isBig = false;
while(!stack.isEmpty()){
int now = stack.peek();
if(now>numbers[i]){ // 스택에 저장된 값이 현재값보다 크면
isBig = true; // 큰수 찾음
answer[idx--] = now;
break;
}else{
stack.pop(); // 스택에서 꺼내기
}
}
// 큰수 못찾으면
if(!isBig){
answer[idx--] = -1;
}
}
}
return answer;
}
}
[실행결과]
