20240119_뒤에 있는 큰 수 찾기(프로그래머스)

오늘의 TIL은 프로그래머스의 문제 중의 '뒤에 있는 큰 수 찾기'라는 문제의 내용이다.

 

문제 링크

 

https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

 

문제의 내용은 심플한데,

 

int 배열 numbers가 주어지는데,

배열의 각 원소들에 대해 자신보다 뒤에 있는 숫자들 중에서

자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 할 때,

모든 원소에 대한 뒷 큰수를 차례로 담은 배열을 return 하는 문제이다.

(단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다)

 

제한사항

4 <= numbers의 길이 <= 1,000,000

1 <= numbers[i] <= 1,000,000

 

for 문 사용

문제 자체는 난이도가 어렵지 않게 풀 수 있는데, for 문을 사용해도 문제 자체는 해결할 수 있기 때문이다.

 

for 문을 사용하는 해답은 아래와 같다.

int[] answer = new int[numbers.Length];

for (int i = 0; i < numbers.Length; i++)
{
    for (int j = i; j < numbers.Length; j++)
    {
        if (numbers[j] > numbers[i])
        {
            answer[i] = numbers[j];
            break;
        }
        else
        {
            answer[i] = -1;
        }
    }
}

 

지금의 수를 i로, 지금의 뒷 수를 j로 지정하여 이중 for문을 만들어서 만약 numbers[j]가 numbers[i]보다 크다면

answer[i] = numbers[j]로 한 후에 바로 break를 하고

j값을 끝까지 탐색했지만 큰 수가 없다면 answer[i] = -1로 리턴하게 만들었다.

 

이는 탐색하는 영역의 범위가 작다면 문제 없이 돌아가지만,

제한 사항이 numbers의 길이가 100만까지이므로 시간 초과가 되므로 해결은 할 수 있지만, 정답은 아니다.

 

또, 걸린 시간과 메모리가 15번 이후에는 130ms 이상, 92MB 이상이 필요한 것을 볼 수 있다.

 

 

Stack 사용

따라서 이를 해결하기 위해서 Stack을 사용하기로 했는데

(Stack은 선입후출로 이 경우와 같이 데이터를 탐색하며 원하는 데이터가 나오는 경우에 바로 꺼낼 수 있다)

 

사용한 식은 아래와 같다.

 

int[] answer = new int[numbers.Length];

Stack<int> stack = new Stack<int>();

for (int i = 0; i < numbers.Length; i++)
{
    while (stack.Count > 0 && numbers[stack.Peek()] < numbers[i])
    {
        answer[stack.Pop()] = numbers[i];
    }
    stack.Push(i);
}

while (stack.Count > 0)
{
    answer[stack.Pop()] = -1;
}

 

int[] answer 를 numbers.Length로 선언해주고, Stack도 초기화 한다.

이후에 배열을 순회하면서, 현재 원소가 스택의 맨 위에 있는 원소보다 큰 경우에 스택의 원소에 대한 뒷 큰수가 현재 원소가 된다. 이 경우에 스택에서 원소를 꺼내고 해당 인덱스를 현재 원소에 할당해준다.

배열의 순회가 끝난 후에 스택에 남아있는 모든 원소들은 뒷 큰수가 없으므로, 해당 인덱스에는 -1을 할당해준다.

라는 생각으로 만든 식이다.

 

 

오늘은 알고리즘 문제를 풀면서 for문의 비효율성(N^2)인 경우에 이를 효율적으로 해결하기 위한 방법으로

Stack을 사용할 수 있는 것(효율성 N)을 느끼고 실제로 코드를 짜는 과정을 거쳤는데,

 

Queue와 Stack은 이론적으로 공부만하고 실제로 알고리즘 문제를 푸는데는 사용하지 않았기에

처음에 코드를 작성하면서 어려움이 있었다.

 

오늘 느낀 점은 Stack과 Queue를 사용하는 알고리즘 문제를 좀 더 많이 풀어서

이 두가지 방법을 좀 더 잘 사용할 수 있게 준비해야될 것으로 느꼈다.