[Programmers] PCCP 기출문제 4번 / 수식 복원하기 - LV 3
접근
- 브루트 포스
풀이
대망의 PCCP 기출문제의 마지막 문제로 프로그래머스 레벨 3으로 측정된 문제이다. 레벨 3인만큼 다른 문제에 비해 코드가 조금 복잡하고 테스트케이스 3문제에 계속 런타임 에러가 나 디버깅하며 푸는데 2시간 넘게 거의 3시간 가까이 걸렸던 문제이다.
문제의 내용은 고대 문명의 수식을 복원하는 것인데 주어지는 수식은 2~9 진법 체계를 따르며 답이 적혀 있는 수식들을 분석해 답이 적혀있지 않은 수식의 답을 유추하는 문제이다. 올 수 있는 답이 여러 개 라면 정답 자리에? 를 출력하고 확실한 하나의 답만 만족한다면 그 답을 수식과 함께 출력한다.
List<String> completeExpression = new ArrayList<>();
List<String> problemExpression = new ArrayList<>();
for (String expression : expressions) {
if (!expression.contains("X")) {
completeExpression.add(expression);
} else {
problemExpression.add(expression);
}
}우선 답이 적혀 있지 않은 수식과 답이 있는 수식을 분리해 줬다.
String[] result = new String[problemExpression.size()];
Map<Integer, Integer> expressionMap = new HashMap<>();
expressionMap.put(2, 0); expressionMap.put(3, 0); expressionMap.put(4, 0);
expressionMap.put(5, 0); expressionMap.put(6, 0); expressionMap.put(7, 0);
expressionMap.put(8, 0); expressionMap.put(9, 0);결과 반환 형식이 문자열 배열이기 때문에 답이 적혀 있지 않은 수식의 개수 크기의 배열을 선언해 줬다. 그리고 진법 확인을 위한 맵을 선언 해줬는데 답이 있는 수식들을 분석하여 사용 가능한 진법을 체크하는 용도이다. 2진법부터 9진법 까지 기본 값 0으로 맵에 넣어주었는데 나중에 맵에서 값을 찾지 못해 발생하는 오류를 방지하기 위해 그냥 초기화해 넣어주었다.
int maxDigitInComplete = 0;
int minBaseInComplete = 0;
for (String ex : completeExpression) {
String[] parts = ex.split(" ");
int maxDigit= Math.max(getMaxDigit(parts[0]), getMaxDigit(parts[2]));
maxDigit = Math.max(maxDigit, getMaxDigit(parts[4]));
maxDigitInComplete = Math.max(maxDigit, maxDigitInComplete);
}
minBaseInComplete = maxDigitInComplete + 1;우선 답이 있는 수식을 분석해 제일 큰 숫자를 찾는 과정이다. 제일 큰 숫자를 기준으로 사용 가능한 진법을 찾아야 불필요한 과정도 줄어들고 오류 발생도 낮아진다. 제일 큰 숫자는 한자리를 기준으로 찾으며 예시에 14 + 3 = 17 수식의 경우 제일 큰 숫자인 7을 기준으로 진법을 결정한다. 이렇게 모든 답이 있는 수식을 순회하고 나서 나온 가장 큰 수가 7이라면 7보다 1 큰 8진법부터 가능하게 된다. 보통 진법의 경우 해당 숫자에 도달하게 되면 그 자리가 0으로 초기화되며 앞자리가 1 증가하는 구조로 7인 경우 7진법이 아니니 8진법부터 가능한 것이다.
private int getMaxDigit(String number) {
int maxDigit = 0;
for (char c : number.toCharArray()) {
if (Character.isDigit(c)) {
maxDigit = Math.max(maxDigit, Character.getNumericValue(c));
}
}
return maxDigit;
}위에 나온 제일 큰 숫자를 구하는 메서드이다. 문자열로 받은 숫자를 char로 한자리 씩 쪼개서 숫자인지 검사하고 숫자라면 최댓값을 갱신해 제일 큰 자리 값을 반환한다.
for (String ex : completeExpression) {
String[] parts = ex.split(" ");
String op = parts[1];
for (int base = minBaseInComplete; base <= 9; base++) {
check(parts, base, op, expressionMap);
}
}다음은 가능했던 진법들로 수식의 앞부분을 계산하여 결과와 동일한 값이 나오는지 확인하는 과정이다. 즉 앞의 숫자를 해당 진법으로 계산해 결과와 같은 값이 나온다면 그 수식에 사용된 진법이 어떤 것인지 알 수 있다.
private void check(String[] parts, int base, String op, Map<Integer, Integer> expressionMap) {
if (!isValidNumber(parts[0], base) || !isValidNumber(parts[2], base) || !isValidNumber(parts[4], base)){
return;
}
int num1 = Integer.parseInt(parts[0], base);
int num2 = Integer.parseInt(parts[2], base);
int res = op.equals("+") ? num1 + num2 : num1 - num2;
String ans = Integer.toString(res, base);
if (ans.equals(parts[4])) {
expressionMap.merge(base, 1, Integer::sum);
}
}진법을 확인하는 메서드로 만약에 해당 숫자가 입력하는 진법으로 계산이 가능한지 먼저 체크해 준다. 계산이 가능하다면 해당 진법의 숫자를 10진법으로 변환하여 계산해 준다. 자바의 Integer.parseInt() 메서드의 두 번째 파라미터로 진법 값을 넣을 수 있으며 현재 문자열에 들어있는 값이 5진법이라면 Integer.parseInt(num, 5)를 할 경우 5진법 문자열 값을 10진법 정수로 알아서 변환해 준다. 그러므로 수식에 있는 숫자는 이미 해당 진법으로 변환되어 있는 숫자기 때문에 10진법으로 변환해 준 뒤 값을 계산하고 다시 해당 진법으로 변환해 비교해 주어야 한다. 더해진 값을 다시 해당 진법으로 변환하고 수식의 결괏값과 비교해 동일하다면 해당 진법 값을 맵에 1 증가시켜 준다.
private boolean isValidNumber(String number, int base) {
for (char c : number.toCharArray()) {
int digit = Character.getNumericValue(c);
if (digit < 0 || digit >= base) {
return false;
}
}
return true;
}진법 변환이 가능한지 체크하는 메서드이다. 문자열로 이루어진 숫자를 char 단위로 쪼개 숫자인지 확인하고 해당 숫자가 음수이거나 진법보다 크거나 같을 경우, 예를 들어 7진법인데 7인 경우는 불가능한 경우이기 때문에 false를 리턴해준다.
이렇게 되면 답이 있는 수식에 대한 처리는 끝이 난다.
int maxDigitInProblem = 0;
int minBaseInProblem = 0;
for (String ex : problemExpression) {
String[] parts = ex.split(" ");
int maxDigit= Math.max(getMaxDigit(parts[0]), getMaxDigit(parts[2]));
maxDigitInProblem = Math.max(maxDigit, maxDigitInProblem);
}
minBaseInProblem = maxDigitInProblem + 1;이제 답이 없는 수식을 처리해야 한다. 답이 있던 수식과 똑같이 제일 큰 숫자를 찾아준다.
for (int i = 0; i < problemExpression.size(); i++) {
String[] parts = problemExpression.get(i).split(" ");
String op = parts[1];
Set<String> resultSet = new HashSet<>();
for (int base = minBaseInProblem; base <= 9; base++) {
int value = expressionMap.get(base);
if (value == completeExpression.size()) {
checkSet(parts, base, op, resultSet);
}
}답이 없는 수식에는 Set을 사용하는데 답이 여러 개인 경우? 를 출력해야 하므로 답이 모두 동일한 경우를 걸러주기 위해 사용했다. 답이 없는 수식에서 제일 큰 수 + 1 값을 또 진법 베이스로 사용하는데 base 값을 통해 맵에서 해당 진법이 답이 있는 수식에서 몇 번 사용되었는지 가져온다. 값을 들고 온 이유는 이 문제에서는 모든 수식이 해당 진법을 따라야 하므로 답이 있는 수식이 모두 해당 진법으로 계산이 가능한 경우에만 답이 없는 수식을 계산하게 된다.
private void checkSet(String[] parts, int base, String op, Set<String> resultSet) {
if (!isValidNumber(parts[0], base) || !isValidNumber(parts[2], base)) {
return;
}
int num1 = Integer.parseInt(parts[0], base);
int num2 = Integer.parseInt(parts[2], base);
int res = op.equals("+") ? num1 + num2 : num1 - num2;
String ans = Integer.toString(res, base);
resultSet.add(ans);
}답이 없는 수식을 계산하는 메서드이다. 해당 진법이 맞는지를 검사하고 맞다면 동일하게 10진수로 변환하여 계산해 준 뒤 다시 해당 진법으로 변환하여 Set에 넣어준다.
if (resultSet.size() != 1) {
result[i] = parts[0] + " " + parts[1] + " " + parts[2] + " " + parts[3] + " " + "?";
} else {
Iterator<String> it = resultSet.iterator();
if (it.hasNext()) {
String value = it.next();
result[i] = parts[0] + " " + parts[1] + " " + parts[2] + " " + parts[3] + " " + value;
}
}
}
return result;그렇게 가능한 모든 진법을 순회하며 계산이 끝나면 만약 해당 수식이 여러 진법으로 계산이 가능하고 답이 다 다르다면 Set의 크기가 1보다 크기 때문에 마지막에? 를 붙여 반환하게 되고 해당 수식이 한 가지 진법으로만 계산할 수 있던가 여러 가지 진법으로 계산해도 값이 다 동일할 경우 Set에 들어있는 한 개의 값을 마지막에 붙여 반환하게 된다.
전체 코드
import java.util.*;
class Solution {
public String[] solution(String[] expressions) {
List<String> completeExpression = new ArrayList<>();
List<String> problemExpression = new ArrayList<>();
for (String expression : expressions) {
if (!expression.contains("X")) {
completeExpression.add(expression);
} else {
problemExpression.add(expression);
}
}
String[] result = new String[problemExpression.size()];
Map<Integer, Integer> expressionMap = new HashMap<>();
expressionMap.put(2, 0); expressionMap.put(3, 0); expressionMap.put(4, 0);
expressionMap.put(5, 0); expressionMap.put(6, 0); expressionMap.put(7, 0);
expressionMap.put(8, 0); expressionMap.put(9, 0);
int maxDigitInComplete = 0;
int minBaseInComplete = 0;
for (String ex : completeExpression) {
String[] parts = ex.split(" ");
int maxDigit= Math.max(getMaxDigit(parts[0]), getMaxDigit(parts[2]));
maxDigit = Math.max(maxDigit, getMaxDigit(parts[4]));
maxDigitInComplete = Math.max(maxDigit, maxDigitInComplete);
}
minBaseInComplete = maxDigitInComplete + 1;
for (String ex : completeExpression) {
String[] parts = ex.split(" ");
String op = parts[1];
for (int base = minBaseInComplete; base <= 9; base++) {
check(parts, base, op, expressionMap);
}
}
int maxDigitInProblem = 0;
int minBaseInProblem = 0;
for (String ex : problemExpression) {
String[] parts = ex.split(" ");
int maxDigit= Math.max(getMaxDigit(parts[0]), getMaxDigit(parts[2]));
maxDigitInProblem = Math.max(maxDigit, maxDigitInProblem);
}
minBaseInProblem = maxDigitInProblem + 1;
for (int i = 0; i < problemExpression.size(); i++) {
String[] parts = problemExpression.get(i).split(" ");
String op = parts[1];
Set<String> resultSet = new HashSet<>();
for (int base = minBaseInProblem; base <= 9; base++) {
int value = expressionMap.get(base);
if (value == completeExpression.size()) {
checkSet(parts, base, op, resultSet);
}
}
if (resultSet.size() != 1) {
result[i] = parts[0] + " " + parts[1] + " " + parts[2] + " " + parts[3] + " " + "?";
} else {
Iterator<String> it = resultSet.iterator();
if (it.hasNext()) {
String value = it.next();
result[i] = parts[0] + " " + parts[1] + " " + parts[2] + " " + parts[3] + " " + value;
}
}
}
return result;
}
private void checkSet(String[] parts, int base, String op, Set<String> resultSet) {
if (!isValidNumber(parts[0], base) || !isValidNumber(parts[2], base)) {
return;
}
int num1 = Integer.parseInt(parts[0], base);
int num2 = Integer.parseInt(parts[2], base);
int res = op.equals("+") ? num1 + num2 : num1 - num2;
String ans = Integer.toString(res, base);
resultSet.add(ans);
}
private int getMaxDigit(String number) {
int maxDigit = 0;
for (char c : number.toCharArray()) {
if (Character.isDigit(c)) {
maxDigit = Math.max(maxDigit, Character.getNumericValue(c));
}
}
return maxDigit;
}
private boolean isValidNumber(String number, int base) {
for (char c : number.toCharArray()) {
int digit = Character.getNumericValue(c);
if (digit < 0 || digit >= base) {
return false;
}
}
return true;
}
private void check(String[] parts, int base, String op, Map<Integer, Integer> expressionMap) {
if (!isValidNumber(parts[0], base) || !isValidNumber(parts[2], base) || !isValidNumber(parts[4], base)){
return;
}
int num1 = Integer.parseInt(parts[0], base);
int num2 = Integer.parseInt(parts[2], base);
int res = op.equals("+") ? num1 + num2 : num1 - num2;
String ans = Integer.toString(res, base);
if (ans.equals(parts[4])) {
expressionMap.merge(base, 1, Integer::sum);
}
}
}만약 문제의 고려사항이 답이 없는 수식에 여러 답이 가능할 때?를 출력하는 것이 아니라 답이 없는 수식들 까지 고려하여 그중 한 가지의 값만 정답을 구하는 문제였다면 끔찍했을 거 같다.
'알고리즘 > 코딩테스트-Programmers' 카테고리의 다른 글
| [Programmers] 택배 배달과 수거하기 Java (2) | 2024.09.20 |
|---|---|
| [Programmers] [1차] 캐시 - JAVA (1) | 2024.09.19 |
| [Programmers] PCCP 기출문제 3번 / 충돌위험 찾기 JAVA (1) | 2024.09.17 |
| [Programmers] PCCE 기출문제 10번 / 공원 Java (1) | 2024.09.16 |
| [Programmers] PCCP 기출문제 2번 / 퍼즐 게임 챌린지 Java (1) | 2024.09.16 |