[Project Euler] Coding Quiz 1

 

출처가 사이냅소프트 채용퀴즈라길래 뭐하는 데인가 했더니 이 사이트를 운영하는 회사였다. 사이트 첫 페이지(https://euler.synap.co.kr/)에서 확인할 수 있다.

 

 

원래는 SW 회사인 것 같고 이 문제를 당사 채용 문제로 출제한 모양이다.

 

아무튼 나는 이 문제의 더 어려운 버전인 92번 문제를 푼 뒤에 이 문제를 풀었기 때문에 쉽게 풀 거라고 생각했다.

하지만 어림도 없지 ㅋㅋ

public class Main {
    public static void main(String args[]) {
      System.out.println(run());
    }
 
    public static String run() {
        long n = 9999 + 1;
        long count1 = 0;
        long count2 = 0;
 
        while(--n > 0) {
            String temp = Long.toString(n);
            long sum;
            do {
                sum = 0;
                for(int i = 0; i < temp.length(); i++) {
                    long a = (long)(temp.charAt(i) - '0');
                    sum += (a*a);
                }
 
                
                if(sum == 1) {
                    ++count1;
                    count2 += ((long)n);
                } else {
                    temp = Long.toString(sum);
                }
 
            } while((sum != 1) && (sum != 89));
        }
 
        return Long.toString(count1*count2);
    }
}

 

8~10행:

 count1 은 행복수의 개수,  count2 는 행복수들의 합.

 

12~13행:

 n 을 문자열로 변환해  temp 에 저장한다.

 sum 은 자릿수 제곱의 합.

 

16~19행:

문자열로 변환된  n 의 길이(=자릿수)만큼 반복하며 각 자릿수의 제곱을  sum 에 더한다.

 

22행~27행:

 sum  값이 1이면(=  n 이 행복수면)  count1 은  1  증가하고  count2 는  n  증가한다.

 

29행:

탈출 조건은 자릿수의 합이 1이거나 89가 되는 것.

이 조건이 유효한 건 모든 수에 대해 자릿수의 합을 구하면 1 또는 89로 끝나기 때문(92번 문제에 밝혀져 있다.).

 

 

처음에는 탈출 조건을  sum == n 으로 했는데 이렇게 하면 탈출이 안 됐다. 문제에서 예시로 든 4의 경우에는 이 조건식을 적용할 수 있지만 이 조건식을 적용할 수 없는 경우가 존재하고, 이 때 무한루프가 발생하는 것이다.

예를 들어  n = 5 라면 계산은 다음과 같이 진행된다.

 

sum = 25

sum = 29

sum = 85

sum = 89

sum = 145

sum = 42

sum = 20

sum = 4

sum = 16

sum = 37

sum = 58

sum = 89

sum = 145

sum = 42

sum = 20

sum = 4

sum = 16

sum = 37

sum = 58

sum = 89

sum = 145

sum = 42

sum = 20

sum = 4

...

 

이 경우

sum = 89

sum = 145

sum = 42

sum = 20

sum = 4

sum = 16

sum = 37

sum = 58

과 같은 과정이 무한히 반복되므로  n 이  89, 145, 42, 20, 4, 16, 37, 58 일 때만

 sum == n 이 탈출 조건으로 쓰일 수 있음을 알 수 있다. 

따라서 탈출 조건이  sum == n 이면 루프를 탈출할 수 없는 경우가 발생해 프로그램이 무한루프를 돌게 된다. 쓰고 보니 뭔가 당연한 얘기를 장황하게 한 것 같다.

 

풀긴 풀었는데 무조건 1 또는 89로 끝난다는 사실을 모르면 탈출 조건을 어떻게 줘야 할 지 모르겠다. 나오는 수들을 다 기록해두고 거기에 포함되어 있으면 탈출하는 식으로 하면 될 것 같긴 한데 시간이 좀 오래 걸리지 않을까 싶다.

 

어쨌든 9999 이하의 행복수는 총 1441개고 이들의 합은 7087069이므로

최종 답은 1441 × 7087069 = 10212466429다.

 

 

 

 * 2021/01/16 

 

앞에서 말한 

 

"풀긴 풀었는데 무조건 1 또는 89로 끝난다는 사실을 모르면 탈출 조건을 어떻게 줘야 할 지 모르겠다. 나오는 수들을 다 기록해두고 거기에 포함되어 있으면 탈출하는 식으로 하면 될 것 같긴 한데 시간이 좀 오래 걸리지 않을까 싶다."

 

를 해봤다.

 

import java.util.Set;
import java.util.HashSet;
 
public class Main {
    public static void main(String args[]) {
      System.out.println(run());
    }
 
    public static String run() {
        long n = 9999 + 1;
        long count1 = 0;
        long count2 = 0;
 
 
        while(--n > 0) {
            String temp = Long.toString(n);
            Set<Integer> set = new HashSet<Integer>(0);
            int sum;
            
            set.clear();
            do {
                sum = 0;
                for(int i = 0;
i < temp.length();
sum += ((temp.charAt(i) - '0')*(temp.charAt(i++) - '0')));
                
                switch(sum) {
                    case 1:
                        ++count1;
                        count2 += ((long)n);
                        break;
                    default:
                        if(set.contains(sum)) {
                            sum = 1;
                        } else {
                            set.add(sum);
                            temp = Long.toString(sum);    
                        }
                }
            } while(sum != 1);
        }
 
        return Long.toString(count1*count2);
    }
}

 

 sum 에 자릿수제곱의 합을 저장하는 것까지는 거의 같다.

 

20행:

새로운 자릿수 제곱의 합들의 집합을 형성하기 위해  set 을 비운다.

 

23행:

 sum 에 (자릿수×자릿수)를 더한다.

 

26행 ~ 29행:

 sum 이  1 이면, 다시말해  n 이 행복수면  count1 은  1 ,  count2 는  n  늘린다.

 

31행 ~ 33행: 

 set 에  sum  값이 포함되어 있으면, 다시 말해 이미 구해진 값이면 while 루프를 탈출하게끔 

 sum 에  1 을 저장한다.

switch 문 말고 if 문을 쓰면  sum = 1  대신  break; 도 쓸 수 있다. switch 문으로 한 건 별 이유는 없고 그냥 해보고 싶어서.

 

33행 ~ 36행:

 set 에  sum  값이 없으면, 다시 말해 처음 구해진 값이면  set 에 그 값을 추가하고 계속 연산을 진행하기 위해  temp 에 문자열로 변환된  sum 을 저장한다.

 

38행:

 sum  값이 1이면 행복수이므로 탈출한다.