BOJ 1181 - 단어 정렬 문제풀이
문제를 읽고 이해하기
알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.
- 길이가 짧은 것부터
- 길이가 같으면 사전 순으로
첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.
조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.
재정의와 추상화
정렬 문제
문제에서 요구한 조건 2개를 순서대로 정렬해야 한다. 즉, 정렬 알고리즘은 아래와 같이 구현한다.
- 길이가 같다면, 사전순으로 정렬한다.
- 길이가 다르다면 길이를 기준으로 오름차순으로 정렬한다.
bool comp(string a, string b) {
if (a.length() == b.length())
return a < b;
return a.length() < b.length();
}
그리고 나서 출력할 때 여러 번 입력된 경우에는 한 번씩만 출력하라고 하였으니, 중복을 제거하라는 의미이다.
따라서 C++ STL에서 제공하는 unique 함수를 이용한다.
unique 함수는 특성상, 첫 번째 중복된 문자 이터레이터를 반환한다. 따라서 벡터객체.begin()부터 unique 함수에서 반환된 이터레이터 앞까지만 출력해주면 된다.
C++ STL unique()에 대해서 알아보기
코드 작성
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool comp(string a, string b) {
if (a.length() == b.length())
return a < b;
return a.length() < b.length();
}
int main() {
vector<string> v;
int n;
cin >> n;
while (n--) {
string temp;
cin >> temp;
v.push_back(temp);
}
sort(v.begin(), v.end(), comp);
auto end_itr = unique(v.begin(), v.end());
for (auto itr = v.begin(); itr != end_itr; itr++)
cout << *itr << '\n';
return 0;
}
'알고리즘 > 문제풀이' 카테고리의 다른 글
BOJ 1927 - 최소 힙 문제풀이 (0) | 2020.03.25 |
---|---|
BOJ 1427 - 소트인사이드 문제풀이 (0) | 2020.03.25 |
BOJ 1026 - 보물 문제풀이 (0) | 2020.03.25 |
BOJ 11286 - 절댓값 힙 문제풀이 (0) | 2020.03.19 |
BOJ 1010 - 다리 놓기 문제풀이 (0) | 2020.03.19 |
댓글
이 글 공유하기
다른 글
-
BOJ 1927 - 최소 힙 문제풀이
BOJ 1927 - 최소 힙 문제풀이
2020.03.25 -
BOJ 1427 - 소트인사이드 문제풀이
BOJ 1427 - 소트인사이드 문제풀이
2020.03.25 -
BOJ 1026 - 보물 문제풀이
BOJ 1026 - 보물 문제풀이
2020.03.25 -
BOJ 11286 - 절댓값 힙 문제풀이
BOJ 11286 - 절댓값 힙 문제풀이
2020.03.19