프로그래머스 : 수식 복원하기 (Java)

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

[PCCP 기출문제] 4번 / 수식 복원하기

문제 설명

첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다.

당신은 덧셈 혹은 뺄셈 수식이 여러 개 적힌 고대 문명의 유물을 찾았습니다. 이 수식들을 관찰하던 당신은 이 문명이 사용하던 진법 체계가 10진법이 아니라는 것을 알아냈습니다. (2 ~ 9진법 중 하나입니다.)

수식들 중 몇 개의 수식은 결괏값이 지워져 있으며, 당신은 이 문명이 사용하던 진법에 맞도록 지워진 결괏값을 채워 넣으려 합니다.

다음은 그 예시입니다.

• X로 표시된 부분이 지워진 결괏값입니다.

51 - 5 = 44에서 이 문명이 사용하던 진법이 8진법임을 알 수 있습니다. 따라서 13 - 6 = X의 지워진 결괏값을 채워 넣으면 13 - 6 = 5가 됩니다.

 

다음은 또 다른 예시입니다.

주어진 수식들에서 이 문명에서 사용한 진법이 6 ~ 9진법 중 하나임을 알 수 있습니다.
1 + 5 = X의 결괏값은 6진법일 때 10, 7 ~ 9진법일 때 6이 됩니다. 이와 같이 결괏값이 불확실한 수식은 ?를 사용해 1 + 5 = ?와 같이 결괏값을 채워 넣습니다.
1 + 2 = X의 결괏값은 6 ~ 9진법에서 모두 3으로 같습니다. 따라서 1 + 2 = X의 지워진 결괏값을 채워 넣으면 1 + 2 = 3이 됩니다.

덧셈 혹은 뺄셈 수식들이 담긴 1차원 문자열 배열 expressions가 매개변수로 주어집니다. 이때 결괏값이 지워진 수식들의 결괏값을 채워 넣어 순서대로 문자열 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한 사항

• 2 ≤ expressions의 길이 ≤ 100
• expressions의 원소는 "A + B = C" 혹은 "A - B = C" 형태의 문자열입니다. A, B, C와 연산 기호들은 공백 하나로 구분되어 있습니다.
• A, B는 음이 아닌 두 자릿수 이하의 정수입니다.
• C는 알파벳 X 혹은 음이 아닌 세 자릿수 이하의 정수입니다. C가 알파벳 X인 수식은 결괏값이 지워진 수식을 의미하며, 이러한 수식은 한 번 이상 등장합니다.
• 결괏값이 음수가 되거나 서로 모순되는 수식은 주어지지 않습니다.

import java.util.*;

class Solution {

    public String[] solution(String[] expressions) {
        List<String> answer = new ArrayList<>(); // 정답을 반환할 리스트
        List<List<String>> questions = new ArrayList<>(); // 결과가 X인 수식을 저장해놓을 리스트
        boolean[] candidate = new boolean[10]; // 진법 후보
        
        Arrays.fill(candidate, true);
        
        for (String str : expressions) {
            List<String> list = parse(str);

            // 결과가 X인 수식은 나중에 다시 푼다.
            if (list.get(4).equals("X")) {
                questions.add(list);
            } 
            
            for (int k=2; k<=9; k++) {
                if (candidate[k]) {
                    // k진법이 가능한지 검사하고 candidate 갱신
                    candidate[k] = isValidK(k, list.get(0), list.get(2), list.get(4), list.get(1));
                }
            }
        }
        
        for (List<String> q : questions) {
            boolean flag = true; // 결과값이 한 개 인지 판단하는 변수
            String c = ""; // 계산 결과
            
            for (int k=2; k<=9; k++) {
                if (!candidate[k]) continue;
                
                String a = q.get(0);
                String b = q.get(2);
                String op = q.get(1);
                int res = calc(changeKtoTen(k, a), changeKtoTen(k, b), op);
                
                // 가능한 모든 k진법에서 결과값이 같은지 검사, 하나라도 다르다면 break
                if (c.isEmpty()) {
                    c = changeTentoK(k, res);
                } else {
                    if (!c.equals(changeTentoK(k, res))) {
                        flag = false;
                        break;
                    }
                }
            }
            
            // 모든 결과값이 같다면 X를 c로 치환, 하나라도 다르다면 ?로 치환
            if (flag) q.set(4, c);
            else q.set(4, "?");
            
            String str = String.join(" ", q); // 수식 다시 합치기
            answer.add(str);
        }
        
        return answer.stream().toArray(String[]::new);
    }
    
    // 수식을 공백 기준으로 분리하는 메소드
    public List<String> parse(String str) {
        String[] strArr = str.split(" ");
        List<String> list = new ArrayList<>(Arrays.asList(strArr));
        
        return list;
    }
    
    // op에 따라 a와 b의 계산 결과를 반환하는 메소드
    public int calc(int a, int b, String op) {
        if (op.equals("+")) return a + b;
        else return a - b;
    }
    
    // 10진수 x를 k진수 String으로 변환하는 메소드
    public String changeTentoK(int k, int x) {
        if (x == 0) return "0";
        
        String ret = "";
        
        while (x > 0) {
            ret += x % k;
            x /= k;
        }
        
        StringBuilder sb = new StringBuilder(ret);
        return sb.reverse().toString();
    }
    
    // k진수 x를 10진수 int 값으로 변환하는 메소드
    public int changeKtoTen(int k, String x) {        
        int d = 1;
        int sum = 0;
        
        for (int i=x.length()-1; i>=0; i--) {
            sum += (x.charAt(i) - '0') * d;
            d *= k;
        }
        
        return sum;
    }
    
    // K진수 기준으로 수식을 계산했을 때 유효한지 검사하는 메소드 
    public boolean isValidK(int k, String a, String b, String c, String op) {
        // a에 있는 모든 숫자는 k보다 작아야 한다.
        for (int i=0; i<a.length(); i++) {
            if (a.charAt(i)-'0' >= k) return false;
        }
        
        // b에 있는 모든 숫자는 k보다 작아야 한다.
        for (int i=0; i<b.length(); i++) {
            if (b.charAt(i)-'0' >= k) return false;
        }
        
        // c가 X면 검사하지 않고, X가 아닐 경우 c에 있는 모든 숫자가 k보다 작은지 검사한다.
        if (c.equals("X")) return true;
        else {
            for (int i=0; i<c.length(); i++) {
                if (c.charAt(i)-'0' >= k) return false;
            }
        }
        
        // a 와 b를 op로 계산했을 때 c와 같은 값인지 검사한다.
        return changeKtoTen(k, c) == calc(changeKtoTen(k, a), changeKtoTen(k, b), op);
    }
    
}