[프로그래머스 JAVA] 수식 복원하기

https://school.programmers.co.kr/learn/courses/30/lessons/340210

프로그래머스

 

---

 

문제 접근 방법

 

 

특별히 떠오르는 알고리즘은 없었다.

 

문제에서 제시한 힌트와 비슷한 방식으로도 풀이해봤고, 조금 더 최적화해서 진행해보기도 했지만 실행결과는 비슷해서 아쉬웠다.

 

---

풀이 방법 (2가지)

 

1. 문제 설명대로 풀어본 코드

 

문제에서 제시한 힌트는 아래와 같다.

 

가능한 STRAT진수 ~ END진수 를 체크해보고, 그 결과들이 다르다면 ?를 출력하고 결과가 같다면 풀이 가능한 문제로 표현하는 것이다.

 

결과들이 다른 것은 Set의 길이로 구분했다.

 

코드

package programmers;

import java.util.*;

public class 수식복원하기 {

    public static void main(String[] args) {

        String[] expressions = {"10 - 2 = X", "30 + 31 = 101", "3 + 3 = X", "33 + 33 = X"};
        String[] solution = solution(expressions);

        for (String expr : solution) {
            System.out.println(expr);  // 결과 출력
        }

    }

    public static String[] solution(String[] expressions) {
        List<String> answerList = new ArrayList<>();     // 결과를 저장할 리스트
        List<Integer> possibleBases = new ArrayList<>(); // 가능한 진법들을 저장할 리스트

        // 1. 가능한 진법 찾기
        for (int base = 2; base <= 9; base++) {
            boolean validBase = true;  // 현재 진법이 유효한지 여부를 나타내는 변수

            for (String expression : expressions) {
                String[] tokens = expression.split(" ");

                String A = tokens[0];           // 첫 번째 피연산자
                String operator = tokens[1];    // 연산자 (+ 또는 -)
                String B = tokens[2];           // 두 번째 피연산자
                String equalsSign = tokens[3];  // 등호 (=)
                String C = tokens[4];           // 결과 값 또는 'X'

                // 숫자들이 해당 진법에서 유효한지 확인
                if (!isValidNumber(A, base) || !isValidNumber(B, base)) {
                    validBase = false;
                    break;  // 유효하지 않으면 더 이상 검사할 필요 없음
                }

                // 결과 값이 'X'가 아닌 경우 계산 검증
                if (!C.equals("X")) {
                    if (!isValidNumber(C, base)) {
                        validBase = false;
                        break;
                    }

                    // 해당 진법에서 숫자를 정수로 변환
                    int operand1 = Integer.parseInt(A, base);
                    int operand2 = Integer.parseInt(B, base);
                    int result = Integer.parseInt(C, base);

                    int computedResult;
                    if (operator.equals("+")) {
                        computedResult = operand1 + operand2;  // 덧셈 계산
                    } else if (operator.equals("-")) {
                        computedResult = operand1 - operand2;  // 뺄셈 계산
                        if (computedResult < 0) {
                            validBase = false;  // 결과가 음수이면 유효하지 않음
                            break;
                        }
                    } else {
                        validBase = false;  // 지원하지 않는 연산자
                        break;
                    }

                    // 계산 결과가 실제 결과와 일치하는지 확인
                    if (computedResult != result) {
                        validBase = false;
                        break;
                    }
                }
            }

            // 유효한 진법이면 리스트에 추가
            if (validBase) {
                possibleBases.add(base);
            }
        }

        // 2. 결과 값 채우기
        for (int i = 0; i < expressions.length; i++) {
            String expression = expressions[i];
            String[] tokens = expression.split(" ");

            String A = tokens[0];           // 첫 번째 피연산자
            String operator = tokens[1];    // 연산자
            String B = tokens[2];           // 두 번째 피연산자
            String equalsSign = tokens[3];  // 등호
            String C = tokens[4];           // 결과 값 또는 'X'

            if (C.equals("X")) {
                Set<String> possibleResults = new HashSet<>();  // 가능한 결과 값들을 저장할 집합

                // 가능한 진법들에 대해 결과를 계산
                for (int base : possibleBases) {
                    // 해당 진법에서 숫자들이 유효한지 확인
                    if (!isValidNumber(A, base) || !isValidNumber(B, base)) {
                        continue;
                    }

                    int operand1 = Integer.parseInt(A, base);  // 첫 번째 피연산자 변환
                    int operand2 = Integer.parseInt(B, base);  // 두 번째 피연산자 변환

                    int computedResult;
                    if (operator.equals("+")) {
                        computedResult = operand1 + operand2;  // 덧셈 계산
                    } else if (operator.equals("-")) {
                        computedResult = operand1 - operand2;  // 뺄셈 계산
                        if (computedResult < 0) {
                            continue;  // 결과가 음수이면 스킵
                        }
                    } else {
                        continue;  // 지원하지 않는 연산자
                    }

                    // 계산된 결과를 해당 진법의 문자열로 변환
                    String resultStr = Integer.toString(computedResult, base).toUpperCase();

                    // 결과가 해당 진법에서 유효한지 확인
                    if (!isValidNumber(resultStr, base)) {
                        continue;
                    }

                    possibleResults.add(resultStr);  // 가능한 결과 값 추가
                }

                if (possibleResults.size() == 1) {
                    // 가능한 결과가 하나이면 결과를 채워 넣음
                    String resultValue = possibleResults.iterator().next();
                    String filledExpression = A + " " + operator + " " + B + " = " + resultValue;
                    answerList.add(filledExpression);
                } else {
                    // 여러 결과가 가능하면 '?'로 표시
                    String filledExpression = A + " " + operator + " " + B + " = ?";
                    answerList.add(filledExpression);
                }
            }
        }

        return answerList.toArray(new String[0]);  // 결과를 배열로 변환하여 반환
    }

