[C++백준 1181:단어 정렬]

문제링크

https://www.acmicpc.net/problem/1181

1181번: 단어 정렬

 

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로입력

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

 

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

 

해석

입력받은 단어의 길이별로 벡터에 저장한다.

벡터가 비어있지 않다면 정렬 후 출력

 

코드

#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;
            }
        }
    }
 
}

 

Memo

보자마자 생각난 방법이 길이별로 벡터에 저장하고 sort하는 방법이었다. 시간 복잡도를 만족 못할 것 같았는데 돌려보니까 통과가 되었다. 다른 방법을 생각해보고 좀 더 효율적인 코드를 작성해봐야겠다.