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

문제 링크

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

풀이

진법 변환 문제를 많이 접해보지 못해서 어려웠던 문제이다.

ArrayList<Formula> com = new ArrayList<>();
ArrayList<Formula> nCom = new ArrayList<>();

나는 먼저 계산된 식을 com에, 계산되지 않은 식을 nCom에 나누어 넣었다.

for(int i = 2; i<=9;i++){
		boolean flag = false;
		for(Formula cur : com){
				try{
						int left = Integer.parseInt(cur.left, i), right = Integer.parseInt(cur.right, i), answer = Integer.parseInt(cur.answer, i);
						if(cur.symbol.equals("+") && left + right != answer) flag = true;
						else if(cur.symbol.equals("-") && left - right != answer) flag = true;
				} catch (NumberFormatException e) {
						flag = true;
				}
				
		}
		check[i] = flag;
}

이후, 계산된 식에서 2에서 9진법까지 돌면서 각 진법에 대해 올바른 식인지 확인했다. i진법으로 변환이 가능하다면 check[i] = false이고, 불가능하다면 check[i] = true로 저장했다. 이 과정에서 Integer.parseInt 메서드를 사용하여 숫자가 i진법이라는 가정하에, 숫자를 10진법으로 변환하여 결과를 확인했다.

만약 i진법으로 변환하지 못하게 된다면 NumberFormatException을 띄우게 되므로 check[i] = true 처리를 해줬다.

그다음이 좀 헷갈렸는데, 계산되지 않은 식의 경우에 대해서도 i진법으로 변환 가능한지 여부를 확인해줘야 했다. 왜냐하면 계산된 식을 만족하는 진법이 계산되지 않은 식에서 만족된다는 보장이 없기 때문이다. 난 이를 몰랐고, 테케는 통과했는데 제출 후 틀렸다.

계산된 식을 만족하는 진법 중, 계산되지 않은 식을 만족하는 진법을 따로 골라야 한다.

for(int i = 2; i <= 9; i++){
	boolean flag = false;
	for(Formula cur : nCom){
			if(check[i]) continue;
				
			try{
					int left = Integer.parseInt(cur.left, i), right = Integer.parseInt(cur.right, i);
			} catch (NumberFormatException e){
					flag = true;
			}
			check[i] = flag;
	}
}

계산되지 않은 식은 답이 없기 때문에, left와 right에 대해서만 진법 변환이 가능한지 판별하면 된다.

이 과정을 거치면 check[]에는 모든 식에 만족하는 진법만이 존재하게 된다.

for(Formula cur : nCom){
	boolean flag = false;
	String temp = "";
	for(int i = 2; i <= 9; i++){
			if(check[i]) continue;

			int left = Integer.parseInt(cur.left, i), right = Integer.parseInt(cur.right, i);
			int answer;
			if(cur.symbol.equals("+")) answer = left + right;
			else answer = left - right;

			if(temp.equals("")) temp = Integer.toString(answer,i);
			else if(!temp.equals(Integer.toString(answer,i))) flag = true;
					
	}
	if(flag) answerList.add(cur.left+" "+cur.symbol+" "+cur.right+" = ?");
	else answerList.add(cur.left+" "+cur.symbol+" "+cur.right+" = "+temp);
}

이제 계산되지 않은 식이 모든 식을 만족하는 진법에 대해서 모두 같은 값을 내놓는지 검증하면 된다. 모든 진법에 대해 같은 결과를 내놓는지 판단하기 위해, answer는 10진법인 left와 right를 계산한 결과가 들어가기 때문에, Integer.toString 메서드로 다시 i진법으로 변환하여 결과값을 저장하고 비교했다.

전체 코드

import java.util.*;

class Formula{
    String left, right, answer, symbol;
    Formula(String left, String right, String answer, String symbol){
        this.left = left;
        this.right = right;
        this.answer = answer;
        this.symbol = symbol;
    }
}
class Solution {
    public String[] solution(String[] expressions) {
        ArrayList<String> answerList = new ArrayList<>();
        
        ArrayList<Formula> com = new ArrayList<>();
        ArrayList<Formula> nCom = new ArrayList<>();

        for(String cur : expressions){
            String input[] = cur.split(" ");
            if(input[4].equals("X")) nCom.add(new Formula(input[0], input[2], input[4], input[1]));
            else com.add(new Formula(input[0], input[2], input[4], input[1]));

        }
        
        boolean[] check = new boolean[10];
        for(int i = 2; i<=9;i++){
            boolean flag = false;
            for(Formula cur : com){
                try{
                    int left = Integer.parseInt(cur.left, i), right = Integer.parseInt(cur.right, i), answer = Integer.parseInt(cur.answer, i);
                    if(cur.symbol.equals("+") && left + right != answer) flag = true;
                    else if(cur.symbol.equals("-") && left - right != answer) flag = true;
                } catch (NumberFormatException e) {
                    flag = true;
                }
               
            }
            check[i] = flag;
        }
        for(int i = 2; i <= 9; i++){
            boolean flag = false;
            for(Formula cur : nCom){
                if(check[i]) continue;
                 
                try{
                    int left = Integer.parseInt(cur.left, i), right = Integer.parseInt(cur.right, i);
                } catch (NumberFormatException e){
                    flag = true;
                }
                check[i] = flag;
            }
        }
        
				for(Formula cur : nCom){
					boolean flag = false;
					String temp = "";
					for(int i = 2; i <= 9; i++){
							if(check[i]) continue;
	
							int left = Integer.parseInt(cur.left, i), right = Integer.parseInt(cur.right, i);
							int answer;
							if(cur.symbol.equals("+")) answer = left + right;
							else answer = left - right;

							if(temp.equals("")) temp = Integer.toString(answer,i);
							else if(!temp.equals(Integer.toString(answer,i))) flag = true;    
									
					}
					if(flag) answerList.add(cur.left+" "+cur.symbol+" "+cur.right+" = ?");
					else answerList.add(cur.left+" "+cur.symbol+" "+cur.right+" = "+temp);
			}
        
        return answerList.toArray(new String[0]);
    }
}