    // 숫자가 해당 진법에서 유효한지 확인하는 함수
    static boolean isValidNumber(String numStr, int base) {
        for (int i = 0; i < numStr.length(); i++) {
            char c = numStr.charAt(i);
            if (c < '0' || c > '9') {
                return false;  // 숫자가 아닌 문자가 포함된 경우
            }
            int digit = c - '0';
            if (digit >= base) {
                return false;  // 자릿수가 진법보다 크거나 같은 경우
            }
        }
        return true;  // 모든 자릿수가 해당 진법에서 유효한 경우
    }
}

 

---

2. 입력값에서 진수를 확정짓는 코드

 

올림이나 빌림에서 N진수를 확정짓는 방법을 추가하고, 추론 과정을 조금 더 직관적으로 변경해봤다.

 

코드

package programmers;

import java.util.Arrays;

public class 수식복원하기_2 {

    public static void main(String[] args) {

        String[] expressions = {
                "1 + 5 = 10",
                "23 + 12 = X",
                "55 + 31 = X",  // 올림 발생 (Carry occurs)
                "52 - 11 = X",
                "53 - 24 = X"   // 빌림 발생 (Borrow occurs)
        };
        String[] solution = solution(expressions);

        System.out.println(confirmedBase);  // 확정된 진수 출력

        for (String expr : solution) {
            System.out.println(expr);  // 결과 출력
        }

    }

    static int estimatedMinimumBase = 2;   // 추정한 최소 진수 (Initially guessed minimum base)
    static int confirmedBase = -1;         // 확정된 진수 (-1이면 아직 확정되지 않음)
    static boolean[] isVisited;            // 이미 처리된 표현식 표시 (Indicates if an expression has been processed)
    static String[] resultExpressions;     // 결과를 저장할 배열 (Array to store the results)
    static int resultIndex = 0;            // 결과 배열의 인덱스 (Index for the result array)

