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

문제 바로가기

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

1181번: 단어 정렬

---

관련 알고리즘

- 정렬

---

정답 및 해설

단어의 개수 N을 입력받은 다음, 입력받은 문자열을 1. 길이가 짧은 순, 2. 길이가 같으면 사전 순으로 정렬하는 문제이다.

이때 중복된 단어는 하나만 출력해야 하는데 입력단계에 발견하기 어렵기 때문에 정렬된 상태에서 중복을 체크한다

---

C++

#include<bits/stdc++.h>
using namespace std;

bool cmp(string s1, string s2){
    if(s1.length()==s2.length())
        return s1<s2;
    return s1.length()<s2.length();
}

int main(){
    string str[20000];
    int N,i;
    cin>>N;
    for(i=0; i<N; i++)
        cin>>str[i];
    sort(str, str+N, cmp);
    cout<<str[0]<<'\n';
    for(i=1; i<N; i++){
        if(str[i]==str[i-1]) continue;
        cout<<str[i]<<'\n';
    }
}

 

Line	해설
4~8	이번 문제에서는 문자열의 정렬을 위해 <algorithm> 라이브러리의 sort 함수를 사용할 것이다. sort 함수의 정렬 순서를 정의하기 위해 cmp함수를 정의하였다. 두 문자열 s1과 s2를 인자로 받아 길이가 같다면 사전순으로, 다르다면 긴 것을 뒤로 보내도록 하였다.1)
11~12	풀이에 필요한 변수를 선언한다. string str[20000] : 1≤N≤20000 이므로 문자열 타입 배열을 선언하였다. 문자의 길이가 20000이 아닌 문자열의 개수가 20000개이다.
13~15	문자열의 개수 N을 입력받은 다음, for 문의 변수 i를 통해 str[i] 배열에 저장하였다.
16	sort 함수를 이용하여 입력받은 문자열들을 정렬한다.1) 이때 Line 4~8에서 cmp함수를 정의하였기 때문에 sort(str, str+N, cmp)로 cmp함수를 인자로 넘겨주어야 한다. 해당 함수을 통해 우리가 원하는 1.길이가 짧은 순, 2.길이가 같다면 사전 순으로 정렬된다.
17~21	먼저 str[0]를 출력한다음 for문을 통해 나머지 문자열을 출력하였다. for문의 변수 i를 1~N-1범위 내에서 반복하면서 문자열을 출력한다. 이때 중복된 문자열을 거르기 위해 if 조건문으로 이전 문자열과 현재 문자열이 동일하다면 continue 구문으로 출력을 생략하고 다음 문자열로 이동한다.

1) sort 함수에 대해서는 추후에 자세히 다루기로 한다.