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

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

프로그래머스

 

 

 

문제 이해

- 주어진 expressions 문자열 배열에 대하여 결과값이 있는 것과 "X"로 되어있는데, 해당 수식은 2진법부터 9진법 사이에 연산으로 이루어져있다.
- 우리는 여기서 해당 수식들이 어떤 진법으로 계산되어있는지를 파악하고, "X"에 해당하는 정확한 연산 결과 값을 넣어서, result 배열에 출력하도록 한다.
- 만약, 진법이 정확하게 유추가 되지 않는 상황이라면 결과값에 대해 "?"를 넣어 return 하도록 한다.

 

 

미리 알아두면 좋은 String 관련 함수들

Character.toCharArray(String 문자열을 각각 char[]형 배열로 확인할 수 있게 도와주는 함수);

Character.isDigit(해당 char형이 숫자형으로 사용할 수 있는지 판별);

Character.getNumericValue(해당 unicode를 int형으로 바꿔준다.);

Integer.parseInt(숫자로 변환하고자 하는 String 문자열, 바꾸고자 하는 진법);

Integer.toString(문자열로 바꾸고자 하는 Integer형 정수, 바꾸고자 하는 진법);

 

 

풀이 과정

해당 코드는 적혀있는 피연산자 값이 내가 유추한 진법에 올바르게 표기되어있는지 확인하는 메소드이다.

// 해당 숫자가 진법에 맞는지 판별 여부
    static boolean isValid(String number, int check) {
        
        for(Character c : number.toCharArray()) {
            
            int value = Character.getNumericValue(c);
            
            if(value < 0 || value >= check) return false;
        }
        
        return true;
    }

 

 

해당 코드는 수식에 적혀있는 피연산자에 대하여, 해당 피연산자의 숫자를 통해 진법을 유추할 수 있기에 사용한다.

ex) 17 이라면, 최소 8진법이상이라는 것을 알 수 있다. 왜냐하면 해당 진법에서 자리수를 올림하기 때문.

// 나올 수 있는 최소 진법
    static int getMaxDigit(String number) {
        int max = 0;
        
        for(Character c : number.toCharArray()) {
            if(Character.isDigit(c)) {
                max = Math.max(max, Character.getNumericValue(c));    
            }
        }
        
        return max;
    }

 

 

해당 메소드는 이미 결과값까지 주어진 수식에 대하여 내가 인자로 넣어준 진법으로 계산했을 때, 결과값이 일치하는지 확인하는 메소드이다.

해당 메소드를 통해, HashMap에 key는 진법, value는 개수를 통해 개수의 비교를 통해 정확하게 계산이 이루어진 진법은 어떤 것들인지 확인할 수 있다. 

// 주어진 수식에 대하여 진법을 활용해서 나온 결과값 비교
    static void solve(int check, String[] splits, Map<Integer, Integer> map) {
        
        if(!isValid(splits[0], check) || !isValid(splits[2], check)
            || !isValid(splits[4], check)) {
            return;
        }
        
        // 진법에 대한 계산 결과 일치를 map에 저장
        // for(int i = check; i <= 9; i++) {
        int a = Integer.parseInt(splits[0], check);
        int b = Integer.parseInt(splits[2], check);

        int c = splits[1].equals("+") ? a + b : a - b;
        String res = Integer.toString(c, check);

        if(res.equals(splits[4])) {
            map.put(check, map.getOrDefault(check, 0) + 1);
        }
        // }
           
    }

 

 

해당 메소드는 연산 결과값이 "X"인 수식에 대하여 연산 결과를 Set 배열에 저장하는 메소드로, 만약 result의 사이즈가 1보다 크다면, 해당 연산 결과는 진법 계산에서 여러 개의 결과값이 나올 수 있는 것이므로 우리가 진법을 정확히 유추할 수 없는 것이다.

따라서 이때는 결과값을 "?"로 담아야 한다.

// 여러 진법을 사용해서 나오는 결과값이 하나가 아닌 경우, 해당 수식의 결과값을 확정지을 수 없다.
    static void solveProblem(int check, String[] splits, Set<String> result) {
        
        if(!isValid(splits[0], check) || !isValid(splits[2], check)) {
            return;
        }
        
        int a = Integer.parseInt(splits[0], check);
        int b = Integer.parseInt(splits[2], check);
        int c = splits[1].equals("+") ? a + b : a - b;

        String ans = Integer.toString(c, check);

        result.add(ans);

    }

 

 

해당 부분이 우리가 구해야하는 수식에 대하여 result 값이 여러 개 나오거나, 하나만 나왔을 때, answer String 배열에 값을 담아주는 코드이다.

	if(result.size() != 1) {
                answer[i] = splits[0] + " " + splits[1] + " " + splits[2] + " "
                    + splits[3] + " " + "?";
            } else {
                Iterator<String> it = result.iterator();
                if(it.hasNext()) {
                    String value = it.next();
                    answer[i] = splits[0] + " " + splits[1] + " " + splits[2] + " "
                    + splits[3] + " " + value;
                }
            }

 

 

