[백준] 1 - 4375(with.Java)

💡문제 분석 요약

-- 문제 --

2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 각 자릿수가 모두 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.

입력 : 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.

출력 : 각 자릿수가 모두 1로만 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.

💡알고리즘 설계

1. n을 BufferedReader로 입력받은 후 1부터 시작해서 n으로 나누기

2. 1다음은 11

3. cnt이용해서 자리수 세기 1→1, 11→2

💡코드

package backjoon;

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

public class BackJoon4375 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n;
        long oneNumber,cnt;
        while (br.readLine()!=null) {
            n = Integer.parseInt(br.readLine());
            oneNumber=1;
            cnt=1;
            while (true) {
                if (oneNumber % n == 0) {
                    System.out.println(cnt);
                    break;
                }
                else{
                    oneNumber=(oneNumber*10)+1;
                    cnt++;
                }
            }
        }
    }
}

💡시간복잡도

O(N*N)

💡틀린 이유

시간 초과 : long은 19자리, 1,11,111…..늘어나면서 20자리 넘어가면 오버플로우(자료형이 저장할 수 있는 최대값 초과)

💡틀린 부분 수정 or 다른 풀이

package backjoon;

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

public class BackJoon4375 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n;
        long oneNumber,cnt;
        while (br.readLine()!=null) {
            n = Integer.parseInt(br.readLine());
            oneNumber=1;
            cnt=1;
            while (true) {
                if (oneNumber % n == 0) {
                    System.out.println(cnt);
                    break;
                }
                else{
                    oneNumber=(oneNumber*10)+1;
                    oneNumber %= n; //여기서 미리 첫번째 나누기 힌거라 생각  111%7=41->6 41은 전 값이었네!
                    cnt++;
                }
            }
        }
    }
}

💡느낀점 or 기억 할 정보

1. 질문 : 1, 11, 111, 1111 …. 이렇게 숫자가 커지는데 마침 % 연산이네 ? → 모듈러 연산 써야지 ? 생각하면 되나??