[백준]_1181번 : 단어 정렬(파이썬 and C언어)

 

1181번: 단어 정렬

 

그냥 말 그대로 조건들만 만족시키면 된다. 다행히도 파이썬은 리스크에 문자형 자료형이 있어도 sort을 사용하면 알파벳 순서로 정리해 주는 쩌는 기능이 있다. 또한 중복을 제거하는 조건은 집합(set)을 통해 간단히 해결할 수 있는데, 대신 순서가 중구난방으로 바뀌기 때문에 다시 list로 만들어주는 작업은 수도 없이 해보아서 이번 문제는 그다지 험난한 길이 아닐 것 같다

---

전략

• 단어를 하나 씩 리스트(ls)로 받는다. 그냥 input과 sys를 이용했을 때 뭐가 달라지는지 비교도 해볼 것이다. 
• ls에 존재하면 중복을 모두 없애주고(set), 리스트화 시킨뒤(list), 정렬해 준다(sorted).
• 한 단어당 최대 글자수가 50이므로 1부터 50까지 글자 수를 세주면서(range로 셀 것이기 때문에 표기상 51까지 표시해야 됨) 그 길이에 해당되는 단어들부터 차례대로 출력

---

시도 1(파이썬)

ls=[]
for i in range(int(input())):
    ls.append(input())
ls=sorted(list(set(ls)))
for i in range(1,51):
    for el in ls:
        if len(el)==i:
            print(el)

---

import sys
ls=[]
for i in range(int(sys.stdin.readline().strip())):
    ls.append(sys.stdin.readline().strip())
ls=sorted(list(set(ls)))
for i in range(1,51):
    for el in ls:
        if len(el)==i:
            print(el)

<평가> 시간이 900 ms에서 168 ms까지 떨어졌다!! 역시 sys를 쓰는 이유는 여전히 굳건함을 깨달았다.

---

시도 2(C언어)

내가 현재 알고 있는 지식으로는 도저히 깔끔한 최종 코드를 써내는 것이 불가능해 보여서 다른 고수들의 코드들을 참고해 보았다.  이를 통해 새로 배워야 할 지식들이 있음을 알게 되었다. 그것은 바로 배열을 정렬하는 데에 이용되는 C언어의 표준 라이브러리 함수인 qsort 함수이다. 

---

추가 정리

qsort 함수는 <stdlib.h> 헤더 파일에서 선언되어 있으며, 함수의 원형은 다음과 같다.

void qsort(void* base, size_t nmemb, size_t size, int (*compar)(const void*, const void*));

• base : 정렬될 배열의 첫 번째 요수의 주소를 가리키는 포인터
• nmemb : 배열의 요소 개수
• size : 배열의 각 요소의 크기
• compar : 비교 함수의 포인터. qsort 함수는 이 함수의 반환 값을 기반으로 배열의 요소들을 비교하고 정렬 순서를 결정 

더 깊게 파고들기 전에 우리의 기본 셋업은 아래와 같다. 최대 20000개의 단어들을 수록할 수 있는 2차원 배열을 선언하고 열의 크기는 51로 선언해 준다. 왜냐하면 c언어에서 문자열을 받을 때는 n개의 알파벳이 들어 있어도 마지막 엔터키(\n)까지 포함시키기 때문이다.

#include <stdio.h>
#include <stdlib.h> 
int main(void)
{    
	int size, length = 51;
	char arr[20000][51] = { 0 };
	scanf("%d", &size);

	for (int i = 0; i < size; i++)      
		scanf("%s", arr[i]);

 

우리 같은 경우에는 arr(base), nmemb(size), size(sizeof(arr[0])), compar(fuction) 으로 작성하면 될 것으로 보인다.

즉 정리하자면 우리는 아래와 같은 코드를 사용해야 한다.

qsort(arr, size, sizeof(arr[0]), compare);

자, 그렇다면 메인 메뉴인 compare 함수를 어떻게 짤 것인가가 관건이다. 그전에 qsort에 대한 사실을 한 가지 더 소개하고 넘어가야 한다. 그것은 바로 compare 함수의 반환 값에 따른 배열 인자(a,b 라 가정. a는 b보다 배열 내 순서에서 앞선다)들의 동향이다. 아래의 표를 보며 이해해 보자.

compare의 반환 값	인자(요소)들의 관계	정렬 유무
양수	a>b	자리 교체
0	a==b	유지
음수	a<b	유지

즉 아래와 같은 코드를 짤 수 있다.

int compare(const void* arg1, const void* arg2) 
{   
	if (strlen((const char*)arg1) > strlen((const char*)arg2)) return 1;
	else if (strlen((const char*)arg1) < strlen((const char*)arg2)) return -1;
	else return strcmp((char*)arg1, (char*)arg2);  
}

참고로 위에서 포인터 앞에 const(한정자)를 붙여준 이유는 포인터를 상수 화함으로써 포인터가 가리키는 값을 변경하지 못하도록 지정하기 위해서이다. 즉 안정성을 위한 장치이다.

 

이제 크기 순으로 정렬은 완료되었다. 유일하게 남은 과제는 길이가 같은 단어의 사전순 정렬이다. 그래서 있는 것이 strcmp 함수이다. 이것은 <string.h> 헤더 파일에서 지원하는 함수로 두 개의 문자열을 비교하는 데 사용된다. 본 형태는 아래와 같다.

int strcmp(const char* str1, const char* str2);

compare 함수와 마찬가지로 반환 값의 동향을 살펴보면 아래와 같다.

strcmp의 반환 값	인자 사이의 관계	정렬 유무
양수	str1이 사전식 순서상 뒤	자리 교체
0	두 인자가 같음	유지
음수	str1이 사전식 순서상 앞	유지

또한 이 함수에서 반환 값의 부호에 따라 사전식이 정해지는지 명확한 이유가 있다. 두 문자열의 앞 알파벳을 아스키코드로 바꾸어 str1에서 str2를 뺀다. 사전 순서상 뒤에 있을수록 아스키코드가 크기 때문에 이 값이 양수이면 str1을 str2 뒤로 보내야 함을 알 수 있다. 여기까지 알게 되었으면 문제를 거의 다 푼 것이다. 하지만 아직 중복 문자열을 제거하는 작업을 하지 않았다. 따라서 우리는 strcmp의 반환 값이 0일 때를 이용할 것이다. 즉 직전 문자열과 현재 문자열의 strcmp반환 값이 0이면 출력을 무시하는 것이다.

---

마무리

#include <stdio.h>
#include <stdlib.h> 
#include <string.h>
int compare(const void* arg1, const void* arg2) 
{   
	if (strlen((const char*)arg1) > strlen((const char*)arg2)) return 1;
	else if (strlen((const char*)arg1) < strlen((const char*)arg2)) return -1;
	else return strcmp((char*)arg1, (char*)arg2);
} 
int main(void)
{    
	int size, length = 51;
	char arr[20000][51] = { 0 };
	scanf("%d", &size);

	for (int i = 0; i < size; i++)      
		scanf("%s", arr[i]);

	qsort(arr, size, sizeof(arr[0]), compare);
	
	for (int i = 0; i < size; i++) {
		if (strcmp(arr[i], arr[i+1]) != 0 || i == size - 1)
			printf("%s\n", arr[i]);
	}
	return 0;
}