Happy Number

== 문제 설명 ==

양의 정수 S0 의 각 아라비아 숫자들의 제곱의 합으로 양의 정수 S1을 만든다고 하자.

동일한 방법이라면, S1으로 S2를 만들 수 있고, 이 후로도 계속 만들 수 있다.

만약 어떤 i(i ≥ 1)에 대해서 Si = 1이라면, 최초의 S0를 Happy Number라고 부른다.

Happy Number가 아닌 수를 Unhappy Number라고 부른다.

예를 들어, 7에서 시작하게 되면 다음과 같은 일련의 순서를 가지게 되며

7, 49(=7^2), 97(=4^2+9^2), 130(=9^2+7^2), 10(=1^2+3^2), 1(=1^2),

따라서 7은 즐거운 수이다.

그리고 4는

4, 16(4^2), 37(1^2+6^2), 58(3^2+7^2), 89(5^2+8^2), 145(8^2+9^2),

42(1^2+4^2+5^2), 20(4^2+2^2), 4(2^2)의 순서로 반복되므로 Unhappy Number이다.

== 입력 ==

첫 라인은 인풋 케이스의 수 n이 주어지며 이후 n라인의 케이스가 주어진다.

각 테스트 케이스는 한 개의 양의 정수 N으로 구성되며 N은 10^9 보다 작다.

== 출력 ==

출력은 주어진 수 N이 Happy Number인지 Unhappy Number인지 여부에 따라 다음과 같이 출력한다.

N이 Happy Number라면 “Case #p: N is a Happy number.”

N이 Unhappy Number라면 “Case #p: N is an Unhappy number.”

p는 1부터 시작하는 케이스의 번호이며 각각의 케이스는 한 줄에 결과를 표시한다.

== 샘플 인풋 ==

3

7

4

13

== 샘플 출력 ==

Case #1: 7 is a Happy number.

Case #2: 4 is an Unhappy number.

Case #3: 13 is a Happy number.

== 채점 기준 ==

  1. 작성한 프로그램은 각각의 테스트케이스에 대해서 올바른 결과를 출력하여야 한다.

  2. 입력 후 결과 출력까지 걸리는 시간이 빠르면 빠를수록 좋다.

(* 이번 문제는 정확한 결과만큼이나 속도도 중요합니다)

  1. 프로그램에서 사용한 자료구조 및 알고리즘이 적절하여야 한다.

  2. 그 외 일반적인 코드 구조, 스타일, 에러/예외 처리 등이 적절할수록 좋다.

UVA 10591 문제이고, 이스트소프트 개발직군 샘플문제로 공개된 자료를 가져왔습니다. 채점기준을 준수한다면 난이도는 좀 더 상승될 것 같습니다.

  • 채점기준에서 속도가 중요하다 했는데, 대부분의 수들이 길지 않은 싸이클로 반복하다보니 처리시간은 순식간입니다. 수십, 수백만개의 Case에 대해 처리시간을 체크해봐야 차이가 날것 같습니다.
