[알고리즘] 16968번

오늘 풀어볼 문제는 백준 16968번 문제 "로마 숫자 만들기" 이다.

이 문제는 브론즈1 문제이고 브루트 포스 문제이다.

문제

상도시의 차량 번호판 형식이 주어졌을 때, 가능한 차량 번호판의 개수를 구해보자.

번호판에 사용할 수 있는 숫자는 0, 1, 2, ..., 8, 9이다.
사용할 수 있는 문자는 a, b, c, d, ..., y, z이다.
차량 번호판의 형식은 최대 4글자이고, c와 d로 이루어진 문자열로 나타낼 수 있다.
c는 문자가 위치하는 자리, d는 숫자가 위치하는 자리이다.
같은 문자 또는 숫자가 연속해서 2번 나타나면 안 된다.
예를 들어, 형식이 "cd"이면, a1, d4, h5, k4 등이 가능하다. 형식이 "dd"인 경우에 01, 10, 34, 69는 가능하지만, 00, 11, 55, 66은 같은 숫자가 2번 연속해서 불가능하다.

입력

첫째 줄에 차량 번호판의 형식이 주어진다. 형식은 길이가 4보다 작거나 같으며, c와 d로만 이루어져 있다.

출력

첫째 줄에 가능한 차량 번호판의 개수를 출력한다.

📌첫 번째 시도📌

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String st = sc.next();

        int total = 1; // 전체 횟수
        int duplication = 1; // 중복된 횟수
        char pre_index = 'n';

        for(int i = 0; i < st.length(); i++) {
            char now_index = st.charAt(i);
            if (now_index == 'c') { // 인덱스가 c 일 때,
                total = total * 26;
                if(pre_index == now_index) {
                    total = total - duplication;
                }
                duplication = duplication * 26;
            }
            else { // 인덱스가 d 일 때,
                total = total * 10;
                if(pre_index == now_index) {
                    total = total - duplication;
                }
                duplication = duplication * 10;
            }
            pre_index = now_index;
        }
        System.out.println("total = " + total);
    }
}

첫 번째 시도 방향성은 현재 문자와 그 전 문자를 비교하고 같다면 중복 크기의 값을 빼주는 방식으로 알고리즘을 작성했다.
하지만 후.. 틀렸다..🥹
어디가 문제일까..?

내가 확률 통계에 대한 지식이 부족했던 것 같다...
코드는 생각보다 더 간단했다..

📌두 번째 시도📌

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String st = sc.next();

        int total = 1; // 전체 횟수
        char pre_index = 'n'; // 반복문 첫 번째 일 땐, 앞 문자가 없기 때문에 대비용으로 'n'이라고 가정했다.

        for(int i = 0; i < st.length(); i++) {
            char now_index = st.charAt(i);
            if (now_index == 'c') { // 인덱스가 c 일 때,
                if(pre_index == now_index) {
                    total = total * 25;
                }
                else {
                    total = total * 26;
                }
            }
            else { // 인덱스가 d 일 때,
                if(pre_index == now_index) {
                    total = total * 9;
                }
                else {
                    total = total * 10;
                }
            }
            pre_index = now_index;
        }
        System.out.println(total);
    }
}

확률 통계적으로 간단하게 생각했음 됐다.
굳이 duplication이라는 변수를 두지 않고, 만약 현재 문자가 앞 문자와 같다면 상황에 따라 25 나 9를 곱하고 그것이 아니라면 상황에 따라 26 나 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));
        String st = br.readLine();

        int total = 1; // 전체 횟수
        char pre_index = 'n'; // 반복문 첫 번째 일 땐, 앞 문자가 없기 때문에 대비용으로 'n'이라고 가정했다.

        for(int i = 0; i < st.length(); i++) {
            char now_index = st.charAt(i);
            if (now_index == 'c') { // 인덱스가 c 일 때,
                if(pre_index == now_index) {
                    total = total * 25;
                }
                else {
                    total = total * 26;
                }
            }
            else { // 인덱스가 d 일 때,
                if(pre_index == now_index) {
                    total = total * 9;
                }
                else {
                    total = total * 10;
                }
            }
            pre_index = now_index;
        }
        System.out.println(total);
    }
}

자바 BufferedReader를 사용해서 속도를 조금이나마 올렸다.. ㅎㅎ

중간 중간 컴파일 에러와 틀렸습니다는 내가 아직 백준이 익숙하지 않아서.. ㅎㅎ 실수로 코드를 올려서 나온 결과다 ㅎㅎ

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