[ACM-ICPC][BOJ] 14954 - HAPPY NUMBER 코드반성

안녕하세요

여행벌입니다.

오늘은 HappyNumber 문제에 대해서 스터디를 진행할 때,

알고리즘 고수... 갓웅님의 코드를 보면서 배운 점에 대해서 정리해보겠습니다.

(기존 여행벌의 코드)

https://travelbeeee.tistory.com/5

---

[배운점]

1. 자릿수를 구해서 제곱해서 더하는 과정.

-갓웅코드

int f(int n)
{
    int sum = 0;

    while(n > 0) {
        sum += (n % 10) * (n % 10);
        n = n / 10;
    }

    return sum;
}

-내코드

/* 자리수별로 자른다. */
/* 자리수별로 제곱해서 더한 값을 return해준다. */
int divide(int ninput) {
	/* 이 부분 예외처리 안해서 틀렸음.*/
	if (ninput < 10) {
		return ninput * ninput;
	}
	int out = 0;
	nlist[0] = ninput / 1000000000;
	nlist[1] = (ninput % 1000000000) / 100000000;
	nlist[2] = (ninput % 100000000) / 10000000;
	nlist[3] = (ninput % 10000000) / 1000000;
	nlist[4] = (ninput % 1000000) / 100000;
	nlist[5] = (ninput % 100000) / 10000;
	nlist[6] = (ninput % 10000) / 1000;
	nlist[7] = (ninput % 1000) / 100;
	nlist[8] = (ninput % 100) / 10;
	nlist[9] = (ninput % 10);
	for (int i = 0; i < 10; i++) {
		if (nlist[i] != 0)
			out += nlist[i] * nlist[i];
	}
	return out;
}

같은 작업을 하고 있지만, 누가 봐도 갓웅의 코드가 훨씬 간결하고 가독성이 좋다.

for문 , % , / 를 이용하면 정말 짧고 간단한 코드로 자릿수를 구할 수 있다는 것을 깨달았다.

 

2. 순환(Cycle)이 생기는지 안 생기는지 체크하는 과정.

-갓웅코드

    if(n <= 729) 
    	v[n] = true;

    while(true) {
        int sum = f(n);
        if(sum == 1) {
            cout << "HAPPY";
            break;
        }
        else {
            if(v[sum] == true) {
                cout << "UNHAPPY";
                break;
            }
            v[sum] = true;
            n = sum;
        }
    }

-내코드

// 지금까지나왔던 값 중에서 현재 값이 있는지 없는지 확인한다.
bool check_repeat(int ninput, int count) {
	for(int i =0 ; i< count; i++){
        if(repeat[i] == ninput)
            return true;
    }
    return false;
}

갓웅은 자릿수의 제곱의 합이 가장 큰 숫자가 999,999,999일 때 729인 것을 캐치하고 v[730]라는 bool 리스트를 만들었다. 그리고 각 자릿수의 제곱의 합을 구해나가면서 그에 해당하는 index를 true 값을 주었고, 다시 한번 true가 나오면 UNHAPPY를 출력해주는 방법으로 진행했다.

나는 기존의 값들을 int형 리스트에 담아두었다가, 순회하면서 다시 나온 숫자가 없는지 찾아줬다.

따라서 갓웅 O(1) vs 여행벌 O(n) 이라는 말도 안 되는 차이를 가진 알고리즘이 만들어졌다.

---

공부하자...