[백준] 1181번 단어정렬

1181 단어정렬

문제

---

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

1. 길이가 짧은 것부터

2. 길이가 같으면 사전 순으로

입력

---

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

출력

---

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

---

풀이)

sort를 하면 되는 문제였다.

1. 길이가 짧은 순으로 

2. 길이가 같다면 사전순으로

((string으로 입력을 받아서 vector에 넣는 방식을 기본적으로 사용했다.))

2개의 풀이법으로 풀어봤는데

첫번째는 vector인자를 pair<int, string>으로 두고

문자 입력 받을때마다, <문자열의 길이, 문자열>로 vector에 넣는 방식이다.

그리고 algorithm헤더의 sort함수로 정렬했다.

sort함수는 첫번째 인자로 정렬한뒤, 두번째 인자로 정렬하니깐 자동적으로 

문자열이 짧은 것은 앞으로 같은 길이의 문자열은 사전순으로 정렬해줬다.

코드)

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
 
int main() {
    int n;
    scanf("%d", &n);
    vector <pair<int,string>> vec;
    for (int i = 0; i < n; i++) {
        string temp;
        cin >> temp;
        vec.push_back({ temp.size(), temp });
    }
    sort(vec.begin(), vec.end());
    for (int i = 0; i < n; i++) {
        if (i > 0 && vec[i].second == vec[i - 1].second) continue;
        cout << vec[i].second << endl;
    }
 
    return 0;
}

결과)

두번째는 vector 인자를 string으로만 두고

sort함수의 비교함수를 직접 만들어서 지정한 방식이다.

시간면에서는 차이가 없었지만 vector에 들어가는 인자가 하나 줄다보니 메모리는 약간 효율성이 좋아졌다.

코드)

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
 
bool cmp(const string &a, const string &b) {
    //길이가 다를때
    if (a.length() < b.length()) {
        return true;
    }
    else if (a.length() > b.length()) {
        return false;
    }
    //길이가 같다면 사전순으로
    else
        return a < b;
}
 
int main() {
    int n;
    scanf("%d", &n);
    vector <string> vec;
    for (int i = 0; i < n; i++) {
        string temp;
        cin >> temp;
        vec.push_back(temp);
    }
    sort(vec.begin(), vec.end(),cmp);
    for (int i = 0; i < n; i++) {
        if (i > 0 && vec[i] == vec[i - 1]) continue;
        cout << vec[i] << endl;
    }
 
    return 0;
}

결과)

+시간을 더 줄일 수 없을까하여 다른 분들의 채점결과를 보니

출력시에 이렇게 구현하거나

temp = "";
for (int i = 0; i < n; i++) {
    if (temp != vec[i]) {
        cout << vec[i] << endl;
        temp = vec[i];
    } 
}

혹은 메인문에 편법으로, c++입출력 개체를 가속화하는 방법을 사용한다.

cin.sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);