[백준 *Java] - 수 이어 쓰기 1 (1748)

 

수 이어 쓰기1

1748번: 수 이어 쓰기 1

문제 설명
1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.
1234567891011121314151617181920212223...
이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다.

출력
첫째 줄에 새로운 수의 자릿수를 출력한다.

---

👇  접근방식 (내 생각 정리)

문제를 이해하고, for문 하나로 돌면서 넣어주고 길이를 카운트 해주면 된다고 생각을 했습니다.

하지만, 이 문제가 간단한 걸로 봐서는 시간초과나 메모리초과에 이슈가 있을 거라 생각 들었습니다

먼저, 처음 드는 생각을 가지고 코드를 한 번 짜보고 실패하면 다른 로직을 생각해보겠습니다.

---

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            sb.append(i);
        }
        System.out.println(sb.length());
    }
}

... 역시나 위 코드는 실패했습니다.

메모리 초과 오류

최대 값은 1억이라는 수입니다. 분명 1억이라는 수를 계속 스트링빌더에 담아주면 담긴 공간이 초과하게 될것입니다.....

 

역시 1분만에 끝나는 문제가 아니였습니다...

다시 생각을 해봅시다!

그래도 규칙이라는 게 있어서 쉽게 접근할 수 있었습니다.

0~ 9까지 길이는 1

10~99까지 길이는 2

100~999까지 길이는 3

1000~ 9999까지 길이는 4

.....

이런 규칙이있습니다.

for문은 1억번 돌 되, 해당 값을 담는 게 아니라, 길이를 카운트로 바로 +연산처리를 하여 다시 코드를 짜보겠습니다.

 

실패 코드입니다. 하.. 이번에는 IDE 에서는 메모리를 감당하지만, 백준에서 메모리 초과로 틀렸다고 떴습니다.

아래 코드는 전 자릿수와 현 자릿수가 루프 돌 때 변화가 생길 때, ++ 해주는 방식으로 갔지만 메모리를 잡아 먹었던 거 같습니다.

아마 메모리 문제가 아니더라도 시간 초과가 떴을 거 같습니다. IDE에서도 생각보다 체감상 1초가 넘어가더라구요..

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int lengthCnt = 1;
        int result = 0;

        for (int i = 1; i <= N; i++) {
            if (String.valueOf(i).length() > String.valueOf(i-1).length())
                lengthCnt++;
            result += lengthCnt;
        }
        System.out.println(result);

    }
}

 

 

다시 다른 방법으로 풀어보겠습니다.

계속해서 10 -> 100 -> 1000 이 방법을 어떻게 if 조건으로 걸러주어야할까? 라는 생각을 갖다가

그냥 *10을 해주면 된다는 생각을 했습니다. 이 생각이 왜 이리 안났을까요..

 

결국 통과했습니다. 아래 코드는 성공한 코드입니다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int lengthCnt = 1;
        int result = 0;
        int breakPoint = 10; 
        for (int i = 1; i <= N; i++) {
            //if (String.valueOf(i).length() > String.valueOf(i-1).length()) lengthCnt++;
            if (i == breakPoint) {
                breakPoint = breakPoint * 10;
                lengthCnt++;
            }
            result += lengthCnt;
        }
        System.out.println(result);

    }
}