[알고리즘] 백준 1181번 "단어 정렬" (C/C++) - Don 임베디드

문제요약:

알파벳 소문자로 이루어진 N개의 단어가 주어질 때,

아래 조건으로 정렬하여 출력하는 프로그램을 작성하라.

1. 길이가 짧은 단어부터.

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

 

 

제약:

 

제한 시간 2초, 메모리 256MB

1 <= N <= 20,000

단어의 길이는 50을 넘지 않음.

 

 

입력:

 

첫째 줄에 총 단어 개수 N이 주어진다.

둘째 줄 부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다.

 

 

출력:

 

정렬한 단어들을 출력한다.

단, 같은 단어가 여러 번 입력된 경우 한 번만 출력한다.

 

예제 1 입력.	예제 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

 

 

정답코드:

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
 
 
#define MAX_WORD_LEN    (51)
 
using namespace std;
 
// 문자열과 단어 길이를 멤버 변수로 가지는 class 생성.
class WordNode
{
public:
    int nCount;
    char str[MAX_WORD_LEN];
    WordNode(char InputStr[])
    {
        strcpy(str, InputStr);
        nCount = strlen(InputStr);
    }
};
 
bool CompareNodes(WordNode A, WordNode B)
{
    if (A.nCount == B.nCount)
    {        
        // 단어 길이가 같으면 사전순으로 앞이 먼저.
        return (strcmp(A.str, B.str) < 0);
    }
    else
    {
        // 단어 길이가 다르면 짧은 것 먼저.
        return (A.nCount < B.nCount);
    }
    
}
 
int main()
{
    int N;
    char TmpStr[MAX_WORD_LEN];
    vector <WordNode> v;
 
    // 총 단어 개수 입력.
    scanf("%d", &N);
 
    for(int i = 0; i < N; i++)
    {
        // N개의 단어 입력.
        scanf("%s", TmpStr);
        v.push_back(WordNode(TmpStr));
    }
 
    // CompareNodes 함수의 규칙에 따라 정렬.
    sort(v.begin(), v.end(), CompareNodes);
 
    vector <WordNode>::iterator iter;
    vector <WordNode>::iterator iterNext;
 
    for (iter = v.begin(); iter < v.end(); iter++)
    {
        if (iter != v.end() - 1)
        {
            iterNext = iter + 1;
            if (strcmp(iterNext->str, iter->str) == 0)
            {
                // 다음 단어가 현재 단어와 같으면 출력하지 않음.
                continue;
            }
        }
        // 단어를 출력.
        printf("%s\n", iter->str);
    }
 
    return 0;
}

 

원본 링크: https://www.acmicpc.net/problem/1181