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

백준 온라인 저지(BOJ) 1181번 단어 정렬
https://www.acmicpc.net/problem/1181

1181번: 단어 정렬

* 사용언어 : C언어, C++
 

1. 문제

알파벳 소문자 단어 N개를 ① 길이 짧은 것부터 ② 같으면 사전 순 정렬하여 출력
단, 중복된 단어는 하나만 남기고 제거
 

2. 풀이

단어가 최대 20,000개로 그리 많지는 않지만 문자열 비교 시 loop 가 필요하므로
시간 복잡도가 nlogn 인 정렬 방법 중 하나로 구현했습니다.
 
같은 카테고리 내의 다른 문제를 풀면서 계수 정렬과 병합 정렬을 구현해봤으니,
이 문제는 힙 정렬로 구현해봤습니다.
 
정확히 말하면 힙 정렬로 푼 것은 아니고
힙 자료구조만 활용하여 힙에 전부 넣었다가 하나씩 빼면서 출력했습니다.
 

1) 중복 제거

중복 제거는 pop 하는 시점에 처리하도록 했습니다.
(입력을 받고 자료구조에 담을 때에는 고려 X)
 
pop 할 때마다 이전에 마지막으로 pop 된 문자열과 비교해서
같으면 출력하지 않고 skip, 다르면 출력하고 마지막 pop 된 문자열을 업데이트 했습니다.
 

2) 문자열 구조체

문자열을 비교할 때 마다 문자열의 길이를 계속 확인해야하기 때문에
_str 이라는 구조체(struct)를 선언하고 길이를 저장해두었습니다.
(불필요한 strlen 중복 호출 방지)
 
 
나머지 풀이는 아래 코드로 설명 대체하겠습니다.
 
개인적으로 준비 중인 시험에서 library 를 쓸 수 없기 때문에
문자열 처리와 힙 자료구조는 직접 구현해보았습니다.
 
본인 상황에 맞춰서 string.h, algorithm 등의 library 를 포함하여 구현하셔도 좋을 것 같습니다.

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
1181_단어 정렬
2364KB	32ms
*/
#include <cstdio>

const int LM = 20000;
const int CLM = 51;
int n;

struct _str {
	int len;
	char s[CLM];
} STR[LM];

_str *h[LM + 1]; // 1 base
int hs;

int my_strlen(const char *s) {
	int len = 0;
	while (*s++) ++len;
	return len;
}

int my_strcmp(const char *a, const char *b) {
	while (*a && *b && *a == *b) a++, b++;
	return *a - *b;
}

void my_strcpy(const char *src, char *dst) {
	while (*src) *dst++ = *src++;
	*dst = 0;
}

int compare(_str *a, _str *b) {
	if (a->len == b->len) return my_strcmp(a->s, b->s);
	return a->len - b->len;
}

void swap(_str **a, _str **b) { 
	_str *t = *a;
	*a = *b;
	*b = t;
}

void push(_str *s) {
	h[++hs] = s;
	for (int c = hs; c > 1; c >>= 1) {
		if (compare(h[c], h[c >> 1]) < 0) swap(&h[c], &h[c >> 1]);
		else break;
	}
}

_str *pop() {
	_str *v = h[1];
	h[1] = h[hs--];

	for (int c = 2; c <= hs; c <<= 1) {
		if (c + 1 <= hs && compare(h[c + 1], h[c]) < 0) ++c;

		if (compare(h[c], h[c >> 1]) < 0) swap(&h[c], &h[c >> 1]);
		else break;
	}
	return v;
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		_str *str = &STR[i];
		scanf("%s", str->s);
		str->len = my_strlen(str->s);
		push(str);
	}

	char prev[CLM];
	for (int i = 0; i < n; ++i) {
		_str *str = pop();
		if (!my_strcmp(str->s, prev)) continue;

		my_strcpy(str->s, prev);
		printf("%s\n", prev);
	}
	return 0;
}