PGMS_수식복원하기 (Java)
[level 3] [PCCP 기출문제] 4번 / 수식 복원하기 - 340210
성능 요약
메모리: 96.1 MB, 시간: 3.00 ms
구분
코딩테스트 연습 > PCCP 기출문제
채점결과
정확성: 100.0
합계: 100.0 / 100.0
제출 일자
2025년 07월 30일 09:38:25
문제 설명
당신은 덧셈 혹은 뺄셈 수식이 여러 개 적힌 고대 문명의 유물을 찾았습니다. 이 수식들을 관찰하던 당신은 이 문명이 사용하던 진법 체계가 10진법이 아니라는 것을 알아냈습니다. (2 ~ 9진법 중 하나입니다.)
수식들 중 몇 개의 수식은 결괏값이 지워져 있으며, 당신은 이 문명이 사용하던 진법에 맞도록 지워진 결괏값을 채워 넣으려 합니다.
다음은 그 예시입니다.
<수식>
14 + 3 = 17
13 - 6 = X
51 - 5 = 44
X로 표시된 부분이 지워진 결괏값입니다.
51 - 5 = 44에서 이 문명이 사용하던 진법이 8진법임을 알 수 있습니다. 따라서 13 - 6 = X의 지워진 결괏값을 채워 넣으면 13 - 6 = 5가 됩니다.
다음은 또 다른 예시입니다.
<수식>
1 + 1 = 2
1 + 3 = 4
1 + 5 = X
1 + 2 = X
주어진 수식들에서 이 문명에서 사용한 진법이 6 ~ 9진법 중 하나임을 알 수 있습니다.
1 + 5 = X의 결괏값은 6진법일 때 10, 7 ~ 9진법일 때 6이 됩니다. 이와 같이 결괏값이 불확실한 수식은 ?를 사용해 1 + 5 = ?와 같이 결괏값을 채워 넣습니다.
1 + 2 = X의 결괏값은 6 ~ 9진법에서 모두 3으로 같습니다. 따라서 1 + 2 = X의 지워진 결괏값을 채워 넣으면 1 + 2 = 3이 됩니다.
덧셈 혹은 뺄셈 수식들이 담긴 1차원 문자열 배열 expressions가 매개변수로 주어집니다. 이때 결괏값이 지워진 수식들의 결괏값을 채워 넣어 순서대로 문자열 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
제한사항
- 2 ≤
expressions의 길이 ≤ 100expressions의 원소는"A + B = C"혹은"A - B = C"형태의 문자열입니다. A, B, C와 연산 기호들은 공백 하나로 구분되어 있습니다.- A, B는 음이 아닌 두 자릿수 이하의 정수입니다.
- C는 알파벳
X혹은 음이 아닌 세 자릿수 이하의 정수입니다. C가 알파벳X인 수식은 결괏값이 지워진 수식을 의미하며, 이러한 수식은 한 번 이상 등장합니다. - 결괏값이 음수가 되거나 서로 모순되는 수식은 주어지지 않습니다.
입출력 예
| expressions | result |
|---|---|
| ["14 + 3 = 17", "13 - 6 = X", "51 - 5 = 44"] | ["13 - 6 = 5"] |
| ["1 + 1 = 2", "1 + 3 = 4", "1 + 5 = X", "1 + 2 = X"] | ["1 + 5 = ?", "1 + 2 = 3"] |
| ["10 - 2 = X", "30 + 31 = 101", "3 + 3 = X", "33 + 33 = X"] | ["10 - 2 = 4", "3 + 3 = 10", "33 + 33 = 110"] |
| ["2 - 1 = 1", "2 + 2 = X", "7 + 4 = X", "5 - 5 = X"] | ["2 + 2 = 4", "7 + 4 = ?", "5 - 5 = 0"] |
| ["2 - 1 = 1", "2 + 2 = X", "7 + 4 = X", "8 + 4 = X"] | ["2 + 2 = 4", "7 + 4 = 12", "8 + 4 = 13"] |
입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
문제 예시와 같습니다.
입출력 예 #3
30 + 31 = 101에서 이 문명이 사용하던 진법이 6진법임을 알 수 있습니다. 따라서 10 - 2 = X, 3 + 3 = X, 33 + 33 = X의 지워진 결괏값을 채워 넣으면 10 - 2 = 4, 3 + 3 = 10, 33 + 33 = 110이 됩니다.
따라서 ["10 - 2 = 4", "3 + 3 = 10", "33 + 33 = 110"]을 return 해야 합니다.
입출력 예 #4
수식에 등장하는 숫자들을 통해 이 문명이 사용하던 진법이 8진법 혹은 9진법임을 알 수 있습니다. 2 + 2 = X와 5 - 5 = X의 지워진 결괏값을 채워 넣으면 8진법, 9진법에 관계없이 2 + 2 = 4, 5 - 5 = 0이 됩니다. 7 + 4 = X의 결괏값은 불확실하므로 지워진 결괏값을 채워 넣으면 7 + 4 = ?가 됩니다.
따라서 ["2 + 2 = 4", "7 + 4 = ?", "5 - 5 = 0"]을 return 해야 합니다.
입출력 예 #5
네 번째 예시와 같지만 5 - 5 = X가 8 + 4 = X로 바뀌었습니다. 이 문명이 사용하던 진법이 9진법임을 알 수 있으므로 7 + 4 = X와 8 + 4 = X의 지워진 결괏값을 채워 넣으면 7 + 4 = 12, 8 + 4 = 13이 됩니다.
따라서 ["2 + 2 = 4", "7 + 4 = 12", "8 + 4 = 13"]을 return 해야 합니다.
출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges
문제 풀이
-
진법 후보를 찾아야한다. 모든 수식(X 포함)에서 나타나는 최대 숫자를 찾아 최소 진법을 결정할 수 있다. ex) ‘7’이 등장하면 최소 8진법 이상이어야 함.
-
유효한 진법 필터링: X가 없는 완전한 수식들이 해당 진법에서 성립하는지 확인
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
import java.util.*;
class Solution {
static List<String> ansList = new ArrayList<>();
static List<Integer> ableRadix = new ArrayList<>();
public String[] solution(String[] expressions) {
int maxN = 0;
for(String e : expressions){
maxN = Math.max(maxN, getMaxFromExpression(e));
}
int minRadix = maxN + 1; // 최소 가능한 진법
for(int i=minRadix; i<=9; i++){
boolean flag = true;
for(String e : expressions){
if(!e.contains("X")){
if(!isValid(e, i)){
flag = false;
break;
}
}
}
// i진법이 유효할때
if(flag) ableRadix.add(i);
}
for(String e : expressions){
if(e.contains("X")){
String res = makeAns(e);
ansList.add(res);
}
}
return ansList.toArray(new String[0]);
}
// 전체식에서 최대숫자찾기
private int getMaxFromExpression(String e){
int m = 0;
String[] arr = e.split(" ");
m = Math.max(m, getMaxFromNumber(arr[0]));
m = Math.max(m, getMaxFromNumber(arr[2]));
if(!arr[4].equals("X")){
m = Math.max(m, getMaxFromNumber(arr[4]));
}
return m;
}
// 각 숫자 String에서 최대 숫자(0~9) 찾기
private int getMaxFromNumber(String str){
if(str.equals("X")) return 0;
int max = 0;
for(char c : str.toCharArray()){
int digit = c - '0';
max = Math.max(max, digit);
}
return max;
}
private boolean isValid(String e, int i){
String[] arr = e.split(" ");
// 숫자가 i진법에서 유효한지 체크 ex) 2진법에선 0,1 만 가능
if(!canParse(arr[0], i) || !canParse(arr[2], i) || !canParse(arr[4], i)) return false;
// a (+/-) b = c
int a = getNum(arr[0], i);
int b = getNum(arr[2], i);
int c = getNum(arr[4], i);
int cal = 0;
if(arr[1].equals("+")) cal = a + b;
else cal = a - b;
return c == cal;
}
private String makeAns(String e){ // X 채우기
String[] arr = e.split(" ");
Set<String> cals = new HashSet<>();
for(int i : ableRadix){
// i진법에서 숫자들이 유효한지 체크
if(!canParse(arr[0], i) || !canParse(arr[2], i)) continue;
int a = getNum(arr[0], i);
int b = getNum(arr[2], i);
int cal = 0;
if(arr[1].equals("+")) cal = a + b;
else cal = a - b;
cals.add(Integer.toString(cal, i));
}
if(cals.size() == 1) return e.replace("X", cals.stream().findFirst().orElse(null));
else return e.replace("X", "?");
}
private int getNum(String str, int radix){
if(str.equals("X")) return 0;
return Integer.parseInt(str, radix);
}
private boolean canParse(String str, int i){
if(str.equals("X")) return true;
for(char c : str.toCharArray()){
int digit = c - '0';
if(digit >= i) return false;
}
return true;
}
}