[BOJ] #1181 - 단어 정렬

👻 단어 정렬

👉🏻 문제 보러가기 👈🏻

---

🌱 문제

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

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

• 시간 제한 : 2초
• 메모리 제한 : 256 MB

---

🌱 입력

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

---

🌱 출력

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

---

🌱 예제

---

🪐 입출력 1

• 입력

  13
  but
  i
  wont
  hesitate
  no
  more
  no
  more
  it
  cannot
  wait
  im
  yours
  

• 출력

  i
  im
  it
  no
  but
  more
  wait
  wont
  yours
  cannot
  hesitate
  

---

👻 풀이

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> v;
vector<string>::iterator it;
bool cmp(string a, string b)
{
    if (a.size() == b.size()) return a < b;
    return a.size() < b.size();
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 단어 정렬
    string s;
    cin >> s;
    int n = stoi(s);
    while (n--)
    {
        cin >> s;
        it = find(v.begin(), v.end(), s);
        if (it != v.end()) continue;
        v.push_back(s);
    }
    sort(v.begin(), v.end(), cmp);
    for (const string &cs : v) cout << cs << '\n';
    return 0;
}

• 시간 : 1220 ms
• 메모리 : 4648 KB

---

👻 글을 마치며

머릿속으로 알고리즘 정리는 확실히 잘 되는 것 같다. 문제는 효율성인데 다른 코드와 크게 다른 부분은 없는 것 같은데 왜 차이가 나는 지 모르겠다. 😂 당장 고칠 수 있는 부분 먼저 고치도록 노력해봐야겠다.

---

소스코드 보러가기