[백준/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();
}
}