프로그래머스 수식 복원하기 자바 풀이

문제 링크

문제 요약

덧셈 또는 뺄셈 수식이 문자열 배열 expressions로 주어진다
사용된 진법은 2 ~ 9진법 중 하나이지만 어떤 진법인지는 알 수 없다
결괏값이 X로 지워진 수식의 값을 채워 넣는다. 진법에 따라 값이 달라지면 ?를 채운다

문제 풀이

처음에는 문자열의 숫자를 그냥 10진수로 읽어서 계산하면 되지 않을까 생각했다.

하지만 이 문제는 애초에 사용된 진법을 모른다는 게 핵심이다.

10진수로 읽으면 결괏값이 지워지지 않은 수식조차 검증할 방법이 없다.

이 문제의 핵심은 결괏값이 남아 있는 수식으로 가능한 진법 후보를 먼저 좁혀야 한다는 점이다.

우선 모든 수식에 등장하는 숫자 중 가장 큰 자릿값을 찾는다.

진법은 그 숫자보다 커야 하므로, 후보 진법의 최솟값이 정해진다.

그 다음 결괏값이 남아 있는 수식들을 하나씩 확인하면서, 각 후보 진법으로 계산했을 때 실제로 식이 성립하는지 검사해 성립하지 않는 진법은 후보에서 제외한다.

남은 후보 진법들로 X가 있는 수식을 계산해서, 모든 후보에서 결괏값이 하나로 같으면 그 값을, 후보마다 값이 다르면 ?를 채워 넣는다.

expressions의 길이가 최대 100이고 후보 진법도 최대 8개뿐이라, 후보를 좁힌 뒤 전부 대입해봐도 충분히 빠르다.

최종 코드

java

import java.util.*;

class Solution {
    public String[] solution(String[] expressions) {
        
        List<String> ans = new ArrayList<>(); // 결괏값이 X인 수식들
        List<String> reason = new ArrayList<>(); // 결괏값이 남아 있어 진법을 판별할 근거가 되는 수식들
        int max = 0; // 등장한 숫자 중 최댓값, 진법 후보의 하한을 정하는 데 쓴다
        
        for(int i=0;i<expressions.length;i++){
            if(expressions[i].endsWith("X"))
                ans.add(expressions[i]);
            else
                reason.add(expressions[i]);
            
            for(int j=0;j<expressions[i].length();j++){
                char now = expressions[i].charAt(j);
                
                if(now >= '0' && now<'9')
                    max = Math.max(max, now - '0');
            }
        }
        String[] answer = new String[ans.size()];
        
        boolean[] isPossible = new boolean[10];
        Arrays.fill(isPossible, true);
        
        // 진법은 등장한 숫자보다 커야 하므로, 그보다 작거나 같은 진법은 후보에서 제외
        for(int i=0;i<Math.max(2, max+1);i++){
            isPossible[i] = false;
        }
        
        for(String now : reason){
            StringTokenizer st = new StringTokenizer(now);
            String num1 = st.nextToken();
            String op = st.nextToken();
            String num2 = st.nextToken();
            st.nextToken();
            String result = st.nextToken();
            
            for(int i=2;i<=9;i++){
                if(!isPossible[i])
                    continue;
                
                int a = Integer.parseInt(num1, i);
                int b = Integer.parseInt(num2, i);
                int r = Integer.parseInt(result, i);
                
                // 결괏값이 남아 있는 수식이 성립하지 않으면 그 진법은 답이 될 수 없다
                if("+".equals(op) && a+b != r){
                    isPossible[i] = false;
                }
                else if("-".equals(op) && a-b != r){
                    isPossible[i] = false;
                }
            }
        }
        
        int idx = 0;
        for(String now : ans){
            StringTokenizer st = new StringTokenizer(now);
            String num1 = st.nextToken();
            String op = st.nextToken();
            String num2 = st.nextToken();
            
            Set<String> s = new HashSet<>(); // 후보 진법마다 계산한 결괏값을 모아 중복을 제거
            for(int i=2;i<=9;i++){
                if(!isPossible[i])
                    continue;
                
                int a = Integer.parseInt(num1, i);
                int b = Integer.parseInt(num2, i);
                
                if("-".equals(op))
                    s.add(Integer.toString(a-b, i));
                else
                    s.add(Integer.toString(a+b, i));
            }
            
            now = now.substring(0,now.length()-1);
            if(s.size()==1){ // 후보 진법 전부에서 값이 같으면 그 값으로 확정
                answer[idx++] = now+s.iterator().next();
            }
            else{
                answer[idx++] = now+"?"; // 진법에 따라 값이 달라지면 ?로 표기
            }
        }
        
        return answer;
    }
}

수식 복원하기

문제 요약

문제 풀이

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기