98. 뒤에 있는 큰 수 찾기

 

기본 틀 :

using System;

public class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[] {};
        return answer;
    }
}

 

처음에는 문제를 보고 당연히 2중 반복문을 통해 비교 하는 코드를 작성했다.

using System;

public class Solution {
    public int[] solution(int[] numbers) 
    {
        int[] list = new int[numbers.Length];
        
        int i = 0;
        
        for(; i < list.Length - 1; i++)
        {
            bool check = true;
            for(int j = i; j < list.Length; j++)
            {
                if(numbers[i] < numbers[j])
                {
                    list[i] = numbers[j];
                    check = false;
                    break;
                }
            }
            if(check) list[i] = -1;
        }
        
        list[i] = -1;
        
        return list;
    }
}

 

 

그 결과 시간  초과에 걸리게 됐다...

 

시간 초과에 걸리는 테스트 케이스를 찾아 본 결과

 

numbers = [9, 9, 9,  ... , 9, 9, 9] 로 1,00,000개 있을 경우

 

2중 반복문은 O(n^2)으로 1,000,000,000,000의 시간 복잡도를 가지게 됐다.

 

위의 사례를 해결하기 위해 방법을 모색해봤지만 뾰족한 수가 떠오르지 않았다.

 

결국 다른 이 작성한 JS 코드를 보고 분석해보는 시간을 가지게 됐다.

function solution(numbers) {
    const stack = []
    let result = new Array(numbers.length).fill(-1)
    for(let i = 0; i < numbers.length; i++)
    {
        while(numbers[stack.at(-1)] < numbers[i]) result[stack.pop()] = numbers[i]
        stack.push(i)
    }
    return result;
}

 

이 코드를 C#으로 변경하면 아래와 같은 코드가 작성된다.

using System;
using System.Collections.Generic;

public class Solution {
    public int[] solution(int[] numbers) 
    {
        Stack<int> indexStack = new Stack<int>();
        int[] result = new int[numbers.Length];
        
        for(int i = 0; i < result.Length; i++)
        {
            result[i] = -1;
        }
        
        for(int i = 0; i < numbers.Length; i++)
        {
            
            while(indexStack.Count > 0 && numbers[indexStack.Peek()] < numbers[i])
            {
                result[indexStack.Pop()] = numbers[i];
            }
            indexStack.Push(i);
        }
        
        return result;
    }
}

 

위의 코드는 Stack을 활용해 반복 중인 index를 저장하고 while문을 통해

 

Stack의 가장 최상단 index의 numbsrs 값과 현재 반복 중인 index의 numbers 값을 비교하여

 

현재 반복 중인 index의 값이 클 경우 결과 배열의 값을 바꾸는 방식으로 작성 돼 있었다.

 

위의 코드의 과정을 

 

[9, 1, 5, 3, 6, 2]로 간략하게 표현해보고자 한다.

 

반복문 index : 0

반복 중인 index : 0   while문 조건 indexStack.Count > 0 => 0 > 0 X   indexStack.Push(0); 현재 indexStack 내부 : [0]   현재 result 내부 : [-1, -1, -1, -1, -1, -1];

 

반복 중인 index : 1

while문 조건 numbers[0] < numbers[1] 9 < 1 X   현재 result 내부 : [-1, -1, -1, -1, -1, -1];   indexStack.Push(1); 현재 indexStack 내부 : [0, 1]

 

반복 중인 index : 2

while문 조건 numbers[1] < numbers[2] 1 < 5 O   result 값 변경 result[indexStack.Pop()] = numbers[i] => result[1] = numbers[2] => result[1] = 5   현재 result 내부 : [-1, 5, -1, -1, -1, -1];   indexStack.Push(2); 현재 indexStack 내부 : [0, 2]

 

반복 중인 index : 3

while문 조건 numbers[2] < numbers[3] 5 < 3 X   현재 result 내부 : [-1, 5, -1, -1, -1, -1];   indexStack.Push(3) 현재 indexStack 내부 : [0, 2, 3]

 

반복 중인 index : 4

while문 조건 numbers[3] < numbers[4] 3 < 6 O   result 값 변경 result[3] = numbers[4] => result[3] = 6 현재 result 내부 : [-1, 5, -1, 6, -1, -1];   현재 indexStack 내부 : [0, 2]   while문 조건 numbers[2] < numbers[4] 5 < 6 O result 값 변경 result[2] = numbers[4] => result[2] = 6 현재 result 내부 : [-1, 5, 6, 6, -1, -1];   현재 indexStack 내부 : [0]   while문 조건 numbers[0] < numbers[4] 9 < 6 X 현재 result 내부 : [-1, 5, 6, 6, -1, -1]; indexStack.Push(4); 현재 indexStack 내부 : [0, 4]

 

반복 중인 index : 5

while문 조건 numbers[4] < numbers[5] 6 < -1 X   현재 result 내부 : [-1, 5, 6, 6, -1, -1];   indexStack.Push(5); 현재 indexStack 내부: [0, 5]

 

위의 과정을 통해  [-1, 5, 6, 6, -1, -1] 이라는 원하는 결과를 얻을 수 있었다.

 

아직 사고의 폭을 넓고 정교하게 못 하는 것 같다...