백준 1323번 JAVA 풀이 - 숫자 연결하기

문제

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

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

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

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

입력

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

출력

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

 

 

# 문제풀이

N을 K로 나눈 나머지에 2를 붙이는 것과 N에 2를 붙여서 K로 나눈 나머지는 동일하다.

예를들어 22를 9로 나눈 나머지는 4이고, 222를 9로 나눈 나머지는 6이다. 

하지만 22를 9로 나눈 나머지 4에 2를 붙여 42를 9로 나눈 나머지 또한 6이다.

같은 나머지가 계속 나올 경우 해당 수는 나누어 떨어질 수 없기 때문에 -1을 출력하면 된다.

 

1. 나머지를 넣을 HashSet을 선언한다.

HashSet<Long> set = new HashSet<>();

 

2. calc은 입력받은 n을 대입해주고 나머지를 계속해서 넣어준다.

이때 calc이 0이 될 경우 나누어 떨어 진 것이기 때문에 반복문을 멈춰주고 그게 아닐 경우 HashSet에 동일한 나머지가 있는지 확인, 있다면 -1을 출력, 없다면  HashSet에 넣고 다시 n을 calc에 이어준다.

answer++;
calc %= k;

if(calc == 0) break;

if(!set.add(calc)){
	System.out.println(-1);
	return;
}

calc = appendNum(calc, n);

 

3. appendNum

나눈 나머지 calc에 입력 값 n을 이어주는 함수이다.

각각 long 형 int 형을 string 형으로 변환한 후 다시 Long 형으로 변환 그 값을 리턴한다.

static long appendNum(long num, int n){
	String temp = Long.toString(num) + Integer.toString(n);
	return Long.parseLong(temp);
}

 

 

# 전체 코드

import java.util.*;
public class Main_1323 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();
        long calc = n;
        int answer = 0;
        HashSet<Long> set = new HashSet<>();

        while(true){
            answer++;
            calc %= k;

            if(calc == 0) break;

            if(!set.add(calc)){
                System.out.println(-1);
                return;
            }
            calc = appendNum(calc, n);
            //System.out.println(calc);
        }
        System.out.println(answer);
    }

    static long appendNum(long num, int n){
        String temp = Long.toString(num) + Integer.toString(n);
        return Long.parseLong(temp);
    }
}