[백준 BOJ 1181번] 단어 정렬(C / C++ ) [정렬]

1181번: 단어 정렬 (acmicpc.net)

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2초	256MB	53809	21852	16346	40.159%

 

문제

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

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

 

입력

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

 

출력

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

 

예제 입력 1

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

예제 출력 1

i
im
it
no
but
more
wait
wont
yours
cannot
hesitate

 

풀이

 중복 제거 시 여러방법을 써보았지만 자꾸 시간초과가 뜨는 바람에 일단 정렬 후 이전 문자열과 비교를 하여 같을 때는 출력을 하지 않는 방향으로 문제를 풀었습니다.

 우선 vector에 문제열을 집어넣은 후 만약 비교대상이 될 각 문자열의 길이가 같다면 그 문자열은 오름차순,

같지 않다면 문자열 길이의 오름차순으로 정렬되게 배열을 만들었습니다.

출력은 방금 말씀 드린 것처럼 이전 문자열과 현재 문자열이 같으면, 즉 문자열 중복이 생긴다면 출력을 하지 않는 방향으로 출력을 하였습니다.

 

코드

// 단어 정렬
#include<bits/stdc++.h>
using namespace std;
vector<string> str;
bool cmp(string a,string b){return a.size()==b.size()?a<b:a.size()<b.size();}
int main(){
    int n;
    string s,prev;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s;
        str.push_back(s);
    }
    sort(str.begin(),str.end(),cmp);
    for(string s:str){
        if(prev==s)continue;
        cout<<s<<"\n";
        prev=s;
    }
}

1181번: 단어 정렬 (acmicpc.net)

1181번: 단어 정렬