    public static String[] solution(String[] expressions) {
        resultExpressions = new String[expressions.length];
        isVisited = new boolean[expressions.length];

        // 각 표현식을 검사하여 진수를 추정하고 확정된 진수를 찾는다.
        for (int i = 0; i < expressions.length; i++) {
            String expression = expressions[i];
            String[] tokens = expression.split(" ");

            int operandA = Integer.parseInt(tokens[0]);    // 첫 번째 피연산자
            String operator = tokens[1];                   // 연산자 (+ 또는 -)
            int operandB = Integer.parseInt(tokens[2]);    // 두 번째 피연산자
            String resultStr = tokens[4];                  // 결과 (또는 'X')

            // 각 숫자의 일의 자리와 십의 자리 추출
            int aUnitsDigit = operandA % 10;   // operandA의 일의 자리
            int aTensDigit = operandA / 10;    // operandA의 십의 자리

            int bUnitsDigit = operandB % 10;   // operandB의 일의 자리
            int bTensDigit = operandB / 10;    // operandB의 십의 자리

            // 현재 표현식에서의 최대 자릿수 구하기
            int currentMaxDigit = Math.max(Math.max(aUnitsDigit, aTensDigit), Math.max(bUnitsDigit, bTensDigit));

            // 추정한 최소 진수를 갱신 (현재 최대 자릿수 + 1과 기존 추정 값 중 큰 값)
            estimatedMinimumBase = Math.max(currentMaxDigit + 1, estimatedMinimumBase);

            if (resultStr.equals("X")) continue;  // 결과가 'X'이면 다음으로
            isVisited[i] = true;  // 결과가 있는 표현식은 방문 표시
            int resultValue = Integer.parseInt(resultStr);     // 결과를 정수로 변환
            int resUnitsDigit = resultValue % 10;              // 결과의 일의 자리
            int resTensDigit = (resultValue % 100) / 10;       // 결과의 십의 자리
            int resHundredsDigit = resultValue / 100;          // 결과의 백의 자리

            // 결과의 최대 자릿수에 따라 추정한 최소 진수를 갱신
            estimatedMinimumBase = Math.max(estimatedMinimumBase, Math.max(resUnitsDigit, resTensDigit) + 1);

            if (operator.equals("+")) {
                // 덧셈에서 올림을 고려하여 확정된 진수를 찾는다.
                int expectedSum = aUnitsDigit + bUnitsDigit;       // 일의 자리 예상 합
                int difference = expectedSum - resUnitsDigit;      // 예상 합과 실제 결과의 차이
                int carry = difference == 0 ? 0 : 1;               // 올림 발생 여부 (0: 없음, 1: 발생)

                if (carry == 1) {
                    confirmedBase = difference;  // 차이가 진수와 관련되므로 확정된 진수 설정
                    break;
                }

                expectedSum = aTensDigit + bTensDigit;
                difference = expectedSum - resTensDigit;
                if (difference == 0) continue;
                confirmedBase = difference;  // 차이가 진수와 관련되므로 확정된 진수 설정
            } else {
                // 뺄셈에서 빌림을 고려하여 확정된 진수를 찾는다.
                if (aUnitsDigit >= bUnitsDigit) {
                    continue;  // 빌림이 없으면 다음으로
                }

                int expectedDifference = 10 + aUnitsDigit - bUnitsDigit;    // 빌림이 발생한 일의 자리 계산
                int difference = expectedDifference - resUnitsDigit;
                confirmedBase = 10 - difference;      // 차이를 통해 진수를 계산하여 확정된 진수 설정
            }
        }

        // 추정한 최소 진수가 9인 경우 확정된 진수를 9로 설정 (진수는 최대 9까지)
        if (estimatedMinimumBase == 9) {
            confirmedBase = 9;
        }

        // 결과가 'X'인 표현식에 대해 결과를 계산한다.
        for (int i = 0; i < expressions.length; i++) {
            if (isVisited[i]) continue;  // 이미 처리된 표현식은 넘어감

            String expression = expressions[i];
            String[] tokens = expression.split(" ");

            int operandA = Integer.parseInt(tokens[0]);
            String operator = tokens[1];
            int operandB = Integer.parseInt(tokens[2]);
            String resultStr = tokens[4];

            if (!resultStr.equals("X")) continue;  // 결과가 있는 표현식은 넘어감

            int aUnitsDigit = operandA % 10;   // operandA의 일의 자리
            int aTensDigit = operandA / 10;    // operandA의 십의 자리

            int bUnitsDigit = operandB % 10;   // operandB의 일의 자리
            int bTensDigit = operandB / 10;    // operandB의 십의 자리

            // 확정된 진수가 없는 경우 추정한 최소 진수로 결과를 계산
            if (confirmedBase == -1) {
                if (operator.equals("+")) {
                    // 덧셈에서 추정한 진수로 결과를 계산하고, 올림이 발생하면 '?'로 표시
                    if (aUnitsDigit + bUnitsDigit >= estimatedMinimumBase || aTensDigit + bTensDigit >= estimatedMinimumBase) {
                        resultExpressions[resultIndex++] = operandA + " " + operator + " " + operandB + " = ?";
                        continue;
                    }

                    // 결과를 계산하여 저장
                    resultExpressions[resultIndex++] = operandA + " " + operator + " " + operandB + " = " + (operandA + operandB);
                } else {
                    // 뺄셈에서 추정한 진수로 결과를 계산하고, 빌림이 발생하면 '?'로 표시
                    if (aUnitsDigit < bUnitsDigit) {
                        resultExpressions[resultIndex++] = operandA + " " + operator + " " + operandB + " = ?";
                        continue;
                    }

                    // 결과를 계산하여 저장
                    resultExpressions[resultIndex++] = operandA + " " + operator + " " + operandB + " = " + (operandA - operandB);
                }
            }
            // 확정된 진수가 있는 경우 그 진수로 결과를 계산
            else {
                calculateResult(operandA, operandB, operator);  // 계산 메서드 호출
            }
        }

        return Arrays.copyOf(resultExpressions, resultIndex);  // 결과 배열 반환
    }

