[백준 알고리즘] 4673번 - 셀프 넘버 (qsort()의 사용)

1. 문제 및, 실행결과 예시

 

 단계별로 문제 풀기에서 첫 함수 카테고리 문제이다. 15596번이 빠진것에 의아해하시는 분들이 있을 수도 있지만, 이 문제를 올리기에는 너무 쉽다는 생각이 들었다...... 이 문제를 풀면서 우리 교수님이 하셨던 말씀이 떠올랐다. "프로그래머는 자신이 모르는 분야여도, 공식이나 일반식이 주어진다면 그것을 코드로 구현할 수 있어야 합니다." 처음엔 그저 그런 이야기라고 생각했지만, 이 문제를 풀면서 왜 그런 말을 해주셨는지 뼈저리게 느끼게 되었다. 다음은 문제와 실행결과 예시이다.

 

출처: https://www.acmicpc.net/problem/4673

4673번: 셀프 넘버

---

4673번 문제 설명

---

 문제를 보면 셀프 넘버에 대한 설명이 나온다. 나는 수학학과도 아니고 대학교 수학 성적에는 상관없이 수학을 잘 하지도 않는다. 셀프 넘버에 대한 설명을 듣고 요구되는 코드를 작성해야 한다는 것만을 안다. 문제를 푸는 과정은 밑에서 확인하고 먼저 실행 결과 예시를 보자.

---

4673번 예시 실행결과

---

 이 문제는 예시 입력이 없다. 아마 블로그에 올린 문제중에서 에시 입력이 없는 문제는 이번이 처음인 것 같다. 출력은 간단하다 그저 해당되는 모든 수를 한 줄에 하나씩 출력하면 된다.

 

2. 문제 풀이

 

 처음에 코드를 구상할 때, 생각했던 방법은 1 부터 10000까지의 숫자 중 셀프 넘버를 검사하여 출력하는 방법이다. 1이 셀프 넘버인지 아닌지를 검사하고, 셀프 넘버이면 출력하고, 그렇지 않으면 넘어가는 방식으로 코드를 구상하였다. 그러나 나의 머리로는 도저희 이 수가 셀프 넘버인지 아닌지를 판단할 수 없었다. 때문에 다른 방법을 선택하였다. 일단 1부터 10000까지의 숫자를 i라고 했을 때, 모든 d(i)를 구한 리스트를 만들고, 다시 1부터 10000까지의 숫자를 차례대로 그 리스트와 비교하여, 숫자가 리스트에 존재하면, 넘어가고 리스트에 존재하지 않으면 넘어가는 방식을 생각하였다. 이게 제일 확실하기 때문이다. 나름 사용하는 메모리와 시간 복잡도를 줄이기 위해 리스트를 정렬하고 그 안에서 찾는 코드를 작성하였다.

 

 전체적인 문장만을 봤을 때는 잘 모를 수도 있다. 그래서 차례 차례 설명해 보려 한다. 일단 내가 작성한 d함수이다. 이 함수의 역할은 i의 d(i)를 구하는 역할이다.

 

int d(int x) {
	int ans = x;
	while (x) {
		ans = ans + (x % 10);
		x = x / 10;
	}
	return ans;
}

 

 들어오는 수의 자릿수를 모르기 때문에, 뒤에서 부터 mod를 사용하여 더해주는 방식을 사용하였다. 다음은 정렬이다. 모든 d(i)의 값을 구한 후 이 값을 리스트에 넣고 이 리스트를 작은 수 부터 큰 수까지 정렬하기 위해서는 정렬함수를 사용해야했다. 정렬함수는 C의 <stdlib.h> 라이브러리에서 제공하는 qsort()함수를 사용하였다.

 

qsort()에 대해서 간단하게 설명하자면, qsort()에서 사용해야하는 비교 함수를 직접 작성해야 한다는 것이다. 이유는 다양한 자료형으로 qsort()함수를 사용할 수 있기 때문이다. Java를 배우시는 분들은 sort()메소드를 사용하기 위해 toCompare()메소드를 오버라이딩하는 과정과 비슷하도 생각하면 된다. 다음은 내가 작성한 정렬 함수이다.

 

int static compare(const void* first, const void* second)
{
	if (*(int*)first > *(int*)second)
		return 1;
	else if (*(int*)first < *(int*)second)
		return -1;
	else
		return 0;
}

 

 그 다음에 작성한 함수는 한 정수가 정수 배열안에 있는지, 없는지를 검사해주는 isIn함수이다. Python을 사용하면 쉽게 해결할 수 있지만, 이왕 C언어로 시작한거 C언어로 마무리를 짓고 싶었다. 그리고 정렬된 리스트를 사용한다면 그렇게 어렵지도 않았다. 다음은 내가 작성한 isIn()함수이다.

 

int isIn(int *list, int n) {
	while (1) {
		if (*list == n)
			return 1;
		if (*list > n)
			return 0;
		list++;
	}
}

 

 다시 한번 단계를 설명하자면, 1부터 10000까지의 d(i)를 구하여 넣은 리스트를 만들고, 그 해당 수가 리스트에 있는지 없는지를 판별하여 출력하는 것이 전체적인 나의 알고리즘이다. 다음은 내가 작성한 전체 코드이다.

 

#include <stdio.h>
#define SIZE 10000
#include <stdlib.h>

int d(int x);
int isIn(int *list, int n);
int static compare(const void* first, const void* second)
{
	if (*(int*)first > *(int*)second)
		return 1;
	else if (*(int*)first < *(int*)second)
		return -1;
	else
		return 0;
}

int main(void) {
	int ans[SIZE] = {0};
	int count = 0;
	int i;
	for (i = 1; i < SIZE; i++) {
		ans[i - 1] = d(i);
		count++;
	}
	qsort(ans, SIZE, sizeof(int), compare);
	for (int i = 1; i <= SIZE; i++) {
		if (!isIn(ans, i))
			printf("%d\n", i);
	}
	return 0;
}

int d(int x) {
	int ans = x;
	while (x) {
		ans = ans + (x % 10);
		x = x / 10;
	}
	return ans;
}

int isIn(int *list, int n) {
	while (1) {
		if (*list == n)
			return 1;
		if (*list > n)
			return 0;
		list++;
	}
}

 

3. 결어

 

 사실 정렬알고리즘을 사용할 때, 급하게 구글링을 통해 찾게 되었다. 엄밀하게 말하자면, 정렬이 없이 구현할 수 있었지만, 이왕 마음먹은거, 끝까지 하고싶어 고집을 부렸다. 정렬에 대한 것을 자세히 다뤄, 이 블로그에 올리는 날이 왔으면 좋겠다.