[level 3] [PCCP 기출문제] 4번 / 수식 복원하기 - 340210

문제 링크

성능 요약

메모리: 9.4 MB, 시간: 1.51 ms

구분

코딩테스트 연습 > PCCP 기출문제

채점결과

정확성: 100.0
합계: 100.0 / 100.0

문제 설명

당신은 덧셈 혹은 뺄셈 수식이 여러 개 적힌 고대 문명의 유물을 찾았습니다. 이 수식들을 관찰하던 당신은 이 문명이 사용하던 진법 체계가 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의 길이 ≤ 100
  • expressions의 원소는 "A + B = C" 혹은 "A - B = C" 형태의 문자열입니다. A, B, C와 연산 기호들은 공백 하나로 구분되어 있습니다.
  • A, B는 음이 아닌 두 자릿수 이하의 정수입니다.
  • C는 알파벳 X 혹은 음이 아닌 세 자릿수 이하의 정수입니다. C가 알파벳 X인 수식은 결괏값이 지워진 수식을 의미하며, 이러한 수식은 한 번 이상 등장합니다.
  • 결괏값이 음수가 되거나 서로 모순되는 수식은 주어지지 않습니다.

입출력 예

입출력 예 설명

입출력 예 #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

문제 풀이

문제 분석

이 문제는 덧셈 또는 뺄셈 수식들이 담긴 배열 expressions를 입력받아, 고대 문명이 사용하던 진법(2~9진법 중 하나)을 알아내고, 결과값이 'X'로 지워진 수식들의 결과값을 채워 넣는 문제입니다.

입력 expressions는 ["A + B = C"] 또는 ["A - B = C"] 형태의 문자열 배열입니다. 여기서 A, B는 두 자릿수 이하의 숫자이고, C는 세 자릿수 이하의 숫자이거나 'X'입니다. 'X'는 지워진 결과값을 의미하며, 이러한 수식은 항상 하나 이상 등장합니다. 문제의 핵심은 다음과 같습니다:

1. 진법 찾기: 'X'가 아닌, 결과값이 명시된 수식들을 통해 고대 문명이 사용하던 정확한 진법 또는 가능한 진법들의 범위를 찾아야 합니다.
2. 결과값 채우기: 찾아낸 진법을 기반으로 'X' 수식의 결과값을 계산합니다.
3. 불확실성 처리: 만약 여러 진법이 가능하고, 어떤 'X' 수식의 결과가 이 가능한 진법들에 따라 달라진다면, 해당 결과는 '?'로 표시해야 합니다. 모든 가능한 진법에서 결과가 동일하다면 그 값을 채워 넣습니다.
4. 제한: 결괏값이 음수가 되거나 서로 모순되는 수식은 주어지지 않습니다.

접근 방법

이 문제를 해결하기 위해 다음과 같은 단계별 접근 방식을 선택합니다.

1. 데이터 분류 및 기본 진법 정보 추출: 주어진 expressions에서 결과값이 있는 수식과 'X'인 수식을 분리합니다. 또한, 수식에 나타나는 모든 숫자 문자(0~9)를 수집하여, 최소한 몇 진법 이상이어야 하는지 (max(decimal) + 1 진법)를 파악합니다. 예를 들어, 수식에 '7'이라는 숫자가 있으면 최소한 8진법 이상이어야 합니다.
2. 유효 진법 식별: 2진법부터 9진법까지 모든 가능한 진법을 순회하면서, 결과값이 명시된 수식들이 해당 진법에서 올바르게 성립하는지 검증합니다. 모든 명시된 수식을 만족하는 진법들을 '유효 진법'으로 간주합니다. collections.Counter를 사용하여, 각 진법이 몇 개의 명시된 수식에서 유효했는지 세고, 모든 명시된 수식의 개수와 일치하는 진법만을 최종 유효 진법으로 선택합니다.
3. 'X' 수식 결과 계산 및 불확실성 처리: 식별된 유효 진법들을 사용하여 'X' 수식의 결과값을 계산합니다. 각 'X' 수식에 대해, 유효 진법별로 계산된 결과값들을 저장하고, 그 결과값들이 모두 동일한지 확인합니다.
   • 모든 유효 진법에서 결과값이 동일하다면 해당 값으로 채웁니다.
   • 결과값이 진법에 따라 달라진다면 '?'로 채웁니다.
   • 만약 유효 진법이 하나도 찾아지지 않았다면, 문제의 조건상 2~9진법 중 하나가 반드시 존재한다는 의미이므로, 가능한 모든 진법(최소 진법 ~ 9진법)을 다시 검토하여 'X' 수식의 결과를 계산하고 불확실성을 처리합니다.
