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

백준 1181번: 단어 정렬

단계별로 풀어보기 12단계(정렬) 8번 문제

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

1181번: 단어 정렬

---

문제 설명

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

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

---

입력과 출력

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

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

---

접근 방법

이번 문제는 단어 개수 N을 입력받고, 소문자로 이루어진 알파벳 단어를 N개만큼 입력받아서 정렬을 하는 문제다. 정렬 순서는 문자열의 길이가 우선시되며, 같으면 사전순으로(A~Z)로 비교해서 풀이하면 된다.

이번 문제는 합병 정렬(merge sort)을 이용해서 해결했다. 합병 정렬은 간단하게 말해서 입력받은 숫자 배열을 반으로 쪼개서 정렬한 후 다시 합치는 방법이다. 이 방법은 시간복잡도가 항상 O(nlogn)으로 나와서 안정적인 방법이다. 이전까지 사용했던 퀵 정렬(quick sort)은 특정 값을 기준으로 보다 작은 값, 보다 큰 값으로 나눠 각각 정렬하는데, 이방법도 대부분의 경우 O(nlong)을 보여주지만, 특정 값이 제일 작거나 제일 큰경우처럼 최악의 경우 O(n^2)의 시간복잡도를 보여주기 때문에 비교적 덜 안정적이다. 이번 문제에서는 퀵 정렬을 사용하지 않은 것은 이때문이다.

앞서 설명했던 것처럼, 정렬을 할때는 문자열의 길이를 우선적으로 비교해야하고, 이후 각 문자를 사전순으로 비교해야한다. 그래서 구조체를 사용해서 해당 문자열의 길이를 저장할 int형 변수 length와 문자를 저장할 배열 arr을 입력했다. 최대 문자열의 길이는 50이므로 크기는 51로 한다. 그리고 merge함수에서는 위 조건들을 활용해서 비교하고 정렬하도록 만든다.

출력할때, 같은 문자열이 여러번 입력된 경우 한번만 출력해야하므로 if문과 strcmp를 사용해서 같지 않은경우만 출력하도록 하면 해결할 수 있다.

---

코드

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

typedef struct {
	int length;
	char arr[51];
} string;

string *sorted;

void merge(string *s, int left, int mid, int right) {
	int i, j, k;
	i = left, j = mid + 1, k = left;

	while (i <= mid && j <= right) {
		if (s[i].length < s[j].length)
			sorted[k++] = s[i++];
		else if (s[i].length > s[j].length)
			sorted[k++] = s[j++];
		else {
			if (strcmp(s[i].arr, s[j].arr) < 0)
				sorted[k++] = s[i++];
			else
				sorted[k++] = s[j++];
		}
	}

	if (i > mid)
		while (j <= right)
			sorted[k++] = s[j++];
	else
		while (i <= mid)
			sorted[k++] = s[i++];
	
	for (k = left; k <= right; k++)
		s[k] = sorted[k];
}

void merge_sort(string *s, int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;
		merge_sort(s, left, mid);
		merge_sort(s, mid + 1, right);
		merge(s, left, mid, right);
	}
}

int main(int argc, char *argv[]) {
	int N;
	scanf("%d", &N);

	string *s = (string *)malloc(sizeof(string) * N);
	sorted = (string *)malloc(sizeof(string) * N);

	for (int i = 0; i < N; i++) {
		scanf("%s", s[i].arr);
		s[i].length = strlen(s[i].arr);
	}

	merge_sort(s, 0, N - 1);

	for (int i = 0; i < N; i++) {
		if (i == 0)
			printf("%s\n", s[i].arr);
		else if (strcmp(s[i - 1].arr, s[i].arr) != 0)
			printf("%s\n", s[i].arr);
	}

	free(s);
	free(sorted);

	return 0;
}

---

결과

백준 제출 결과

실수로 출력할때 같은 문자열을 출력하지 않는 문장을 입력하지 않아서 아쉽게 한번 틀렸었다..