프로그래머스 - 뒤에 있는 큰 수 찾기 <9점> - 자바 java Stack

크고 가까운놈 나와ㅋ

문제가 level 2치고는 간단해 보였다.

구현 문제자나~~ 시간 복잡도만 고려하면 되겠다 싶었다.

 

일단 문제 그대로 읽으면서 구현해봤다.

뒤에 큰수를 찾으면 max에 저장해두고, 해당값을 answer[i]에 넣는다.

max가 본인이 되는 경우를 제외하면 그 사잇값은 max가 뒷큰수가 된다.

찾지 못한경우 boolean으로 구분해 -1을 넣어주었다.

 

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        
        for (int i = 0; i < numbers.length; i++) {
            int max = -1;
            boolean find = false;
            
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] < numbers[j]) {
                    find = true; // 큰 수 발견
                    max = numbers[j]; // 큰 수 저장
                    break;
                }
            }
            
            if (find) {
                answer[i] = max;
            } else {
                answer[i] = -1;
            }
        }
        return answer;
    }
}
 

 

하지만 입력값이 1,000,000 까지기에 n^2은 무리였나보다.

나머지는 맞았으나, tc 20~23번에서 시간 초과가 발생했다.

 

하지만 다른 방법은 안떠오르고,, 어떻게 최적화 할까 하다가

앞부터 찾으니 큰 수를 하나하나 다 찾아야하는게 오래걸린다 싶었다.

뒤에서 부터 탐색하며, 뒤에 숫자의 뒷큰수에 따라 앞이 정해지면 보다 빠르게 연산이 가능하다 판단해서 로직을 수정했다.

 

 

import java.util.Arrays;
 
public class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Arrays.fill(answer, -1);
        
        for (int i = numbers.length - 2; i >= 0; i--) { // 뒤에서부터 탐색
            for (int j = i + 1; j < numbers.length; j++) { 
                if (numbers[i] < numbers[j]) { // 뒤에 수가 크다면
                    answer[i] = numbers[j];    // answer 에 넣기.
                    break;
                } else if (numbers[i] >= numbers[j]) { // 만약 크지 않고
                    if (answer[j] == -1) {             // 뒤에 수도 뒷큰수가 없다면
                        answer[i] = -1;                // i도 없는것
                        break;
                    } else if (numbers[i] < answer[j]) { // i번째가 j의 뒷큰수보다 작다면
                        answer[i] = answer[j];           // i의 뒷큰수도 j와 동일
                        break;
                    }
                }
            }
        }
        return answer;
    }
}
 

다행이게도 모두 시간내에 연산되었다. 물론 이 문제여서 가능했지만

 

다른사람들은 어떻게 구현했다 찾아보니 Stack을 많이들 사용하셨었다.

뭐를 보고 스택을 사용하였나 했더니 큰수고, 가장 가까운이 키워드였다.

결국 스택에 넣고, 상단이 다음 수보다 작다면 다음수가 스택 상단의 뒷큰수가 되는 것이었다.

 

 

아 맞네

 

import java.util.ArrayDeque;
import java.util.Deque;
 
public class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Deque<Integer> stack = new ArrayDeque<>();
     
        for (int i = 0; i < numbers.length; i++) {
            // 스택이 비어있지 않고, 스택의 맨 위에 있는 요소가 현재 요소보다 작은 경우 >> 다음으로 큰 수
            // ex) 스택에 2가 들어있고 3이 들어온다면 2 < 3 이므로 3이 뒷큰수가 됨.
            while (!stack.isEmpty() && numbers[stack.peek()] < numbers[i]) {
                int index = stack.pop(); // 다음으로 큰 수의 인덱스를 가져옴
                answer[index] = numbers[i]; // 해당 인덱스의 answer 값을 다음으로 큰 수로 업데이트합니다.
            }
            stack.push(i); // 다음 값의 인덱스를 스택에 넣어서 비교를 진행합니다.
        }
 
        // 남은 요소들은 뒤에 큰 수가 없으므로 -1로 채웁니다.
        while (!stack.isEmpty()) {
            int index = stack.pop();
            answer[index] = -1;
        }
 
        return answer;
    }
}
 

 

스택으로 구현해보았다. 인덱스를 넣고~ 비교하고, 스택이 비어있지 않고, 다음수가 peek()보다 크면? 고놈이 뒷큰수여!

남아있는 친구들은 아쉽게도 큰 형님을 못만나 솔로가 되는.. ( -1)

 

자료구조는 기본으로 다 공부하고, 사용해보고 예제들을 많이 다뤄야겠다.

 

코드 별 경과 시간

		스택 사용
이중 for문 사용	로직을 수정한 코드	stack 사용

 

\알고리즘 4개월 했나..? 1500이 오는군용

 

요즘 뭔가 공부가 더뎌진거 같은데 더워서 하기가 싫다 후후.

운동도 하기싫어 ~

 

잔디는 그래도 키워봅시다