4. 진법 변환 보조 함수: 문자열로 된 숫자를 특정 진법의 10진수로 변환하는 로직과, 10진수 숫자를 특정 진법의 문자열로 변환하는 보조 함수 (decimals)가 필요합니다.

구현 설명

1단계: 수식 분류 및 숫자 정보 추출

• 입력 expressions 배열을 순회하면서 각 수식(i)을 처리합니다.
• i[-1] == "X" 조건을 사용하여 결과값이 지워진 수식(answer_check)과 결과값이 있는 수식(answer_list)을 각각의 리스트에 추가합니다.
• 수식 문자열 내에서 숫자(isdigit())인 모든 문자를 decimal이라는 set에 추가합니다. 이 set을 통해 수식에 사용된 가장 큰 숫자 문자를 찾을 수 있으며, 이는 최소한 몇 진법부터 탐색해야 하는지(int(max(decimal)) + 1)를 결정하는 데 사용됩니다.
• answer_list와 answer_check에 저장된 문자열 수식들을 split() 함수를 이용하여 공백을 기준으로 분리하여 answer_lists와 answer_checks에 저장합니다. 이는 이후 숫자를 진법 변환하기 쉽게 만듭니다. data_check는 answer_check에 있는 각 'X' 수식에 대해 가능한 결과값들을 임시로 저장할 2차원 리스트입니다.

2단계: 유효한 진법 식별

• int(max(decimal)) + 1 (예: '7'이 max_digit이면 8진법부터)부터 9진법까지 모든 m (후보 진법)에 대해 반복합니다.
• answer_lists (결과값이 명시된 수식들)의 각 수식을 순회하며 해당 진법 m에서 수식이 유효한지 검증합니다.
  • 수식 answer_lists[i]의 각 숫자 문자열(예: "14", "3", "17")을 m 진법으로 해석하여 10진수 값으로 변환합니다. 변환 로직은 각 자릿수 d에 대해 d * m**(자릿수_위치)를 더하는 방식입니다.
  • 변환된 10진수 값들로 실제 덧셈 또는 뺄셈 연산을 수행하고, 그 결과가 수식의 10진수 결과값과 일치하는지 확인합니다.
  • 일치하면 해당 진법 m을 true_decimal 리스트에 추가합니다.
• 모든 m 진법과 모든 answer_lists 수식에 대한 검증이 끝나면, true_decimal 리스트에 저장된 진법들의 빈도를 collections.Counter를 사용하여 계산합니다.
• len(answer_list) (명시된 결과가 있는 수식의 총 개수)와 빈도수가 일치하는 진법들만 true_decimals 리스트에 저장합니다. 이들은 모든 명시된 수식을 만족하는 최종 유효 진법들입니다.
• 특별히 max(decimal)이 '8'인 경우, 9진법도 유효 진법으로 추가하는 조건이 있습니다. 이는 range(int(max(decimal))+1, 10) 범위 설정이 max(decimal)이 '8'일 때 9진법을 포함하지 않을 수 있는 가능성을 고려한 것으로 보입니다.

3단계: 'X' 수식 결과 계산 및 불확실성 처리

• set(true_decimals) (중복 제거된 유효 진법들)에 있는 각 m 진법에 대해 반복합니다.
• answer_checks (결과값이 'X'인 수식들)의 각 수식을 순회하며 해당 진법 m에서 결과값을 계산합니다.
  • 'X' 수식의 좌항과 우항 숫자 문자열을 m 진법으로 해석하여 10진수 값으로 변환합니다.
  • 연산(+ 또는 -)을 수행하여 10진수 결과값을 얻습니다.
  • 이 10진수 결과값을 m 진법 문자열로 변환하기 위해 별도로 정의된 decimals(n, base) 함수를 호출합니다. 이 함수는 10진수 n을 base 진법 문자열로 변환하여 반환합니다.
  • 계산된 m 진법 결과 문자열을 data_check[i] 리스트에 추가합니다.
• 만약 true_decimals가 비어있다면, 이는 모든 2~9진법이 유효한 진법 후보가 될 수 있다는 의미입니다. 이 경우 max(decimal)+1부터 9까지의 모든 진법을 m으로 간주하고, 위와 동일한 방식으로 각 X 수식의 결과를 data_check에 추가합니다.
• 최종적으로 data_check 리스트를 기반으로 answer_checks의 X 부분을 채웁니다. 각 data_check[i] (특정 'X' 수식에 대한 가능한 결과값들의 리스트)를 set()으로 변환하여 크기를 확인합니다.
  • len(set(data_check[i])) == 1이면, 모든 유효 진법에서 결과값이 동일하므로, 그 유일한 값을 answer_checks[i][4] (원래 'X' 위치)에 할당합니다.
  • len(set(data_check[i])) > 1이면, 결과값이 진법에 따라 다르므로 answer_checks[i][4]에 '?'를 할당합니다.

