문제링크
https://www.acmicpc.net/problem/1181
문제
알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.
- 길이가 짧은 것부터
- 길이가 같으면 사전 순으로입력
입력
첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.
출력
조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.
해석
입력받은 단어의 길이별로 벡터에 저장한다.
벡터가 비어있지 않다면 정렬 후 출력
코드
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 <string>
#include <vector>
#include <algorithm>
#define MAX 200001
using namespace std;
vector<string> v[MAX];
int main() {
int N;
string val;
cin >> N;
for (int i = 0; i < N; i++) {
// 중복된 것이 있는지 판단하기 위한 변수
bool possible = true;
cin >> val;
// 중복된 것이 있다면 넣지 못함
for (int j = 0; j < v[val.length()].size(); j++) {
if (val == v[val.length()][j]) {
possible = false;
}
}
if (possible == true) {
v[val.length()].push_back(val);
}
}
//하나라도 들어가있다면 정렬
for (int i = 0; i < MAX; i++) {
if (v[i].size() != 0) {
sort(v[i].begin(), v[i].end());
}
}
// 출력
for (int i = 0; i < MAX; i++) {
if (v[i].size() != 0) {
for (int j = 0; j < v[i].size(); j++) {
cout << v[i][j] << endl;
}
}
}
}
|
cs |
Memo
보자마자 생각난 방법이 길이별로 벡터에 저장하고 sort하는 방법이었다. 시간 복잡도를 만족 못할 것 같았는데 돌려보니까 통과가 되었다. 다른 방법을 생각해보고 좀 더 효율적인 코드를 작성해봐야겠다.