Q 1284 집 주소

💡 문제 요약 및 분석

아래 규칙에 따라 주어지는 숫자의 너비를 계산하면 된다.

- 각 숫자 사이에는 1cm의 여백이 들어가야한다.
- 1은 2cm의 너비를 차지해야한다. 0은 4cm의 너비를 차지해야한다. 나머지 숫자는 모두 3cm의 너비를 차지한다.
- 호수판의 경계와 숫자 사이에는 1cm의 여백이 들어가야한다.

💡 알고리즘 설계

문제에서 제시한 규칙을 바탕으로 아래와 같이 조건문을 만들어보았다. 이번 문제는 숫자가 주어지긴 하지만 문자열로 받는 것이 포인트라는 생각이 들었다. 주어지는 숫자가 연산에 쓰이는 것이 아니고, 오히려 숫자의 자리수나 특징에 따라 더해지는 값이 다르기 때문에 ‘수’ 로서의 특징 보다는 ‘문자’ 로서의 특징을 파악하는 것이 중요하다.

  1. 고정값

    • 양 끝에 1cm + 1cm = 2cm 는 고정값이다.

    • 숫자 사이 1cm = 만약 주어지는 숫자가 3자리수라면 2cm 는 고정값이다.

  2. 변동값

    • 반복문 + 조건문으로 1 = 2cm, 0 = 4cm 로 계산하고, 나머지 숫자는 3cm 로 계산한다.

  3. 주어진 숫자가 0이면 즉시 프로그램을 종료한다.

💡 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        List<String> list = new ArrayList<>();
        while (true) {
            String N = br.readLine();
            if (N.equals("0")) break;
            list.add(N);
        }

        for (int i = 0; i < list.size(); i++) {
            // 1. 양끝 여백을 더함
            int sum = 2;

            // 2. 숫자 사이 여백을 더함
            String num = list.get(i);
            sum += num.length() - 1;

            // 3. 숫자의 너비를 더함
            char[] chars = num.toCharArray();
            for (int j = 0; j < chars.length; j++) {
                if (chars[j] == '1') {
                    sum += 2;
                } else if (chars[j] == '0') {
                    sum += 4;
                } else {
                    sum += 3;
                }
            }
            System.out.println(sum);
        }
    }
}

💡 틀린 부분 수정

💡 시간 복잡도, 공간 복잡도

시간 복잡도공간 복잡도
O(n * m)O(n * m)

  • 입력 개수 (n), 각 숫자의 길이(m)

  • ⏱️ 입력 개수 n 개가 있고, 연산을 n 번 수행하면서 문자열 길이 m 만큼 시간이 소비되므로 최악의 경우 (n * m) 이다.

  • 🧠 입력 개수 n 개를 저장하는 List 공간이 있고, n 의 문자열 m 을 저장하는 char[] 가 있으므로 (n * m) 공간을 차지한다.

💡 다른 풀이

시간 복잡도와 공간 복잡도를 고려하여 최소한의 자원으로 연산하는 풀이가 있어서 가져와봤다. 일단 기존의 내 코드는 1. 숫자를 입력받을 때 List 를 써서 공간복잡도가 증가했고, 2. println 으로 매번 출력하기 때문에 처리 시간이 늘어날수밖에 없었다. 1번 문제는 입력받은 숫자를 따로 저장하지 않고 바로바로 연산으로 처리하면 List 를 쓸 필요가 없을 것이고, 2번 문제는 StringBuilder 로 연산 결과를 모아뒀다가 한번에 출력하도록 만들어주면 된다.

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));
        StringBuilder sb = new StringBuilder();

        while (true) {
            String N = br.readLine();
            if (N.equals("0")) break;
            int sum = N.length() + 1; // 양 끝 여백 + 숫자간 여백 더함

            for (int i = 0; i < N.length(); i++) {
                char num = N.charAt(i);
                if (num == '1') {
                    sum += 2;
                } else if (num == '0') {
                    sum += 4;
                } else {
                    sum += 3;
                }
            }

            sb.append(sum).append("\n");
        }
        System.out.println(sb);
    }
}
시간 복잡도공간 복잡도
O(n * m)O(n)

  • ⏱️ 입력은 n 개 주어진다. 계산은 n 번 수행하면서 문자열의 길이 m 만큼 소비되므로 최악의 경우 (n * m) 시간이 걸린다.

  • 🧠 출력 결과를 저장하는 StringBuilder 가 하나 있으므로 입력되는 n 값에 따라 저장 공간도 증가할 것이다.

💡 느낀점 및 기억할 정보

  • 알고리즘을 설계할 때는 문제풀이 방법뿐만 아니라 코드로 어떻게 구현할 것인지까지 고민하고 작성해야 풀이 시간을 줄일 수 있다.

String 관련 메서드

  • length() : 문자열의 길이를 알 수 있다.

  • charAt() : 문자열을 char로 분리한다.

  • toCharArray() : 문자열을 char 배열로 만든다.

  • Java 에서 문자열은 “쌍따옴표”를 쓰고, 문자는 ‘따옴표’를 쓴다.

StringBuilder

문자열을 효율적으로 조작할 수 있다. (변경, 조작, 삭제) 아래와 같이 쓸 수 있으며, 문자열을 연결할 때 + 연산보다 빠르고 String 과 달리 내부 문자열을 수정할 수도 있다.

StringBuilder sb = new StringBuilder();
sb.append("Hello"); // 문자열 추가
sb.append("\n");
sb.append("World!");
System.out.println(sb.toString()); // 최종 문자열 반환