4단계: 최종 결과 포맷팅

• answer_checks는 ['A', '+', 'B', '=', 'C']와 같은 형태의 리스트들의 리스트입니다.
• ' '.join(sublist)를 사용하여 각 내부 리스트를 다시 공백으로 구분된 문자열로 변환하고, 이들을 result 리스트에 담아 반환합니다.

decimals 함수 (decimals(n, base))

• 이 함수는 10진수 n을 입력받아 base 진법으로 변환된 문자열을 반환합니다.
• n이 0이면 "0"을 반환합니다.
• while n: 루프를 돌면서 n을 base로 나눈 나머지를 digits 리스트에 추가하고, n을 base로 나눈 몫으로 업데이트합니다. 이 과정은 base 진법의 각 자릿수를 역순으로 얻는 과정입니다.
• digits 리스트를 뒤집고 ([::-1]), 각 숫자를 문자열로 변환한 후 ''.join()을 사용하여 하나의 문자열로 합쳐 반환합니다.

⏱복잡도 분석

• 입력 크기: expressions의 길이 E (최대 100), 각 수식 문자열의 최대 길이 L (대략 15문자, A,B 최대 2자리, C 최대 3자리, 공백 및 연산자 포함). 숫자의 최대 자릿수 D (최대 3자리).

• 진법 범위: 2부터 9까지, 총 8개의 진법 (Max_Base_Range = 8).

• 숫자 변환: 10진수 N을 base 진법으로 변환하거나 그 반대로 변환하는 데 필요한 연산 횟수는 숫자의 자릿수(로그 스케일)에 비례합니다. 예를 들어, log_base(N) 연산이 필요하며, 최대 3자리 숫자이므로 이 값은 매우 작은 상수입니다.

• 시간 복잡도:

  • 초기 전처리 (수식 분류 및 숫자 정보 추출): expressions 배열을 한 번 순회합니다. 각 수식은 L 길이이므로, split() 및 숫자 추출 작업은 O(L) 시간이 걸립니다. 따라서 O(E * L).
  • 유효 진법 식별:
    • Max_Base_Range (8개) 진법에 대해 반복합니다.
    • answer_lists (최대 E개 수식)를 순회합니다.
    • 각 수식 내 3개의 숫자 문자열(A, B, C)을 10진수로 변환합니다. 각 변환은 숫자의 최대 자릿수 D에 비례하는 연산이 필요합니다 (예: int(digit) * m**power). 따라서 O(D)
    • 종합적으로 O(Max_Base_Range * E * D).
  • 'X' 수식 결과 계산:
    • Max_Base_Range (8개) 진법 또는 true_decimals의 수(최대 8개)에 대해 반복합니다.
    • answer_checks (최대 E개 수식)를 순회합니다.
    • 각 수식 내 2개의 숫자(A, B)를 10진수로 변환하고, decimals 함수로 다시 특정 진법 문자열로 변환합니다. decimals 함수는 O(log_base(N)) 시간이 걸립니다.
    • 종합적으로 O(Max_Base_Range * E * D * log_base(N)).
  • 최종 포맷팅: answer_checks (최대 E개)를 순회하며 set 생성 및 ' '.join() 작업을 합니다. O(E * L).

  D와 log_base(N)은 문제의 제한 사항(숫자가 최대 3자리)을 고려할 때 매우 작은 상수입니다. 따라서 전체 시간 복잡도는 O(E * Max_Base_Range * D * log_base(N))로 볼 수 있으며, 이는 E와 상수에 비례하므로 매우 효율적입니다.

• 공간 복잡도:

  • answer_list, answer_check, answer_lists, answer_checks: O(E * L) (수식 문자열의 총 길이에 비례)
  • decimal: 최대 L (수식 내 고유한 숫자 문자 수)에 비례하므로 O(L).
  • true_decimal: 최악의 경우 E * Max_Base_Range개의 진법을 저장할 수 있으므로 O(E * Max_Base_Range).
  • data_check: E개의 'X' 수식에 대해, 각 수식당 Max_Base_Range개의 결과 문자열을 저장합니다. 각 결과 문자열의 길이는 log_base(N) (상수)이므로, O(E * Max_Base_Range * log_base(N)).

  따라서 전체 공간 복잡도는 O(E * L + E * Max_Base_Range * log_base(N)) 로 볼 수 있으며, 이는 문제의 제한 사항 내에서 충분히 적은 양입니다.

