[백준]#1323 숫자 연결하기

문제

영훈이는 태형이에게 어떤 수 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

풀이

이 문제는 모듈러 연산에 대해 조금 찾아본다면 풀 수 있는 문제였다. 2에 2를 쓴 수인 22를 k로 나눈 나머지와 2를 k로 나눈 나머지에 2를 쓴 수를 k로 나눈 나머지는 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        StringBuilder sb = new StringBuilder();
        HashSet<Long> set = new HashSet<>();    //나온 나머지 체크
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);
        long num = N;
        int cnt = 0;

        while(true) {
            cnt++;
            long remain = num%K;
            if(remain==0) break;

            if(!set.add(remain)) {    //같은 나머지가 나오면 반복 되기때문에 루프 탈출
               System.out.println(-1);
               return;
            }

            sb.append(remain).append(N);
            num = Long.parseLong(sb.toString());
            sb.delete(0, sb.length());
        }

        System.out.println(cnt);
    }
}