전체코드

아래는 전체 코드이다.

import java.util.*;
import java.io.*;

/**
* 가장 큰 자리수 구하기
* 연산했을 때의 결과값을 비교한다.
* 진법을 알았을 경우, 해당 진법을 활용해서 결과값 유추

*/


class Solution {
    
    // 해당 숫자가 진법에 맞는지 판별 여부
    static boolean isValid(String number, int check) {
        
        for(Character c : number.toCharArray()) {
            
            int value = Character.getNumericValue(c);
            
            if(value < 0 || value >= check) return false;
        }
        
        return true;
    }
    
    // 나올 수 있는 최소 진법
    static int getMaxDigit(String number) {
        int max = 0;
        
        for(Character c : number.toCharArray()) {
            if(Character.isDigit(c)) {
                max = Math.max(max, Character.getNumericValue(c));    
            }
        }
        
        return max;
    }
    
    // 주어진 수식에 대하여 진법을 활용해서 나온 결과값 비교
    static void solve(int check, String[] splits, Map<Integer, Integer> map) {
        
        if(!isValid(splits[0], check) || !isValid(splits[2], check)
            || !isValid(splits[4], check)) {
            return;
        }
        
        // 진법에 대한 계산 결과 일치를 map에 저장
        // for(int i = check; i <= 9; i++) {
        int a = Integer.parseInt(splits[0], check);
        int b = Integer.parseInt(splits[2], check);

        int c = splits[1].equals("+") ? a + b : a - b;
        String res = Integer.toString(c, check);

        if(res.equals(splits[4])) {
            map.put(check, map.getOrDefault(check, 0) + 1);
        }
        // }
           
    }
    
    // 여러 진법을 사용해서 나오는 결과값이 하나가 아닌 경우, 해당 수식의 결과값을 확정지을 수 없다.
    static void solveProblem(int check, String[] splits, Set<String> result) {
        
        if(!isValid(splits[0], check) || !isValid(splits[2], check)) {
            return;
        }
        
        int a = Integer.parseInt(splits[0], check);
        int b = Integer.parseInt(splits[2], check);
        int c = splits[1].equals("+") ? a + b : a - b;

        String ans = Integer.toString(c, check);

        result.add(ans);

    }
    
    public String[] solution(String[] expressions) {
        List<String> completeExpressions = new ArrayList<>();
        List<String> notCompleteExpressions = new ArrayList<>();
        
        Map<Integer, Integer> map = new HashMap<>();
        
        for(int i = 0; i < expressions.length; i++) {
            if (expressions[i].contains("X")) {
                notCompleteExpressions.add(expressions[i]);
            } else {
                completeExpressions.add(expressions[i]);
            }
        }
        
        // 숫자들로부터 가장 큰 진법 구하기
        int check = 0, min = 0;
        for(String complete : completeExpressions) {

            String[] splits = complete.split(" ");
            
            min = Math.max(getMaxDigit(splits[0]), 
                             Math.max(getMaxDigit(splits[2]), getMaxDigit(splits[4])));
            check = Math.max(check, min + 1);
        }
        
        // 완성된 수식으로부터 어떤 이진법이 올바른 결과값인지 확인하기
        for(String complete : completeExpressions) {
            String[] splits = complete.split(" ");
            
            for(int i = check; i <= 9; i++) {
                solve(i, splits, map);
            }
        }
        
        int nCheck = 0, nMin = 0;
        
        for(String nComplete : notCompleteExpressions) {
            String[] splits = nComplete.split(" ");
            
            nMin = Math.max(Math.max(getMaxDigit(splits[0]), 
                                     getMaxDigit(splits[2])), getMaxDigit(splits[4]));
            nCheck = Math.max(nCheck, nMin + 1);
        }
        
        String[] answer = new String[notCompleteExpressions.size()];
        
        for(int i = 0; i < notCompleteExpressions.size(); i++) {
            String[] splits = notCompleteExpressions.get(i).split(" ");
            
            Set<String> result = new HashSet<>();
            
            for(int j = nCheck; j <= 9; j++) {
                int value = map.getOrDefault(j, 0);
                if(value == completeExpressions.size()) {
                    solveProblem(j, splits, result);        
                }
            }
            
            if(result.size() != 1) {
                answer[i] = splits[0] + " " + splits[1] + " " + splits[2] + " "
                    + splits[3] + " " + "?";
            } else {
                Iterator<String> it = result.iterator();
                if(it.hasNext()) {
                    String value = it.next();
                    answer[i] = splits[0] + " " + splits[1] + " " + splits[2] + " "
                    + splits[3] + " " + value;
                }
            }
        }
      
        
        
        
        
        return answer;
    }
}