[프로그래머스] [PCCP 기출문제] 4번 / 수식 복원하기

문제 설명

• https://school.programmers.co.kr/learn/courses/30/lessons/340210
• LV3
• 풀이시간 : 55분

문제 풀이

• 생소한 진법 문제였다. 알고리즘에 try, catch는 처음 쓰는듯..
• 우선 2~9진법의 타당성 여부를 저장하기 위한 배열을 둔다.
• 각 표현식에 대해서 아래와 같이 validation을 진행한다.

  1. 각 숫자가 n진법 -> 10진법 변환이 불가능하다면 bools[n] = false로 바꿔줌
  2. 변환된 10진법 수의 연산 결과가 틀리다면 bools[n] = false로 바꿔줌

• 주의할 점은 'X'가 포함된 표현식도 변환을 통한 validation을 해줘야 한다는 점.
• 이후 valid한 진법들의 연산 결과가 모두 같다면 해당 수를 넣고 다르다면 '?'로 치환해서 결과 배열에 넣어줌

소스 코드 (JAVA)

import java.util.*;
class Solution {

    boolean[] bools = new boolean[10];

    // 해당 표현식이 어떤 진법에 맞는지 여부 판별 -> bools 업데이트
    void validate(String expr) {

        StringTokenizer st = new StringTokenizer(expr);
        String A = st.nextToken();
        String command = st.nextToken();
        String B = st.nextToken();
        st.nextToken();
        String C = st.nextToken();

        for (int i = 2; i <= 9; i++) {
            int convA = 0, convB = 0, convC = 0;
            try {
                convA = Integer.parseInt(A, i);
                convB = Integer.parseInt(B, i);
                if (!"X".equals(C)) convC = Integer.parseInt(C, i);
            } catch (NumberFormatException e) {
                bools[i] = false;
                continue;
            }
            if ("X".equals(C)) continue;
            if ("+".equals(command)) {
                if (convA + convB != convC)
                    bools[i] = false;
            } else {
                if (convA - convB != convC)
                    bools[i] = false;
            }
        }
    }

    // 진법 범위에 따른 표현식 완성
    String convert(String expr) {
        // 문제 아닌 문자열 건너뜀
        if (expr.charAt(expr.length() - 1) != 'X') return null;

        StringTokenizer st = new StringTokenizer(expr);
        String A = st.nextToken();
        String command = st.nextToken();
        String B = st.nextToken();
        st.nextToken();
        st.nextToken();

        String res = "";
        for (int i = 2; i <= 9; i++) {
            if ("?".equals(res)) break;
            if (!bools[i]) continue;

            int convA = 0, convB = 0;
            try {
                convA = Integer.parseInt(A, i);
                convB = Integer.parseInt(B, i);
            } catch (NumberFormatException e) {
                continue;
            }
            if ("+".equals(command)) {
                String convC = Integer.toString(convA + convB, i);
                if ("".equals(res)) res = convC;
                else if (!res.equals(convC)) res = "?";
            } else {
                String convC = Integer.toString(convA - convB, i);
                if ("".equals(res)) res = convC;
                else if (!res.equals(convC)) res = "?";
            }
        }

        return A + " " + command + " " + B + " = " + res;
    }

    public String[] solution(String[] expressions) {
        ArrayList<String> result = new ArrayList<>();
        Arrays.fill(bools, true);

        int ind = 0;
        // 1. 어떤 진법이 맞는지 여부 판별
        for (String str : expressions) {
            validate(str);
        }
        // 2. 특정 진법 범위에 따른 결과 출력
        for (String str : expressions) {
            String res = convert(str);
            if (res != null) result.add(res);
        }
        return result.toArray(new String[0]);
    }
}

/**
 * [PCCP 기출문제] 4번 / 수식 복원하기 (20:45)
 *
 * - expressions (2 <= 길이 <= 100)
 * - 더하기 혹은 뺄셈으로 구성되어 있음 (A + B = C)
 * - A, B -> 두자릿수 이하 정수
 * - C -> 음이아닌 세자릿수 이하 정수, X라고 표시될 수 있음, 여러번
 * - 음수나 모순되는 수식은 주어지지 않음
 * - 2~9진법 중 하나임
 * - 정답 진법 범위 내에서 표현되는 식이라면 값을 채워넣고 아니라면 ?로 채워 넣음
 *
 */