[백준 4375] 1 - Java

백준을 풀다가 오랜만에 너무 안 풀렸던 문제가 있어 해결과정을 기록해두려 한다.

문제 내용은 다음과 같다.

 

문제 링크

https://www.acmicpc.net/problem/4375

 

 

 

처음에는 문제의 출력 내용 자체부터 이해하지 못했다.

1로 이루어진 n의 배수..?

 

알고 보니 n의 배수 중 (전체 자릿수가 1로만 이루어진 수 중에) 가장 작은 배수를 출력하는 것으로 

n이 1 -> 11 -> 111 -> 1111과 같이 1로만 이루어진 수에 나누어 떨어졌을 때 자릿수의 개수를 출력하는 것이었다.

 

이 뜻을 이해하고 나서 구현 자체는 매우 쉽다고 생각했다.

(무수한 시간초과가 나타나기 전까지는..)

 

 

다음은 정답 전에 제출했던 코드이다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String num;
		while ((num = br.readLine()) != null) {
			try {
				long numL = Long.parseLong(num);
				for (long i = 1; ; i = i * 10 + 1) {
					if (i % numL == 0) {
						String answer = "";
						answer += i;
						bw.write(answer.length() + "\n");
						break;
					}
				}
				bw.flush();
			} catch (NumberFormatException e) {
				break;
			}
		}
	}
}

 

 

간단하게 코드 풀이를 해보자면, 일단 숫자의 입출력을 위해 BufferedReader와 BufferedWriter를 사용했다.

Scanner를 사용하지 않은 이유는 이 전에 시간 초과가 났기 때문인데 문제를 풀고 다른 답을 확인해 본 결과 Scanner를

사용하신 분들도 있어서 Scanner과 시간초과와는 무관할 것 같다.

 

다음으로 본인이 직접 입력의 테스트 케이스 수를 정하는 것이 아니라 입력 수가 정해져있기 때문에 while 반복문 내에

입력값이 null 값이면 코드를 수행하지 않도록 했다.

 

while 반복문 내에서는 for 반복문을 통해 수의 계산 후 결과를 비교했다.

각 자릿수가 1로만 이루어진 수를 입력값으로 나눴을 때 나누어 떨어져야 했기 때문에

i의 값을 i * 10 + 1 씩 증가하게 만들어 나머지가 0이 되었을 때 값을 반환하도록 했다.

 

 

모든 구현이 끝나고 테스트 예제는 모두 통과했지만 시간초과 오류가 발생했다.

 

 

 

무슨 이유인지 몇번이나 수정하고 제출했지만 결과는 같았다..

그 후 계속 문제를 풀어보다 시간 초과의 오류는 for문 내의 계산식 때문이라 생각되어 다음과 같이 코드를 수정했다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String num;
		while ((num = br.readLine()) != null) {
			try {
				long numL = Long.parseLong(num);
				long i = 1;
				int cnt = 1;
				while(i%numL!=0) {
					i = (i * 10 + 1) % numL;
					cnt++;
				}
				bw.write(String.valueOf(cnt)+"\n");
				bw.flush();
			} catch (NumberFormatException e) {
				break;
			}
		}
	}
}

 

 

반복문 내의 계산식 변화를 살펴보면

기존에는 i = i * 10 + 1 식을 통해 i의 값을 1 -> 11 -> 111..로 증가시킨 후 if문을 통해 나누어 떨어지는지 비교했지만

i = ((i * 10 + 1) % 입력값)으로 바꾸면서 i의 값을 증가시킨 후 바로 입력값으로 나눈 나머지 값을 대입시켰다.

 

예시로 numL 값이 3 일 때

i = 1  ->  11 % 3  ->  i = 2, cnt = 2

i = 2  ->  21 % 3  ->  i = 0, cnt = 3 ... 으로 i가 0이 되어 while문을 빠져나와 종료가 된다.

 

약간 헷갈릴 수도 있는데 처음 구현했던 (for문 증감식 + if문 비교)를 합쳐서

불필요한 코드 및 계산을 줄였다고 보면 될 거 같다..