Q 2037 문자메시지

💡 문제 요약 및 분석

문제를 이해하는 것 부터가 쉽지 않았다..

버튼을 한 번 누를 때 p초가 걸린다. (공백도 마찬가지임)
같은 숫자인 문자를 연속으로 누를 때 w초가 걸린다. 이 경우 버튼을 누르는 시간 p초가 더해진다. (p + w)

💡 알고리즘 설계

입력
- StringTokenizer
- int p, int w
- String msg
연산 (예상 시간 복잡도 : O(msg))
- msg 를 for 문으로 돌면서 char 하나씩 분리한다.
- if 문으로 버튼 맨 앞 문자(A,D,G,J,M,P,T,W) 및 공백인 경우 p 초를 누적합한다.
- 그 외의 경우는 p + w 초를 누적합한다.
출력
- 누적합을 한 번만 출력한다.

💡 코드

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

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

        String time = br.readLine();
        String msg = br.readLine();
        StringTokenizer timeTokens = new StringTokenizer(time);
        int p = Integer.parseInt(timeTokens.nextToken());
        int w = Integer.parseInt(timeTokens.nextToken());
        br.close();

        int sum = 0;
        for (int i = 0; i < msg.length(); i++) {
            char button = msg.charAt(i);
            if (button == 65 || button == 68 || button == 71 || button == 74 || button == 77
                    || button == 80 || button == 84 || button == 87 || button == 32) {
                sum += p;
            } else {
                sum += p + w;
            }
        }
        System.out.println(sum);
    }
}

💡 틀린 부분 분석

문제에서 공백을 연속으로 누를 때는 기다릴 필요가 없다는 부분을 놓쳤다. StringTokenizer 는 연속된 공백은 하나의 구분자로 처리하므로 토큰이 몇 개인지 세고 공백을 계산하는 방식으로 바꿨다.
그럼에도 틀렸다. 다른 사람의 답지를 보니 내가 문제 이해를 잘못했다는 것을 깨달았다. 숫자를 연속해서 입력하는 경우, w초의 대기시간 + 버튼을 누른 횟수 * p 를 해줘야 한다. 나는 이 부분에서 무조건 p + w 로 처리했기 때문에 실패한 것이다. 추가로, A(공백)C 를 입력한다고 가정했을 때는 C 는 대기시간이 필요 없다고 한다. 대기 시간이 들어가는 경우는 AC 처럼 같은 버튼을 연속해서 눌러야 할 때 구분점을 두기 위해 있는 룰인 것 같다.
고쳤는데도 틀려서 다시 확인했는데, 공백을 연속해서 누를 때 기다리지 않아도 된다고 해서 공백이 여러 번 들어가면 P초 한 번만 누르고 마는 건줄 알았는데 아니었다. 버튼을 누르긴 눌렀으니 누른만큼 누적합해야한다…

💡 알고리즘 재설계 및 정답 코드

입력
- StringTokenizer
- int p, int w
- String msg
- 이차원 배열
연산
- 입력된 문자열을 공백으로 나눈다. (공백 입력시간 계산)
- prevGroup 변수로 연속된 그룹의 문자일 경우 대기시간 w 초를 더한다.
- 이차원 배열에서 i = 그룹, j = 버튼을 누르는 횟수 가 된다.
출력
- 누적합을 한 번만 출력한다.

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

public class Main {

    static char[][] dial = {
            {'A','B','C'}, {'D','E','F'}, {'G','H','I'},
            {'J','K','L'}, {'M','N','O'}, {'P','Q','R','S'},
            {'T','U','V'}, {'W','X','Y','Z'}
    };

    static int prevGroup = -1;

    public static int cal(char c, int p, int w) {
        int sum = 0;
        for (int i = 0; i < dial.length; i++) {
            for (int j = 0; j < dial[i].length; j++) {
                if (dial[i][j] == c) {
                    if (prevGroup == i) sum += w;
                    sum += (j + 1) * p;
                    prevGroup = i;
                    return sum;
                }
            }
        }
        return 0;
    }

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

        String time = br.readLine();
        String msg = br.readLine();
        StringTokenizer timeTokens = new StringTokenizer(time);
        int p = Integer.parseInt(timeTokens.nextToken());
        int w = Integer.parseInt(timeTokens.nextToken());
        br.close();

        int sum = 0;
        for (int i = 0; i < msg.length(); i++) {
            char c = msg.charAt(i);
            if (c == ' ') {
                sum += p;
                prevGroup = -1;
                continue;
            }
            sum += cal(c, p, w);
        }
        System.out.println(sum);
    }

}

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

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

⏱️ main 에서 for 반복문은 들어오는 문자열 개수 n 만큼 시간을 소비하고, cal 함수는 char 배열을 순회하는데, 이 때 char 배열은 정해진 값이므로 O(1) 만큼 시간을 소비한다. 따라서 O(n) 이다.
🧠 입력 문자열과 배열, 기타 변수 등이 있는데, 문자열은 n 만큼 공간을 차지할 것이고, 나머지는 상수이므로 O(1) 차지한다.

💡 느낀점 및 기억할 정보

코딩보다 문제를 이해하는게 더 힘들었다 ㅜㅜ 계속 잘못된 이해를 바탕으로 코드를 짰으니 통과할 수 있을 리 없었다. 문제를 정확히 이해하고 넘어갈 것 !! 기본 중의 기본이다.