Q. 3750. Digit sum(D3)

Q. 3750. Digit sum(D3)

 

0. 문제

 

D3 난이도의 문제이고, 구현 문제라고 생각된다.

수 n이 주어지고, n의 각 자리수를 더한다.

다시 그 값이 n이 되고, n이 한 자리가 될 때 까지 이를 반복한다.

주의해야 할 점은 입력값의 범위가 최대 10^18이라는 점 이다.

---

1. 풀이

 

1) 처음 입력이 int 범위를 넘어설 가능성이 있으므로 char 배열로 입력을 받았다.

2) 이후에 입력값의 길이를 검사해서 만약 한 자리의 입력일 경우 그냥 이를 출력하고,

한 자리 이상인 경우 모든 자리의 수를 더한 값을 int로 저장했다.3) 위에서 int로 저장한 값이 한 자리 이하일 때 까지 이를 반복했다.

 

풀이 코드는 아래와 같다

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
 
    static BufferedReader br;
    static StringBuffer sb = new StringBuffer();
    static StringTokenizer st;
     
    static char[] N;
    static int intN;
     
     
    static void input() throws IOException {
        N = br.readLine().toCharArray();
        intN = 0;
    }
     
    static void pro(int tc) throws Exception{
         
        if (N.length == 1) {
            intN = N[0] - '0';
        } else {
            for (int i = 0; i < N.length; i++) intN += N[i] - '0';
             
            while (intN > 9) {
                 
                int n = intN;
                int res = 0;
                while (n != 0) {
                    res += n % 10;
                    n /= 10;
                }
                intN = res;
            }
     
        }
        sb.append(String.format("#%d %d\n", tc, intN));
    }
     
    public static void main(String[] args) throws Exception{
         
        br = new BufferedReader(new InputStreamReader(System.in));
//      br = new BufferedReader(new InputStreamReader(new FileInputStream("res/input.txt")));
         
        int T = Integer.parseInt(br.readLine());
        for(int tc = 1; tc <= T; tc++) {
            input();
            pro(tc);
        }
        System.out.println(sb);
         
    }
 
}

---

2. 시간복잡도 계산

 

N의 최대 길이는 18이고, 최대 값은 9가 18번 나온 값 이다.

그리고 이 경우에도 모든 자리수를 더하면 9 * 18 = 162

한번 더 로직을 돌면 9로 3번만에 연산의 결과가 나온다.

따라서 모든 입력값에 대해 1초 이내에 풀 수 있다.