[level 3][PCCP 기출문제] 4번 / 수식 복원하기 - 340210

문제 링크

성능 요약

메모리: 96.1 MB, 시간: 3.00 ms

구분

코딩테스트 연습 > PCCP 기출문제

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2025년 07월 30일 09:38:25

문제 설명

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

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

다음은 그 예시입니다.

<수식>

14 + 3 = 17
13 - 6 = X
51 - 5 = 44

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

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

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

<수식>

1 + 1 = 2
1 + 3 = 4
1 + 5 = X
1 + 2 = X

주어진 수식들에서 이 문명에서 사용한 진법이 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인 수식은 결괏값이 지워진 수식을 의미하며, 이러한 수식은 한 번 이상 등장합니다.
  • 결괏값이 음수가 되거나 서로 모순되는 수식은 주어지지 않습니다.

입출력 예

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

문제 예시와 같습니다.

입출력 예 #3

30 + 31 = 101에서 이 문명이 사용하던 진법이 6진법임을 알 수 있습니다. 따라서 10 - 2 = X, 3 + 3 = X, 33 + 33 = X의 지워진 결괏값을 채워 넣으면 10 - 2 = 4, 3 + 3 = 10, 33 + 33 = 110이 됩니다.

따라서 ["10 - 2 = 4", "3 + 3 = 10", "33 + 33 = 110"]을 return 해야 합니다.

입출력 예 #4

수식에 등장하는 숫자들을 통해 이 문명이 사용하던 진법이 8진법 혹은 9진법임을 알 수 있습니다. 2 + 2 = X와 5 - 5 = X의 지워진 결괏값을 채워 넣으면 8진법, 9진법에 관계없이 2 + 2 = 4, 5 - 5 = 0이 됩니다. 7 + 4 = X의 결괏값은 불확실하므로 지워진 결괏값을 채워 넣으면 7 + 4 = ?가 됩니다.

따라서 ["2 + 2 = 4", "7 + 4 = ?", "5 - 5 = 0"]을 return 해야 합니다.

입출력 예 #5

네 번째 예시와 같지만 5 - 5 = X가 8 + 4 = X로 바뀌었습니다. 이 문명이 사용하던 진법이 9진법임을 알 수 있으므로 7 + 4 = X와 8 + 4 = X의 지워진 결괏값을 채워 넣으면 7 + 4 = 12, 8 + 4 = 13이 됩니다.

따라서 ["2 + 2 = 4", "7 + 4 = 12", "8 + 4 = 13"]을 return 해야 합니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

문제 풀이

• 진법 후보를 찾아야한다. 모든 수식(X 포함)에서 나타나는 최대 숫자를 찾아 최소 진법을 결정할 수 있다.
  ex) '7'이 등장하면 최소 8진법 이상이어야 함.

• 유효한 진법 필터링: X가 없는 완전한 수식들이 해당 진법에서 성립하는지 확인

코드

import java.util.*;

class Solution {
    static List<String> ansList = new ArrayList<>();
    static List<Integer> ableRadix = new ArrayList<>();
    public String[] solution(String[] expressions) {        
        int maxN = 0;
        for(String e : expressions){
            maxN = Math.max(maxN, getMaxFromExpression(e));
        }
        int minRadix = maxN + 1; // 최소 가능한 진법
        
        for(int i=minRadix; i<=9; i++){
            boolean flag = true;
            for(String e : expressions){
                if(!e.contains("X")){
                    if(!isValid(e, i)){
                        flag = false;
                        break;  
                    }
                }
            }
            
            // i진법이 유효할때
            if(flag) ableRadix.add(i);
        }
        
        for(String e : expressions){
            if(e.contains("X")){
                String res = makeAns(e);
                ansList.add(res);
            }
        }
        
        return ansList.toArray(new String[0]);
    }
    
    // 전체식에서 최대숫자찾기
    private int getMaxFromExpression(String e){
        int m = 0;
        String[] arr = e.split(" ");
        
        m = Math.max(m, getMaxFromNumber(arr[0]));
        m = Math.max(m, getMaxFromNumber(arr[2]));
        if(!arr[4].equals("X")){
            m = Math.max(m, getMaxFromNumber(arr[4]));
        }
        
        return m;
    }
    
    // 각 숫자 String에서 최대 숫자(0~9) 찾기
    private int getMaxFromNumber(String str){
        if(str.equals("X")) return 0;
        
        int max = 0;
        for(char c : str.toCharArray()){
            int digit = c - '0';
            max = Math.max(max, digit);
        }
        return max;
    }
    
    private boolean isValid(String e, int i){
        String[] arr = e.split(" ");
        
        // 숫자가 i진법에서 유효한지 체크 ex) 2진법에선 0,1 만 가능
        if(!canParse(arr[0], i) || !canParse(arr[2], i) || !canParse(arr[4], i)) return false;
        
        // a (+/-) b = c
        int a = getNum(arr[0], i);
        int b = getNum(arr[2], i);
        int c = getNum(arr[4], i);
        
        int cal = 0;
        if(arr[1].equals("+")) cal = a + b;
        else cal = a - b;
        
        return c == cal;
    }
    
    private String makeAns(String e){ // X 채우기
        String[] arr = e.split(" ");
        
        Set<String> cals = new HashSet<>();
        
        for(int i : ableRadix){
            // i진법에서 숫자들이 유효한지 체크
            if(!canParse(arr[0], i) || !canParse(arr[2], i)) continue;
            
            int a = getNum(arr[0], i);
            int b = getNum(arr[2], i);
            
            int cal = 0;
            if(arr[1].equals("+")) cal = a + b;
            else cal = a - b;
            
            cals.add(Integer.toString(cal, i));
        }
        
        if(cals.size() == 1) return e.replace("X", cals.stream().findFirst().orElse(null));
        else return e.replace("X", "?");
    }
    
    private int getNum(String str, int radix){
        if(str.equals("X")) return 0;
        return Integer.parseInt(str, radix);
    }
    
    private boolean canParse(String str, int i){
        if(str.equals("X")) return true;
        
        for(char c : str.toCharArray()){
            int digit = c - '0';
            if(digit >= i) return false;
        }
        return true;
    }
}