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

프로그래머스

 

이 문제를 풀려면 10진법을 N 진법으로, N진법을 10진법을 바꾸는 방법 에 대해서 정확하게 알고 있어야 한다. 

그 기법을 정리하기에도 좋은 문제이다. 

 

이 문제의 경우 2~9진법을 제한을 두었지만 지금은 제한이 없다고 생각해보자.

그래야 각 함수가 왜 문자열을 쓰는지 이해할 수 있다. 

10진법 ➡️ N진법

public static String toString(int i,
                              int radix)

 

i 를 radix 진법으로 바꾼다. 왜 return 하는게 String 이냐면 11진법 이후로는 알파벳이 생기기 때문이다.

"알파벳이 생길 수 있다"를 기억하면 toString이 N 진법으로 바꾸는데 쓰인다는 것을 외우기 쉽다. 

 

N진법 ➡️ 10진법

public static int parseInt(String s,
                           int radix)
                    throws NumberFormatException

 

이 함수를 사용하는데 radix가 "밑"이다. 2진법에서는 2,    4진법에서는 4 라고 생각하면 쉽니다. 

따라서 String 으로 표현되어 있는 수가 radix 진법이니 해석해 달라고 볼 수 있다. 

 

Integer.parseInt("ab2",16); 

라고 하면 16진법으로 표현한 ab2니까 10진법으로 해석해줘. 이렇게 볼 수 있다. 

 

그리고 보면 throws NumberFormatException 가 있다.

 

만약 2진법인데 30 이런 숫자는 존재할 수 가 없다. 

왜냐하면 2진법은 '0'과 '1'이라는 두 개의 숫자만 사용해서 모든 수를 표현하는 방식이기 때문이다.

 

따라서 만약 String s 와 radix가 정의에 맞지 않게 적혀있다면 Exception을 일으킨다. 

이 문제에서도 이 Exception을 활용했다. 

 

다시 문제로 돌아가보면

이 문제에서는 수식들을 모두 고려하여

1) 가능한 진법들을 모두 구한다.

2 - 1) 그리고 그 모든 진법에 대해 값이 값을 경우 X를 대체하여 값을 적고

2 - 2) 진법들에 대해서 계산 값이 다르면 X를 대체하여 ? 를 적는다.

 

뭔말인지 모르겠으니 예를 들어보자

 

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

 

 

이렇게 수식이 있다. 

직접 다 계산을 해봤을 때, 5~9진법이 가능하나

1 + 5 = X 가 있으므로 5진법일 수는 없다.

 

따라서 6~9진법이 가능하다.

1 + 5 = X를 먼저 보자

 

6진법 1 + 5 = 10

7진법~9진법 1 + 5 = 6

 

즉 6진법을 제외하고는 다 값이 같다. 모든 가능한 진법에 대해 값이 같지 않으니 X 자리에는 ? 가 들어간다. 

 

반면에 

1 + 2 는 6~9진법에 대해 전부 3이다. 

 

따라서 

1 + 5 = ?, 1 + 2 = 3 이 답이다.

 

 

 

나는 우선 2~9진법으로 모든 수식을 순회하며 우선 해당 진법으로 변환이 되는지 확인했다.

이렇게 하면 아까와 같이 

1 + 5 = 6 에서 5진법을 Exception으로 걸러낼 수 있다. 

 

다음으로 등호 옆의 같이 X가 아닌 경우 계산 값과 일치하는지를 고려해 후보 진법을 뽑아냈다. 

 

그 이후에는 X가 있는 수식에 모든 후보 진법에 대해서 값이 같게 나오는지 확인했다.

 

이 문제에서 거의 처음으로 Exception을 코테 문제에서 써본거 같다. 

덕분에 확실히 진법 관련 문제는 풀 수 있을 거 같다. 

 

import java.util.*;
import java.util.stream.*;

class Solution {
    
    public ArrayList<String> solution(String[] expressions) {
        ArrayList<String> answer = new ArrayList<>();
        ArrayList<Integer> candidate = new ArrayList<>();
        
        //2~9 진법을 순환하기
        for(int i=2; i<10; i++){
            boolean flag = true;
            
            for(int j=0; j<expressions.length; j++) {
                String[] arr = expressions[j].split(" ");

                String res = getResult(expressions[j], i);
                
                if (res.isEmpty()) {
                    flag = false;
                    break; 
                }
                
                if (!arr[4].equals("X")) {
                    try {
                        Long.parseLong(arr[4], i); 
                    } catch (NumberFormatException e) {
                        flag = false; 
                        break;
                    }

                    if (!arr[4].equals(res)) {
                        flag = false; 
                        break;
                    }
                }
            }
            
            if(flag == true){
                candidate.add(i);
            }
        }
        
        
        for(String exp: expressions) {
            String[] arr = exp.split(" ");
            if(arr[4].equals("X")){
                int N = candidate.get(0);
                String start = getResult(exp, N);
                boolean flag = true;
                for(int i=1; i<candidate.size(); i++) {
                    N = candidate.get(i);
                    String res = getResult(exp, N);
                    if(!start.equals(res)){
                        flag = false;
                        break;
                    }
                }
                
                String ans = "";
                if(flag){ 
                    ans = arr[0] + " " + arr[1] + " " + arr[2] + " " 
                            + arr[3] + " " + start + "";
                } else {
                    ans = arr[0] + " " + arr[1] + " " + arr[2] + " " 
                            + arr[3] + " ?";
                }
                answer.add(ans);
            }
        }
        
        return answer;
    }
    
    
    private static String getResult(String exp, int N){
        try{
            String[] arr = exp.split(" ");
            long a = Long.parseLong(arr[0], N);
            String op = arr[1];
            long b = Long.parseLong(arr[2], N);
            String c = arr[4];

            long result = calculate(a, b, op);
            String result2 = Long.toString(result, N);
            
            return result2;
            
        } catch (NumberFormatException e) {
            return ""; 
        }
    }
   
    
    private static long calculate(long a, long b, String op){
        switch (op){
            case "+":
                return a + b;
            case "-":
                return a - b;
        }
        return 0;
    }
}