문제 URL : https://www.acmicpc.net/problem/17299
17299번: 오등큰수
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
www.acmicpc.net
문제접근법: 문제 접근법을 생각하느라 꽤 시간이 걸렸던 문제입니다. 결론적으로 스택을 이용하는 문제였고 역으로 접근하면서 스택을 응용하는거였습니다. 스택응용문제가 약하다보니 타 풀이의 참고를 많이했습니다.
소스코드 2가지를 보여드릴게요
C++ 소스코드:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
//By 콩순이냉장고
#include <iostream> #include <string>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
int n;
int F[1000001];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
vector<int> v(n),res(n);
for (int i = 0; i < n; i++){
cin >> v[i];
F[v[i]]++;
}
stack<pair<int, int>> st;
for (int i = n-1; i>=0; i--)
{
while (!st.empty()&&st.top().second<=F[v[i]])//핵심 큰것만 집어넣기위해 현재 나보다 작은수는 다 버림
st.pop();
if (st.empty())
res[i] = -1;
else
res[i] = st.top().first;
st.push({ v[i], F[v[i]] });
}
for (int i = 0; i < n; i++)
cout << res[i] << " ";
cout << "\n";
}
|
cs |
파이썬 소스코드:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
# -*- coding: euc-kr -*-
# By 콩순이냉장고
n=int(input())
list=[int(x) for x in input().split()]
F=[0]*1000001
res=[None]*n
for i in list:
F[i]+=1
st=[]
for i in range(n-1,-1,-1):
while st :
if st[-1][1]<=F[list[i]]:
st.pop()
else :
break
if st:
res[i]=st[-1][0]
else:
res[i]=-1
st.append([list[i],F[list[i]]])
for i in res:
print(i,end=' ')
|
cs |
모르는점 혹은 궁금한점 혹여나 틀린것이 있다면 언제든지 댓글을 이용해주시길 바랍니다.
'백준' 카테고리의 다른 글
| 백준 16946 벽 부수고 이동하기 4 (0) | 2020.08.24 |
|---|---|
| 백준 1202 보석 도둑 (0) | 2020.08.24 |
| 백준 11576 Base Conversion (0) | 2020.08.13 |
| 백준 1927 놀라운 문자열 (0) | 2020.08.13 |
| 백준 1411 비슷한 단어 (0) | 2020.08.10 |