17299번: 오등큰수
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
www.acmicpc.net
boj 17298 오큰수
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 스..
emoney96.tistory.com
위의 문제와 같은 문제입니다.
오큰수는 오른쪽에 있는 자신보다 큰 수 중에 가장 왼쪽에 있는 수를 출력하는 문제이고,
이 문제는 오른쪽에 있는 자신보다 등장횟수가 많은 수 중에 가장 왼쪽에 있는 수를 출력하는 문제입니다.
자신보다 큰 수 -> 자신보다 등장횟수가 많은 수 의 차이이며 풀이는 같습니다.
이 문제 역시 수열을 역순으로 탐색하였고,
list[i]를 스택에 넣기 전에 자신보다 등장횟수가 적은 값들을 모두 pop해줍니다.
스택이 비어있으면 -1, 아니면 top을 출력해주시면 됩니다.
[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
36
37
38
39
40
41
42
43
44
45
|
#include <iostream>
#include <stack>
using namespace std;
stack<int> s;
int list[1000001], num[1000001], ans[1000001];
int N;
void print() {
for (int i = 1; i <= N; i++) {
cout << ans[i] << ' ';
}
cout << '\n';
}
void func() {
for (int i = N; i > 0; i--) {
while (!s.empty() && num[list[i]] >= num[s.top()]) s.pop();
if (s.empty()) ans[i] = -1;
else ans[i] = s.top();
s.push(list[i]);
}
}
void input() {
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> list[i];
num[list[i]]++;
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
print();
return 0;
}
|
cs |
[Java]
|
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static Stack<Integer> s = new Stack<>();
static int list[], num[], ans[];
static int N;
static void print() {
StringBuffer sb = new StringBuffer();
for (int i = 1; i <= N; i++)
sb.append(ans[i]).append(" ");
System.out.println(sb.toString());
}
static void func() {
for (int i = N; i > 0; i--) {
while (!s.isEmpty() && num[list[i]] >= num[s.peek()])
s.pop();
if (s.isEmpty())
ans[i] = -1;
else
ans[i] = s.peek();
s.push(list[i]);
}
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
list = new int[N + 1];
num = new int[1000001];
ans = new int[1000001];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
list[i] = Integer.parseInt(st.nextToken());
num[list[i]]++;
}
}
public static void main(String[] args) throws Exception {
input();
func();
print();
}
}
|
cs |
'algorithm > data-structure' 카테고리의 다른 글
| boj 15926 현욱은 괄호왕이야!! (1) | 2023.07.24 |
|---|---|
| boj 21939 문제 추천 시스템 Version 1 (0) | 2022.02.11 |
| boj 9372 상근이의 여행 (0) | 2021.02.09 |
| boj 1158 요세푸스 문제 (0) | 2021.02.09 |
| boj 1918 후위 표기식 (0) | 2021.02.05 |