1748번 수 이어 쓰기 1

문제

---

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

코드

---

최초 풀이

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

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 count = 0;

        if (1 <= N && N < 10) {
            count = N;
        } else if (10 <= N && N < 100) {
            count = 9 + (N - 9) * 2;
        } else if (100 <= N && N < 1000) {
            count = 9 + (90 * 2) + (N - 99) * 3;
        } else if (1000 <= N && N < 10000) {
            count = 9 + (90 * 2) + (900 * 3) + (N - 999) * 4;
        } else if (10000 <= N && N < 100000) {
            count = 9 + (90 * 2) + (900 * 3) + (9000 * 4) + (N - 9999) * 5;
        }else if (100000 <= N && N < 1000000) {
            count = 9 + (90 * 2) + (900 * 3) + (9000 * 4) + (90000 * 5) + (N - 99999) * 6;
        } else if (1000000 <= N && N < 10000000) {
            count = 9 + (90 * 2) + (900 * 3) + (9000 * 4) + (90000 * 5) + (900000 * 6) + (N - 999999) * 7;
        } else if (10000000 <= N && N < 100000000) {
            count = 9 + (90 * 2) + (900 * 3) + (9000 * 4) + (90000 * 5) + (900000 * 6) + (9000000 * 7) + (N - 9999999) * 8;
        }else{
            count = 9 + (90 * 2) + (900 * 3) + (9000 * 4) + (90000 * 5) + (900000 * 6) + (9000000 * 7) + (90000000 * 8) + (N - 99999999) * 9;
        }

        System.out.println(count);
    }
}

최종 풀이

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

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 count = 0;
        for (int i = 1; i <= N; i *= 10) {
            count += N - i + 1;
        }

        System.out.println(count);
    }
}

풀이 방법

---

• 위 문제의 경우, 시간 제한이 0.15초이기 때문에 N에 대해서 O(N)의 시간복잡도이면 시간초과가 걸리고 만다.

• 따라서 O(N)을 만들지 않을 방법으로 규칙을 찾아서 최초 풀이를 도출했다.

• 10의 자리라면 10~99까지가 자리수가 2개, 100~999까지가 자리수 3개, 이런식으로 접근하였었다.

• 하지만 막상 규칙을 찾고나서 코드로 일반화하는 것에 어려움을 느끼고, 다른 코드를 찾아보았다.

• 그 코드가 최종 풀이이다.

• 인덱스를 10씩 곱하면서 for문을 수행한다.

• count += N - i + 1; 이 코드는 자리수 별로 숫자가 몇개인지 판단한다.

  💡

  N이 120이라고 가정해보자.

  • 최초에 i는 1이 될것이다. 따라서 120 - 1 + 1 = 120 이 된다. 이 말은 1의 자리 숫자는 120개가 포함된다는 의미이다.

  • 그 다음에는 i는 10이 된다. 따라서 120 - 10 + 1 = 111 이 된다. 이 말은 10의 자리 숫자는 111개가 포함된다는 뜻이다. 1~9는 1의 자리수이고 10~120은 10의 자리수를 포함하고 있다. 따라서 120에서 1~9까지를 빼면 111이 된다.

  • i = 100이면 120 - 100 + 1 = 21 이 된다. 마찬가지로 120까지의 숫자중에 세자리 수는 100~120까지이다. 따라서 120(전체 숫자) - 99(1~99까지의 숫자)를 구하면 21이 나온다.

핵심 포인트

---

• 시간 제한을 보고 O(N)으로 해결되지 않는다는 것을 캐치할 수 있어야 한다.

• for문을 좀 더 자유롭게 사용할 줄 알아야 한다. (i++말고)

• 규칙을 찾을 수 있어야 한다.

보완할 점 / 느낀 점

---

• 처음에 규칙을 찾았으나, 일반화 시키기 매우 어려워서 노가다로 일일이 분기를 걸어줬었다. 수행시간도 준수하긴 하였으나, 다른 방법이 있을 것 같아 자료를 찾아봤다.

• 다른 코드를 보니, 규칙성을 코드로 잘 구현하고 있었다. 하지만 초반에 이해를 하는데 다소 시간이 걸렸다.

• 규칙 찾는 연습을 더 해야될 것 같다.

참고자료

---

• https://iridescent-zeal.tistory.com/83