simple math happy numbers cycle finding (Floyd's cycle finding algorithm)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

23개의 풀이가 있습니다. 1 / 3 Page

해피넘버, 언해피넘버 및 매 수행시의 이력을 다 저장하는 방법이 있지만, 모든 값을 캐싱하면서 캐싱한 값의 상태에 따라서 결과값을 찾습니다.

  • 해피넘버 ==> 초기값 및 그간의 경로 중에서 값이 미정인 값은 모두 해피넘버
  • 언해피넘버, 미결정값 ==> 해피넘버가 아닌 것으로 판명되므로 초기값 및 미결정 값은 모두 언해피넘버가 됩니다.

재귀호출하면서 상태를 pending --> 다음 결과에 따라 결과 확정하는 식으로 처리했습니다.

enum Happy {
    case Happy, Unhappy, Pending
}

var cache = Dictionary<Int, Happy>()
cache[1] = .Happy

let next:(Int) -> Int = {n in 
    "\(n)".utf8.map{ (Int($0) - 48)*(Int($0) - 48) }
    .reduce(0, combine:(+))
}

func test(n: Int) -> Bool {
    if let r = cache[n] {
        switch r {
        case .Happy: return true
        case .Unhappy: return false
        default:
            cache[n] = .Unhappy
            return false
        }
    }
    cache[n] = .Pending
    let r = test(next(n))
    cache[n] = r ? .Happy : .Unhappy
    return r
}

func main(){
    guard let input = readLine() else { return }
    let data = input.characters.split(" ").map{ Int(String($0))! }
    for (i, e) in data.enumerate() {
        print("case #\(i+1) \(e) is \(test(e) ? "a Happy" : "an Unhappy") number.")
    }
}

main()

아래는 같은 아이디어에 대한 파이썬 구현입니다.

# 0: unhappy
# 1: happy
# 2: pending
cache = {1: 1}

def f(n):
    if n in cache:
        if cache[n] == 1:
            return True
        cache[n] = 0
        return False
    cache[n] = 2
    m = 0
    while n > 0:
        m += (n % 10)**2
        n = n // 10
    r = f(m)
    if r:
        cache[n] = 1
    else:
        cache[n] = 0
    return r

p = int(input())
ins = []
for _ in range(p):
    ins.append(int(input()))
for i, e in enumerate(ins):
    print("Case #{}: {} is {} number.".format(
        i+1, e, "a Happy" if f(e) else "an Unhappy"))

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
#Python 3.5
T=[3,7,4,13]
def happyNumber(d) :
    numbers=[]
    unhappy=[]
    l=d
    while(l != "1" ) :
        for i in range(len(l)) :
            a = int(l[i])*int(l[i])
            numbers.append(a)
        l = str(sum(numbers))
        del numbers[0:len(numbers)]
        if l == d : return False
        for i in unhappy :
            if i == l : return False
        unhappy.append(l)
    return True

if len(T)-1 != T[0] :
    print("영혼이 비정상...")
    exit()
else : T.pop(0)

#T=range(2,10000) #속도테스트
for i,d in enumerate(T) :
    if happyNumber(str(d)) :
        print("Case #"+(str(i+1))+": %s is a Happy number."%d)
    else :
        print("Case #"+(str(i+1))+": %s is an Unhappy number."%d)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
//class 
//HappyNumber.isHappyNumber(7) is True;
//HappyNumber.isHappyNumber(42) is false;
public class HappyNubmer 
{
    public static bool isHappyNumber(int number)
    {
        bool isHappy = false;
        List<int> numberList = new List<int> ();
        int nextNumber = number;
        while (true) {
            nextNumber = getNextNumber (nextNumber);

            if (numberList.Contains (nextNumber)) {
                isHappy = false;
                break;
            }

            if (nextNumber == 1) {
                isHappy = true;
                break;
            }

            numberList.Add (nextNumber);
        }

        return isHappy;
    }

    public static int getNextNumber(int number)
    {
        List<int> splitedNumbers = splitNumber (number);

        int nextNumber = 0;
        foreach (int splitedNumber in splitedNumbers) {
            nextNumber += square (splitedNumber);
        }

        return nextNumber;
    }

    public static List<int> splitNumber(int number)
    {
        List<int> splitedNumber = new List<int> ();

        int splitNumber = number;
        while (true) {
            splitedNumber.Insert(0,splitNumber % 10);

            if (splitNumber < 10)
                break;

            splitNumber = splitNumber / 10;
        }

        return splitedNumber;
    }

    public static int square(int number)
    {
        return number*number;
    }
}


//nunit test
[TestFixture]
public class HappyNumberTest {
    [Test,Sequential]
    public void isHappyNumberTest([Values(7,42)]int n,[Values(true,false)]bool r)
    {
        bool check7 = HappyNubmer.isHappyNumber (n);
        Assert.AreEqual (r, check7);
    }

    [Test]
    public void getNextNumberTest()
    {
        int number1 = 7;
        int nextNumber = HappyNubmer.getNextNumber (number1);

        Assert.AreEqual (49, nextNumber);
    }

    [Test]
    public void splitNumberTest()
    {
        int number1 = 130;
        List<int> result = HappyNubmer.splitNumber (number1);

        Assert.AreEqual (1, result [0]);
        Assert.AreEqual (3, result [1]);
        Assert.AreEqual (0, result [2]);
        Assert.AreEqual (3, result.Count);
    }

    [Test]
    public void squareTest()
    {
        int number1 = HappyNubmer.square (5);

        Assert.AreEqual (number1, 25);

    }
}

공부중인 ttd를 활용해서 한번..

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
def check_num(n, List):
    if n == 1:
        return 1

    Next_n = sum([int(x) ** 2 for x in list(str(n))])

    if Next_n in List:
        return 0
    else:
        List.append(Next_n)
        return check_num(Next_n, List)


if __name__ == '__main__':
    case_n = input('Input case number: n = ')
    for i in range(int(case_n)):
        while True:
            n = int(input('Number: '))
            if n <= pow(10,9):
                break
        decision = check_num(n, [])
        print('Happy Number' * decision + 'Unhappy Number' * (not decision))
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

초짜입니다. ^^ 문자열을 아직 잘 다루지 못 해 수학 함수로만 짜 봤습니다. 제대로 짰는지 모르겠네요. 일단 test 결과는 제대로 나오는데...

# tried to find happy number only with math functions

import math
n = int(input("how many happy number candidates? "))

while n > 0:
    a = int(input("type in happy number candidate: "))
    c = 10

    while c >=10:
        b = math.floor(math.log10(a))
        c = 0

        while b >= 0:
            c = c + ((a // (10 ** b)) ** 2)
            a = a % (10 ** b)
            b = b - 1

        a = c

    if c == 1:
        print ("happy")
    else:
        print ("unhappy")

    n = n - 1
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Python으로 작성

# find happy number
def is_happy_num(s0, history=[]):
    s1 = sum(map(lambda x:x*x, [int(i) for i in repr(s0)]))    
    if s1 == 1:
        return True
    elif s1 in history:
        return False
    else:
        history.append(s1)
        return is_happy_num(s1)

# Test case
for i, num in enumerate([3,7,4,13]):
    case = "Case #%d: %d is " % (i, num)
    result = "Happy number." if is_happy_num(num, []) else "an Unhappy number."
    print(case + result)

결과
Case #0: 3 is an Unhappy number.
Case #1: 7 is Happy number.
Case #2: 4 is an Unhappy number.
Case #3: 13 is Happy number.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Haskell로 작성

import Data.Char (digitToInt)
import Control.Monad (join)

is_happy_number n history
    | sumnum == 1 = True
    | sumnum `elem` history = False
    | otherwise = is_happy_number sumnum (sumnum:history)
    where sumnum = sum [(digitToInt x)^2 | x<-show(n)]

test_happy_number n = join [show(n), " is ", (if is_happy_number n [] then "a Happy" else "an Unhappy"), " number."]

main = do
    mapM_ putStrLn $ map test_happy_number [3,7,4,13]

결과
3 is an Unhappy number.
7 is a Happy number.
4 is an Unhappy number.
13 is a Happy number.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

def happy(a) : aa =[] n=a

while True: b=n s=0 while n>0 : s+= pow( n%10,2) n/= 10

if s == 1 : print str(a) + " is happy number." break elif s in aa: print str(a) + " is unhappy number." else : aa.append(b) n = s

a = [7,4,13]

for i in a: happy(i)

모바일로 작성해서 어떻게 보일지 모르겠네요

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
  • 두번째 풀이 이구요, 좀 더 효율적으로 해피넘버를 찾아보았습니다. 언어는 C#입니다.
  • 현재의 S0가 언해피넘버로 정해졌을 경우, 그 수의 모든 Si들을 언해피넘버 테이블에 저장
  • 현재의 S0가 해피넘버로 정해졌을 경우, 그 수의 모든 Si들을 해피넘버 테이블에 저장
  • 그래서 다음 S0의 Si가 양쪽 테이블리스트상에 존재하는지 판단하는 방식입니다
  • 테이블에 존재한다면 계산하나마나 어차피 이전과 같은 결과로 수렴이 되기 때문입니다
  • 그래서 대부분의 S0들은 1-2번의 계산만으로 해피넘버가 판별될 수 있었습니다
  • 제한수가 10^9 = 10억이지만 Si들은 1 ~ 729까지 뿐이 나오지 않기 때문에 테이블 메모리는 얼마 되지 않았습니다
  • 1도 하나의 해피넘버 Si로 보고 초기화시에 추가하였습니다
  • 1부터 1000만까지 총 1000만개의 샘플 입니다. 제 컴퓨터에서(i7 4790k)의 처리시간은 약 0.66초 정도 나옵니다.
static void Main()
{
    Stopwatch sw = new Stopwatch();
    sw.Start();

    int i, temp, digit, si, nHappyNum = 0;
    HashSet<int> listHappy = new HashSet<int>() { 1 };
    HashSet<int> listUnhappy = new HashSet<int>();
    List<int> listCurrent = new List<int>();

    for (int s0 = 1; s0 < 10000001; s0++)
    {
        if (listCurrent.Count > 0) listCurrent.Clear();
        temp = s0;

        while (true)
        {
            si = 0;
            do
            {
                digit = temp % 10;
                si += digit * digit;
            }
            while ((temp /= 10) > 0);

            if (listUnhappy.Contains(si) || listCurrent.Contains(si))
            {
                for (i = 0; i < listCurrent.Count; i++)
                    listUnhappy.Add(listCurrent[i]);
                break;
            }
            if (listHappy.Contains(si))
            {
                nHappyNum++;
                for (i = 0; i < listCurrent.Count; i++)
                    listHappy.Add(listCurrent[i]);
                break;
            }

            listCurrent.Add(si);
            temp = si;
        }
    }

    Console.WriteLine(string.Format("Elapsed Time : {0}", sw.Elapsed));
    Console.WriteLine(string.Format("Number of HappyNumber (1 ~ 10000000) : {0}", nHappyNum));
}

결과

  • Elapsed Time : 00:00:00.6631938
  • Number of HappyNumber (1 ~ 10000000) : 1418854
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

C언어 입니다.! 다른 분들의 경우를 참고해서 풀어봤어요~!(해쉬테이블) 더 분발해야 겠습니다!

#include <stdio.h>
#define BK 1000
#define SL 1
int hashtable[BK][SL];

int Hash(int key)
{
    return key % 10;
}
void AddNum(int num)
{
  int bucket = Hash(num);
  if(hashtable[bucket][0] == 0){
     hashtable[bucket][0] = num;
  }
}
int FindNum(int num)
{
  int bucket = Hash(num);
  return (hashtable[bucket][0] == num);
}

int main()
{
  int t, TC = 5;

  for(t=0; t<TC; t++){
    int N, sN;
    int sum, digit;

    scanf("%d", &N);
    sN = N;
    memset(hashtable, 0, sizeof(hashtable));

    while(1){
        sum = 0;
        do
        {
          digit = N % 10;
          sum += digit * digit;
        }while((N/=10) > 0);

        N = sum;
        //printf("N = %d \n", N);

        if(N == 1) break;
        else if((FindNum(sum)) == 1) break;
        else AddNum(sum);
    }

    if(N == 1) printf("Case #%d : %d is Happy Number.\n", t+1, sN);
    else printf("Case #%d : %d is Unhappy Number.\n", t+1, sN);

  }

  return 0;
}

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.

simple math x 1
happy numbers x 1
cycle finding (Floyd's cycle finding algorithm) x 1

언어별 풀이 현황
전 체 x 23
java x 1
기 타 x 2
python x 12
cpp x 2
haskell x 1
cs x 3
r x 1
ruby x 1