728x90
반응형
https://school.programmers.co.kr/learn/courses/30/lessons/154539
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
입력으로 주어지는 배열의 길이가 1,000,000이기 때문에, 단순 계산으로는 20~23번 테스트케이스에서 시간 초과가 난다.
문제에서 뒤에있는 숫자 중, 자신보다 크면서 가장 가까이에 있는 수를 찾아야 한다.
뒷 큰수를 구하지 못한 수들을 저장하는 배열을 선언한다.
예를 들어, 뒷 큰 수를 구하지 못한 수가 {9, 5, 3}으로 있다고 하자.
뒷 큰수를 구하지 못한 수들은 모두 내림차순으로 배열에 저장된다.
(뒷 큰수를 구하지 못했다는 것은 아직 이 수들보다 큰 수가 들어오지 않았기 때문)
만약, 다음 수가 7이 들어온다고 하자.
그러면, 뒷 큰 수를 구하지 못한 수 배열에서 가장 먼저 3과 비교하여 3보다 큰지 확인한다.
3<7이니, 3의 뒷 큰 수는 7이 된다.
5<7이니, 5의 뒷 큰 수는 7이 된다.
9>7이니, 5는 뒷 큰수를 구하지 못한 수 배열에 들어가게 된다. {9, 7}
이 과정을 반복하게 되면, 마지막에 뒷 큰 수를 구하지 못한 내림차순 배열만이 남게 된다.
이들은 하나씩 꺼내며 뒷 큰수를 -1로 할당한다.
이 알고리즘은 Stack 자료구조를 활용하여 후입선출을 통해 구하면 비교적 간단하게 구현할 수 있다.
#include <string>
#include <vector>
#include <stack>
using namespace std;
vector<int> solution(vector<int> numbers) {
vector<int> answer;
stack<pair<int, int>> s;
answer.resize(numbers.size());
for (int i = 0; i < numbers.size(); ++i)
{
// 뒷 큰수를 구하지 못한 수의 배열
int Size = s.size();
while (Size--)
{
// 뒷 큰수를 발견했는가?
bool Check = false;
// 마지막에 배열에 들어온 수부터 비교 (후입선출)
if (s.top().first < numbers[i])
{
answer[s.top().second] = numbers[i];
s.pop();
Check = true;
}
// 뒷 큰수를 발견하지 못했으면 넘어간다.
if (!Check) break;
}
s.push({ numbers[i], i });
}
while (!s.empty())
{
answer[s.top().second] = -1;
s.pop();
}
return answer;
}
728x90
반응형
'📕알고리즘 문제 > 📝Programmers' 카테고리의 다른 글
[프로그래머스] Level 3 : 기지국 설치 (0) | 2024.11.26 |
---|---|
[프로그래머스] Level 2 : 무인도 여행 (0) | 2024.11.25 |
[프로그래머스] Level 2 : 게임 맵 최단 거리 (0) | 2024.11.21 |
[프로그래머스] Level 2 : 프로세스 (0) | 2024.11.20 |
[프로그래머스] Level 3 : 디스크 컨트롤러 (0) | 2024.11.18 |