[Programmers / Level2] 154539. 뒤에 있는 큰 수 찾기(Java)

💡 Info

• 난이도: Lv2
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/154539
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/2/154539. 뒤에 있는 큰 수 찾기

입출력 조건

입출력 예시

문제 이해

• 자신보다 뒤에 있는 숫자 중, 자신보다 크면서 가장 가까이 있는 수를 차례로 배열에 담아서 반환하면 되는 문제

알고리즘

풀이 시간 : 35분

• 인덱스 선언
• 인덱스가 모든 numbers 배열을 순회할 동안
  • numbers[index] < numbers[i]일 경우 -> numbers[i]를 정답 배열에 저장
  • 더 큰 값을 찾지 못한 경우 -> -1 반환

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        int index = 0;
        while(index < numbers.length) {
            for(int i=index; i<numbers.length; i++) {
                if(numbers[index] < numbers[i]) {
                    answer[index] = numbers[i];
                    break;
                }
            }
            if(answer[index] == 0) {
                answer[index] = -1;
            }
            index++;
        }
        return answer;
    }
}

오답체크

• 테스트 일부 미통과 문제
  
  • stack을 사용해 문제를 풀어야 복잡도에 걸리지 않음!

//before

while(index < numbers.length) {
	for(int i=index; i<numbers.length; i++) {
		if(numbers[index] < numbers[i]) {
			answer[index] = numbers[i];
			break;
		}
	}
    if(answer[index] == 0) {
		answer[index] = -1;
	}
	index++;
}

//after

// 스택 사용
Stack<Integer> stack = new Stack<>();
        
//1번째
stack.push(0);
for(int i=1; i<numbers.length; i++) {
	while(!stack.empty() && numbers[stack.peek()] < numbers[i]) {
		answer[stack.pop()] = numbers[i];
	}
	//다음 인덱스로 이동
	stack.push(i);
}
        
// stack에 남은 인덱스 값들 = -1
while(!stack.empty()) {
	answer[stack.pop()] = -1;
}

최종 풀이

풀이 시간 : 1시간 10분(첫 풀이 시간 포함)

• 인덱스 선언
• 인덱스가 모든 numbers 배열을 순회할 동안
  • 스택이 비어있지 않고 + numbers[stack.peek()] < numbers[i]인 경우 -> numbers[i]를 정답 배열에 저장
  • while문 순회 후 다음 인덱스 값 넣기(push)
  • 더 큰 값을 찾지 못한 경우(while문으로) -> -1 반환

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        // 스택 사용
        Stack<Integer> stack = new Stack<>();
        
        //1번째
        stack.push(0);
        for(int i=1; i<numbers.length; i++) {
            while(!stack.empty() && numbers[stack.peek()] < numbers[i]) {
                answer[stack.pop()] = numbers[i];
            }
            //다음 인덱스로 이동
            stack.push(i);
        }
        
        // stack에 남은 인덱스 값들 = -1
        while(!stack.empty()) {
            answer[stack.pop()] = -1;
        }
        return answer;
    }
}

결과

🚨 참고할 풀이

• Arrays.fill을 활용해 초기값을 세팅하는 코드 추가
• 출처 : [프로그래머스[] - 뒤에 있는 큰 수 찾기(LV2) java

import java.util.*;


class Solution {
    public int[] solution(int[] numbers) {
        Stack<Integer> stack = new Stack<>();
        int[] answer = new int[numbers.length];

        Arrays.fill(answer, -1); // 초기값을 -1로 세팅

        for (int i = 0; i < numbers.length; i++) {
            // 스택에 들어있는건 index이다.
            // 스택에 들어있는 애들은 아직 자기보다 큰 수를 찾지 못해서 안에 들어있다고 생각하면 된다.
            // 현재 number[i] 의 값이 numbers[stack.peek()] 값보다 크다면
            // answer값을 현재 numbers[i] 로 채워주면 된다.
            while (!stack.isEmpty() && numbers[stack.peek()] < numbers[i]) {
                answer[stack.pop()] = numbers[i];
            }
            stack.push(i);
        }
        return answer;
    }
}