📌문제접근
문제 : 백준 1181 : 단어정렬
알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.
길이가 짧은 것부터
길이가 같으면 사전 순으로
단, 중복된 단어는 하나만 남기고 제거해야 한다.
- 중복 제거
- 길이 순 정렬
- 사전순 정렬 (같은 길이일 때)
📌제출코드
#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;
int main() {
int n;
string str;
map<string, int> strMap;
map<int, vector<string>> intStrMV;
cin >> n;
for (int i = 0; i < n ; i++) {
cin >> str;
strMap.insert({str, str.length()});
}
for (auto s : strMap) {
intStrMV[s.second].push_back(s.first);
}
for (auto& im : intStrMV) {
for(auto& strv : im.second) {
cout << strv << endl;
}
}
return 0;
}📌문제 해결
-
중복제거
C++에서map과set은 중복된 key를 자동으로 제거하고, key값을 오름차순으로 정렬하는 특성을 가지고 있다. 이러한 특성을 활용하면 문제가 요구하는 두가지 조건을 자연스럽게 만족할 수 있다,
(1) 중복된 단어는 하나만 남긴다.
(2) 길이가 같으면 사전순으로 정렬한다.
또한, 기본 조건인 길이가 짧은 순으로 정렬을 처리하기 위해, 사용자의 입력을 받을 때 각 문자열의 길이 정보를 함께 저장할 수 있는map<string, int>를 사용하였다.
set을 통해 문자열만 저장하고 나중에.length()를 길이를 계산할 수도 있지만 이후 과정을 고려하여 문자열과 길이를 함께 저장할 수 있는map을 선택하였다. -
길이순 + 사전순 정렬
map<string, int>에서 이미 사전순으로 자동 정렬되고 value에는 문자열 길이가 저장되어 있으므로, 이를 기반으로 다시 문자열 길이를 기준으로 정렬하면 문제의 조건을 모두 충족할 수 있다.
이를 위해map<int,vector<string>>형태를 사용하여, 문자열 길이(int)를 key로 하고 해당 길이에 속하는 문자열들을 vector로 체이닝하여 저장하였다. 이 구조에서map의 특성에 따라 길이는 자동으로 오름차순 정렬되며, 각vector<string>안에는 이미 사전순으로 정렬된 문자열들이 있게 된다. 이를 이중for문으로 순회하면 문제의 모든 요구조건을 만족한 출력이 가능하다.
📌오늘의 회고
자료구조의 기본 특성을 알고 있어야 문제 해결 방향을 잡기 쉽다.
