[백준/JAVA] 1323 : 숫자 연결하기

계속 틀린건 비밀임

10달 전부터 시도했지만, 도저히 풀리지 않아서 냅두었다.

처음 문제를 보고 정말 쉬워보였다.. 하지만 풀면 풀수록 타입은 어떻게 정해야 하는지, 나눗셈의 또 다른 공식은 없는지 등에 대한 여러가지 문제점들이 있었다. 가장 먼저 파악한 것은 나눗셈의 공식이었다. 자세한 공식은 코드에서 다루어보도록 하겠다. 나눗셈의 공식에 대해 이해를 하게 되어 그것을 처음에는 숫자로 구현하였다. 

int temp = n;
for(int i = 0; i < 9; i++) {
	if(temp % k != 0) {
		temp = temp % k;
		temp = temp * pow + n;
	} else {
		break;
	}
	count++;
}

대충 이런식이었다. 여기서 잘못된 점은, temp의 설정을 int형식으로 하여 더 긴 숫자에 대해서는 받지 못하게 되어있었다. n이 10억보다 작거나 같은 수라고 생각하게 되어 int형식으로도 충분하다고 생각했는데, 보니 그 숫자 뒤에 숫자를 더 붙일 수 있도록 설계를 해두고, int로 설정한 내 잘못이었다.

두번째로는 for구문을 9까지만 설정한 것이다. k가 당연하게 10까지라고 생각했나보다. 나머지는 9까지만 나오는줄 알고 착각하고 알고리즘을 설계했다. 왜 틀린지 몰라 계속 고민하던 나에게 다른 알고리즘 정답을 본 것은 채찍질을 할 수 있도록 도와주었다. 맨날 난 내가 짱이라고 생각한다. 

결국 StringBuilder를 활용하여 append를 통해 뒤에 연결시키고, Long.parseLong을 통해 다시 타입을 변환하는 식으로 하여 문제를 풀어나갔다.

숫자 연결하기 성공

시간제한	메모리제한	제출	정답	맞힌사람	정답비율
2 초	128 MB	1279	247	171	23.916%

문제

영훈이는 태형이에게 어떤 수 N과 K를 주었다.

태형이는 N을 종이에 쓰기 시작했다. 태형이는 자신이 이 수를 몇 번 써야 그 수가 K로 나누어지는지 궁금해지기 시작했다.

N=10일 때, 이 수를 한 번 쓰면 10이고, 두 번 쓰면 1010이고, 세 번쓰면 101010이고,... 이런식이다.

어떤 수 N과 K가 주어졌을 때, N을 몇 번 써야 K로 나누어 떨어지는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. K는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 몇 번 써야하는지 그 최솟값을 출력한다. 만약 아무리 써도 불가능할 경우에는 -1을 출력한다.

예제 입력 1

2 9

예제 출력 1

9

 

문제 해답

import java.util.*;
import java.io.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();
        
        /* set은 중복이 되지 않는다는 장점이 있었다. 즉, 값을 나누고 나서의 나머지를 추가시키고,
         * 다시 그 값이 중복되어서 나왔을 때에 종료시킨다. 나머지가 다시 나온다는 것은
         * 앞으로도 계속 순환되며 나누어지지 않을 수라는 것을 의미한다. */
        Set<Long> set = new HashSet<Long>();
        int count = 0;
        
        /* 계속해서 나머지를 앞에 연결시킬 수이다. */
        long temp = n;
        while(true) {
        	count++;
            
            /* 나누어 지면 종료 */
        	if(temp % k == 0) break;
            
            /* set에 추가시키면서 동시에 if구문 안에 넣어 add가 되었는지 확인한다.
            * add가 되지 않았다면 나머지가 이미 set안에 존재하는 것이므로 종료시킨다. */
        	if(!set.add(temp % k)) {
        		System.out.println(-1);
        		return;
        	}
            
            /* 2를 9로 나눈다고 생각하면
             * 2 % 9 = 2
             * 22 % 9 = 4
             * 222 % 9 = 6
             * 즉, 2라는 숫자가 겹쳐서 계속 나오는 것이고, 앞에서 미리 나머지를 구해놓았기 때문에
             * 계속해서 늘어나는 숫자에 대해 나눗셈을 시킬 필요가 없다.
             * 위의 식을 다음과 같이 바꿀 수도 있다.
             * 2 % 9 = 2 (2의 숫자가 다음 식의 앞으로 간다.)
             * 22 % 9 = 4 (4의 숫자가 다음 식의 앞으로 간다.)
             * 42 % 9 = 6 (앞으로도 쭉.)
             */
        	sb.append(temp % k).append(n);
            temp = Long.parseLong(sb.toString());
            sb.delete(0, sb.length());

        }
        System.out.println(count);
        br.close();
    }
}