https://www.acmicpc.net/problem/17298
17298번: 오큰수
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
www.acmicpc.net
# 문제 분석
>> 자신 오른쪽의 원소에서 가장 처음 큰 수인 오큰수를 구한다.
>> 스택을 사용하라고 하는데 어떻게 하는 지 잘 모르겠다.
#include <stdio.h>
#include <vector>
using namespace std;
int main()
{
int n;
scanf_s("%d", &n);
int num;
vector<int> data;
for (int i = 0; i < n; ++i)
{
scanf_s("%d", &num);
data.push_back(num);
}
vector<int> result;
result.push_back(-1);
int pre = -1;
num = -1;
while (!data.empty())
{
num = data.back();
data.pop_back();
if (pre > num)
{
result.push_back(pre);
}
else
{
for (auto iter = result.rbegin(); iter != result.rend(); ++iter)
{
if (*iter == -1)
{
result.push_back(-1);
break;
}
else if (*iter > num)
{
result.push_back(*iter);
break;
}
}
}
pre = num;
}
for (auto iter = result.rbegin(); iter!=--result.rend(); ++iter)
{
printf("%d ", *iter);
}
return 0;
}
# 문제 풀이 과정
>> 다음과 같은 알고리즘을 생각해봤다.
[1번 알고리즘]
3 5 2 7 _ _ _ _ | 해당 수: -
3 5 2 _ _ _ _ | 해당 수: 7 >> -1
3 5 7 _ _ _ | 해당 수: 2 >> 7 -1
3 2 7 _ _ | 해당 수: 5(1)
3 2 7 _ _ _ | 해당 수: 5(2) >> 7 7 -1
5 2 7 _ | 해당 수: 3 >> 5 7 7 -1
1. 데이터를 스택에 저장한다.
2. 데이터를 다 받았으면, 결과 값을 저장할 vecter를 구성한다.
2-1. 받은 데이터의 back()이 결과 값을 저장할 번수의 수이다.
2-2. 데이터를 pop해서 임시 저장한 vector와 값을 비교한다.
2-2-1. 임시 저장 백터가 비어있다면 result에 -1을 push한다.
2-2-2. 임시 저장 백터의 back이 해당 값보다 크면 그 값을 result에 push한다.
2-2-3. 임시 저장 백터의 back이 해당 값보다 작으면 그 값을 원래 임시 스택으로 다시 push 한다.
>> 다시 비교한다.
2-2-4. 비교가 끝났다면 임시 스택이 빌 때까지 vector에 push하고 마지막으로 자기 자신을 push한다.
!오류!
> 내림차순으로 데이터가 들어올 경우 O(n^2)의 시간이 걸려 효율적이지 못하다!!
[2번 알고리즘]
*위와 유사하다.
=> 다만 스택을 push와 pop하며 비교하는 것이 아닌, 임의 접근을 통해 값을 비교한다
!오류!
>> 방법이 다를 뿐 결론적으로 O(n^2)의 시간복잡도를 해결하지 못했다. (다만 공간복잡도는 줄인듯 하다...!!)
[3번 알고리즘]
3 5 2 7 | 해당 수: -
3 5 2 pre(-)| 해당 수: 7 >> -1
3 5 pre(7)| 해당 수: 2 >> 7 -1
3 pre(2)| 해당 수: 5 >> 7 7 -1
pre(5)| 해당 수: 3 >> 5 7 7 -1
1. 데이터를 스택에 저장한다.
2. 데이터를 다 받았으면, 결과 값을 저장할 vector를 구성한다.
2-1. data의 back이 해당 수가 된다.
2-2. 해당 수와 pre, result 배열을 참고한다.
2-2-1. 만약 해당 수보다 pre가 더 크다면, result에 pre를 push 한다.
2-2-2. 만약 해당 수보다 pre보다 더 크지 않고, result의 back이 더 크다면 result에 result의 back을 다시 push한다.
2-2-3. 만약 위 모든 조건에 해당하지 않으면, result를 둘러보며 자신보다 큰 수를 찾는다.
2-2-4. -1을 만나면 -1을 result에 push 한다.
>> 기대 효과: O(n)까지는 아니나 더 효율적으로 구성해봤다!
# 문제 풀이 후기
>> 마의 38% 구간을 넘었을 때 쾌감이 짜릿했다 흐흐...
>> 교수님께서 항상 알고리즘을 먼저 생각하고 코드를 짜라고 하셨는데 이제야 그것이 어떤 의미인지 잘 이해할 수 있었다.
>> 다만 앞으로는 데이터의 범위를 생각해, 미리 처음부터 최대한 효율적인 알고리즘을 만들 수 있도록 노력해야겠다.
>> 나는 풀이에 300ms가 넘는 시간이 걸렸는데, 찾아보는 200ms 언저리에서 푼 사람들이 많다는 것을 알 수 있었다.
빨리 성장해서 나도 그런 사람이 되야겠다.