[백준 1181] 단어 정렬

단어 정렬

문제설명

단어의 수를 입력받고 정렬한다.
조건1) 길이가 짧은 것 부터
조건2) 길이가 같으면 사전순으로
조건에 따라 정렬하고 중복 된 단어는 한 번만 출력한다.

---

알고리즘

1. 단어의 수를 입력 받고, 단어도 입력 받는다.
2. 벡터에 단어와 단어 길이 또한 같이 저장한다.
3. cmp함수로 정렬한다.
4. unique를 활용하여 중복되는 단어는 지운다.
5. 벡터를 출력한다.

---

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
bool cmp(const pair <string,int>&a, const pair <string,int> &b)
{
    if (a.second == b.second)//단어의 글자 수가 같으면 
        return a.first < b.first;//사전순 
    return a.second < b.second;//그렇지 않은 경우 길이가 짧은 순서대로 
}
int main(void)
{
    int N;
    cin >> N;
    vector <pair<string,int>> v;
    while (N)//값 입력 받기
    {
        string s;
        cin >> s;
        v.push_back({ s,s.length() });//단어와 단어 길이 넣기 
        N--;
    }

    sort(v.begin(), v.end(),cmp);//단어정렬 
    v.erase(unique(v.begin(), v.end()),v.end());//중복값 찾기 및 제거

    for (int i = 0; i < v.size(); i++)//결과 출력
        cout << v[i].first<< "\n";

    return 0;
}

개념

bool cmp(const pair <string,int>&a, const pair <string,int> &b)
{
    if (a.second == b.second)//단어의 글자 수가 같으면 
        return a.first < b.first;//사전순 
    return a.second < b.second;//그렇지 않은 경우 길이가 짧은 순서대로 
}

sort(v.begin(), v.end(),cmp);//단어정렬 
v.erase(unique(v.begin(), v.end()),v.end());//중복값 찾기 및 제거 

cmp함수를 다음과 같이 만들어서 정렬한다.
그리고 unique를 사용하면 중복되는 부분이 벡터의 맨 뒤로 이동한다.
이때 unique는 중복되는 부분이 시작되는 부분을 반환해준다-> iterator로 받아도 된다.
erase를 활용하여 중복되는 부분을 제거한다.

고찰

이번 문제는 단순 정렬이지만 cmp함수 작성 방법과 vector를 까먹으면 복잡해질 수 있는 문제였다.
벡터 활용 관련 함수를 이용하면 쉽게 풀 수 있다.