핵심 포인트

1. 진법 탐색 및 검증: 2부터 9까지 모든 진법을 순회하며, 결과값이 이미 주어진 수식들을 통해 유효한 진법을 찾아내는 것이 중요합니다. collections.Counter를 활용하여 모든 기지의 수식을 만족하는 진법을 정확히 식별하는 로직이 핵심입니다.
2. 진법 변환 구현: 문자열로 된 숫자를 특정 진법의 10진수로 변환하는 로직 (각 자릿수에 진법의 거듭제곱을 곱하여 더하는 방식)과, 10진수를 특정 진법의 문자열로 변환하는 decimals 함수 (나눗셈과 나머지 연산을 활용하는 방식)를 정확히 구현하는 것이 문제입니다.
3. 불확실한 결과 ('?') 처리: 'X'로 표시된 수식의 결과가 유효한 진법에 따라 달라질 수 있다는 점을 고려해야 합니다. 모든 유효 진법에서 계산된 결과값들이 동일한지 set을 활용하여 확인하고, 다르면 '?'로 표시하는 조건부 로직이 문제의 요구사항을 만족하는 중요한 부분입니다.

풀이 코드

from collections import Counter

def solution(expressions):
    answer_list = []
    answer_check = []
    true_decimal = []
    decimal = set()
    for i in expressions:
        if i[-1]=="X":
            answer_check.append(i)
        else:
            answer_list.append(i)
        
        for j in range(len(i)):
            if i[j].isdigit():
                decimal.add(i[j])
    answer_lists = []
    answer_checks= []
    data_check = [[] for i in range(len(answer_check))]
    for i in range(len(answer_list)):
        answer_lists.append(answer_list[i].split())
    for i in range(len(answer_check)):
        answer_checks.append(answer_check[i].split())
    
    for m in range(int(max(decimal))+1,10):
        for i in range(len(answer_lists)):
            data = [int(answer_lists[i][0]),int(answer_lists[i][2]),int(answer_lists[i][4])]
            for j in range(len(answer_lists[i])):
                sum=0
                a = len(answer_lists[i][j])
                if a >= 2:
                    start = a-1
                    for k in range(a):
                        sum += int(answer_lists[i][j][k:k+1])*m**start
                        start-=1
                    data[int(j/2)] = sum

            if (answer_lists[i][1] == '+'):
                if(data[0] + data[1] == data[2]):
                    true_decimal.append(m)
            else:
                if(data[0] - data[1] == data[2]):
                    true_decimal.append(m)
    
    counter = Counter(true_decimal)
    
    true_decimals = [num for num, count in counter.items() if count == len(answer_list)]
    if max(decimal) == '8':
        true_decimals.append(9)
        
    for m in set(true_decimals):
        print("decimal = " + str(m))
        for i in range(len(answer_checks)):
            data = [int(answer_checks[i][0]),int(answer_checks[i][2])]
            for j in range(len(answer_checks[i])):
                sum=0
                a = len(answer_checks[i][j])
                if a >= 2:
                    start = a-1
                    for k in range(a):
                        sum += int(answer_checks[i][j][k:k+1])*m**start
                        start-=1
                    data[int(j/2)] = sum

            if (answer_checks[i][1] == '+'):
                data_check[i].append(str(decimals(data[0]+data[1],m)))
            else:
                data_check[i].append(str(decimals(data[0]-data[1],m)))
    
    if len(true_decimals) == 0:
        for i in range(len(answer_checks)):
            data = [int(answer_checks[i][0]),int(answer_checks[i][2])]
            for m in range(int(max(decimal))+1,10):
                for j in range(len(answer_checks[i])):
                    sum=0
                    a = len(answer_checks[i][j])
                    if a >= 2:
                        start = a-1
                        for k in range(a):
                            sum += int(answer_checks[i][j][k:k+1])*m**start
                            start-=1
                        data[int(j/2)] = sum
                if answer_checks[i][1] == '+':
                    data_check[i].append(str(decimals(data[0]+data[1],m)))
                elif answer_checks[i][1] == '-':
                    data_check[i].append(str(decimals(data[0]-data[1],m)))
    print(data_check)

    for i in range(len(data_check)):
        if len(set(data_check[i])) == 1:
            answer_checks[i][4] = str(data_check[i][0])
        else:
            answer_checks[i][4] = '?'
    
    print(answer_checks)
    result = [' '.join(sublist) for sublist in answer_checks]

    return result

def decimals(n, base):
    if n== 0:
        return 0
    digits = []
    while n:
        digits.append(int(n % base))
        n //= base
    
    return ''.join(str(x) for x in digits[::-1])