백준 1181번 문제는 단어 정렬 문제로, 여러 단어가 주어졌을 때 이를 길이가 짧은 것부터, 길이가 같으면 사전 순으로 정렬하는 문제입니다. 이 문제를 해결하기 위해서는 두 가지 주요 단계가 필요합니다: 정렬과 중복 제거입니다.
접근 방법
정렬: 단어들을 먼저 길이에 따라 정렬하고, 길이가 같은 단어들끼리는 사전 순으로 정렬합니다. 이를 위해 사용자 정의 비교 함수를 작성하여 qsort 함수에 사용할 수 있습니다.
중복 제거: 정렬된 단어 목록에서 중복된 단어를 제거합니다. 정렬 과정을 거친 후에는 중복된 단어들이 연속해서 위치하기 때문에, 이전 단어와 현재 단어를 비교하여 중복을 제거할 수 있습니다.
해결 방법
주어진 단어들을 저장할 수 있는 적절한 자료구조를 준비합니다. 예를 들어, 단어와 그 길이를 저장할 수 있는 구조체 배열을 사용할 수 있습니다.
단어를 입력받을 때, 각 단어의 길이도 함께 계산하여 저장합니다.
사용자 정의 비교 함수를 작성하여, 단어의 길이를 기준으로 정렬하고, 길이가 같은 경우 사전 순으로 비교하여 정렬합니다.
정렬된 배열을 순회하면서, 중복된 단어를 출력하지 않습니다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
char word[51]; // 단어를 저장할 배열
int len; // 단어의 길이
} Word;
int compare(const void *a, const void *b) {
Word *wordA = (Word *)a;
Word *wordB = (Word *)b;
if (wordA->len == wordB->len) { // 길이가 같으면 사전 순으로 정렬
return strcmp(wordA->word, wordB->word);
}
return wordA->len - wordB->len; // 길이에 따라 정렬
}
int main() {
int N;
scanf("%d", &N);
Word words[N]; // 단어를 저장할 구조체 배열
for (int i = 0; i < N; i++) {
scanf("%s", words[i].word);
words[i].len = strlen(words[i].word); // 단어의 길이 저장
}
qsort(words, N, sizeof(Word), compare); // 사용자 정의 비교 함수로 정렬
// 중복 제거하며 출력
printf("%s\n", words[0].word);
for (int i = 1; i < N; i++) {
if (strcmp(words[i].word, words[i-1].word) != 0) { // 이전 단어와 다르면 출력
printf("%s\n", words[i].word);
}
}
return 0;
}