백준 1181번 C, C++ 풀이

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

1181번: 단어 정렬

 

숫자를 정렬하던 기존의 문제와는 달리, 이번에는 문자열을 정렬하는 문제. 비교함수를 작성한 후에, 내장함수를 사용해서 정렬한다.

 

C언어로 풀 때, 원래는 문자열 배열을 사용해서 문제를 해결하려고 했는데, 자꾸 segmentation fault가 떠서, 해결하려다가 도저히 답이 안나와서 그냥 구조체를 만든 후에 해결했다.

 

// C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 문자열로 해결하려 했으나 자꾸 안돼서 그냥 구조체 선언
typedef struct { 
    char word[51];
    int len;
}String;

// compare함수 : 원하는 비교연산을 통해 -1, 0 ,1을 반환한다. qsort에서 쓰는 인자는 const void 포인터.
int compare (const void * p1, const void * p2) { 
    // compare
    String * str1 = (String *)p1;
    String * str2 = (String *)p2;
    
    if (str1->len < str2->len) return -1; // 길이에 따라 반환
    else if (str1->len > str2->len) return 1;
    else return strcmp(str1->word, str2->word); 

}

int main () {
    int n;
    scanf("%d", &n);
    String * strArr = (String *)malloc(sizeof(String) * n); // 동적 할당, 변수가 배열 길이로 들어가는 것을 방지
    
    for (int i = 0; i < n; i++) {
        while (getchar() != '\n'); // 입력받기 전에 입력버퍼를 비운다.
        scanf("%s", strArr[i].word); // 입력받고
        strArr[i].len = strlen(strArr[i].word); // strlen함수로 길이 입력
    }

    qsort(strArr, n, sizeof(String), compare); // quick sort (in stdlib.h)
    
    for (int i = 0; i < n-1; i++) { // 중복 제거
        for (int j = i + 1; j < n; j++) {
            if (!strcmp(strArr[i].word, strArr[j].word)) { // 중복이 발견되면
                strcpy(strArr[j].word, "\0"); // 널문자로 바꿔쓰고
                strArr[j].len = 0; // 길이를 0으로
            }            
        }
    }

    for (int i = 0; i < n; i++) { // 출력
        if(strArr[i].len) printf("%s\n", strArr[i].word);
    }
    free(strArr);
}

 

C++의 경우 벡터에서 중복을 제거하는 방법을 배우게 되었다. 항상 느끼지만 여러모로 C++이 편하다.

// C++
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool compare (string str1, string str2) {
    if (str1.size() == str2.size()) return str1 < str2;
    else return str1.size() < str2.size();
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string temp;
    vector<string> words;
    vector<string>::iterator iter;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> temp;
        words.push_back(temp);
    }
    
    sort(words.begin(), words.end(), compare);
    words.erase(unique(words.begin(), words.end()), words.end()); // 중복제거

    for (iter = words.begin(); iter != words.end(); iter++)
        cout << *iter << '\n';    
}