문제
https://www.acmicpc.net/problem/12933
문제해설
“quack”하고 우는 오리가 있다.
문자열이 주어지고 몇 마리의 오리가 우는지 구하면 된다.
잘못된 문자열이면 -1을 출력한다.
문제풀이
구현문제
n^2으로 그냥 구현해도 시간초과가 나진 않을 것 같지만
n으로 푸려고 노력했다.
우선 -1을 출력하는 조건을 제대로 처리하지 못해서 틀렸다.
예를들어 q보다 a가 먼저오는 것처럼 순서가 뒤바뀌어도 -1이지만
q와 각 문자들의 숫자가 맞지 않아도 -1을 출력해야 한다.
그래서 앞부분에 문자들의 개수를 세어 -1을 판별해주었고
후에 이중벡터를 이용해 몇마리의 오리가 있는지 판단해주었다.
각 벡터에 순서대로 quack를 넣었고 다 차면 다시 비어주었다.
코드가 깔끔하지가 못한게 아쉽다.
전체코드
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
string input; cin >> input;
int len = input.length();
vector<int>arr;
vector<int>num(6, 0);
for (int i = 0; i < len; i++) {
if (input[i] == 'q') {
arr.push_back(1);
num[1]++;
}
else if (input[i] == 'u') {
arr.push_back(2);
num[2]++;
}
else if (input[i] == 'a') {
arr.push_back(3);
num[3]++;
}
else if (input[i] == 'c') {
arr.push_back(4);
num[4]++;
}
else if (input[i] == 'k') {
arr.push_back(5);
num[5]++;
}
}
if (num[1] != num[2] || num[1] != num[3] || num[1] != num[4] || num[1] != num[5]) {
cout << -1;
return 0;
}
vector<vector<int>>duck;
vector<int>cnt;
for (int i = 0; i < len; i++) {
int now = arr[i];
bool flag = false;
if (now == 1) {
for (int k = 0; k < duck.size(); k++) {
if (duck[k].empty()) {
duck[k].push_back(1);
flag = true;
break;
}
}
if (flag) continue;
vector<int>s;
s.push_back(1);
duck.push_back(s);
cnt.push_back(0);
continue;
}
bool err = true;
for (int j = 0; j < duck.size(); j++) {
if (duck[j].empty()) continue;
if (duck[j].back() == now - 1) {
duck[j].push_back(now);
err = false;
if (duck[j].size() == 5) {
duck[j].clear();
cnt[j]++;
}
break;
}
}
if (err) {
cout << -1;
return 0;
}
}
int res = 0;
for (int i = 0; i < cnt.size(); i++) {
if (cnt[i] > 0)
res++;
}
if (res == 0)
cout << -1;
else
cout << res;
return 0;
}