    // 확정된 진수를 사용하여 결과를 계산하는 메서드
    private static void calculateResult(int operandA, int operandB, String operator) {
        int aUnitsDigit = operandA % 10;  // operandA의 일의 자리
        int aTensDigit = operandA / 10;   // operandA의 십의 자리

        int bUnitsDigit = operandB % 10;  // operandB의 일의 자리
        int bTensDigit = operandB / 10;   // operandB의 십의 자리

        int carryOrBorrow = 0;   // 올림 또는 빌림을 저장할 변수
        int resUnitsDigit = 0;   // 결과의 일의 자리
        int resTensDigit = 0;    // 결과의 십의 자리
        int resHundredsDigit = 0; // 결과의 백의 자리 (덧셈에서 발생할 수 있음)

        if (operator.equals("+")) {

            // 덧셈에서 일의 자리 계산
            if (aUnitsDigit + bUnitsDigit >= confirmedBase) {
                carryOrBorrow = 1;  // 올림 발생
                resUnitsDigit = aUnitsDigit + bUnitsDigit - confirmedBase;
            } else {
                resUnitsDigit = aUnitsDigit + bUnitsDigit;
            }

            // 덧셈에서 십의 자리 계산
            if (aTensDigit + bTensDigit + carryOrBorrow >= confirmedBase) {
                resHundredsDigit = 1;  // 백의 자리 발생
                resTensDigit = aTensDigit + bTensDigit + carryOrBorrow - confirmedBase;
            } else {
                resTensDigit = aTensDigit + bTensDigit + carryOrBorrow;
            }

            // 최종 결과를 계산하여 저장
            int finalResult = resUnitsDigit + resTensDigit * 10 + resHundredsDigit * 100;
            resultExpressions[resultIndex++] = operandA + " " + operator + " " + operandB + " = " + finalResult;
        } else {
            // 뺄셈에서 일의 자리 계산
            if (aUnitsDigit < bUnitsDigit) {
                aTensDigit--;                   // 빌림 발생으로 십의 자리에서 1 차감
                aUnitsDigit += confirmedBase;    // 일의 자리에 진수를 더함
                resUnitsDigit = aUnitsDigit - bUnitsDigit;
            } else {
                resUnitsDigit = aUnitsDigit - bUnitsDigit;
            }

            // 뺄셈에서 십의 자리 계산
            resTensDigit = aTensDigit - bTensDigit;

            // 최종 결과를 계산하여 저장
            int finalResult = resUnitsDigit + resTensDigit * 10;
            resultExpressions[resultIndex++] = operandA + " " + operator + " " + operandB + " = " + finalResult;
        }
    }
}

 

---

결론

 

두 풀이를 잘 조합하면 더 효율적인 풀이가 가능할 것 같은데, 결과적으로 두 풀이의 실행시간 차이가 크게 나지않아서 그만뒀다.

문제를 풀이하면서 (Integer.ParseInt(str, base)), Integer.toString(computedResult, base) 을 처음 사용해봤다.