1339번 - 단어 수학

1. 단어 수학

A. 📜 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

B. 💡 내 답안

a. 😅 1차 시도 (실패)

n = int(input())

arrays = []
max_len = 0

for _ in range(n):
    temp = input()
    arrays.append(temp)
    max_len = max(max_len, len(temp))

# 초기에 리스트의 원소 10개를 사용하지 않는 문자 'Z'로 초기화
checked = ['Z'] * 10

"""
문자열이 "GCF", "ACDEB"라면 
  GCF
ACDEB
이런 구조로 만들어서, 왼쪽 문자부터 checked 리스트에 (오른쪽 인덱스 -> 왼쪽 인덱스) 순서로 집어넣는다.
A = checked[9]
C = checked[8]
G = checked[7]
D = checked[6]
C = x (이미 checked 리스트에 존재하여 패스)
E = checked[5]
F = checked[4]
B = checked[3]
"""
for i in range(max_len):
    for array in arrays:
        if len(array) >= max_len - i:
            index = len(array) - max_len + i
            for j in range(9, -1, -1):
                if array[index] not in checked:
                    if checked[j] == 'Z':
                        checked[j] = array[index]
                        # print(checked)
                        break
                else:
                    break

new_arrays = []

"""
문자열을 "GCF", "ACDEB" -> 784, 98653로 치환해야함.
checked = ['Z', 'Z', 'Z', 'B', 'F', 'E', 'D', 'G', 'C', 'A']
문자열을 문자 단위로 쪼개서 chekced 리스트의 인덱스 번호를 가져옴.
그리고 문자열로 변환하여 concat을 함
"""
for array in arrays:
    new_string = ''
    for string in array:
        new_string += str(checked.index(string))
    new_arrays.append(new_string)

answer = 0

"""
원하는 결과는 주어진 단어의 합의 최댓값이라서 각 원소를 int로 변환하고 합함.
"""
for num in new_arrays:
    answer += int(num)

print(answer)

"""
완벽하게 풀었다고 생각하였으나, 이런 방식으로 푸는 문제가 아니었음.
# 반례
10
ABB
BB
BB
BB
BB
BB
BB
BB
BB
BB
정답값 : 1790
출력값 : 1780
"""

"""
이 문제는 문자열(알파벳)의 위치에 따라 숫자로 변환하는 것이 아니라,
문자열의 발생 횟수를 계산하여, 가장 많이 발생한 순서부터 9~0 순서로 곱하는 문제였음... 
"""

b. 😊 2차 시도 (성공)

n = int(input())

arrays = []

for _ in range(n):
    temp = input()
    arrays.append(temp)

string_dict = dict()

for array in arrays:
    for i in range(len(array)):
        # 문자열을 key로 갖는 dict value에 현재 자리수만큼 더한다.
        if array[i] not in string_dict:
            string_dict[array[i]] = 10 ** (len(array) - i - 1)
        else:
            string_dict[array[i]] += 10 ** (len(array) - i - 1)

# 딕셔너리를 value 기준으로 내림차순 정렬하여 리스트로 만든다.
sort_dict = sorted(string_dict.items(), key=lambda x:x[1], reverse=True)

answer = 0

for i in range(9, -1, -1):
    k = 9 - i
    if len(sort_dict) > k:
        answer += i * sort_dict[k][1]

print(answer) 

a. 🙄 회고

내 풀이

  • 처음에는 문자열 파싱 문제인줄 알았다. 그런데 알고보니 수학 문제였다.

반성

  • 단순하게 제시된 예제와 문제를 1차원적으로 생각하고 판단했다.
  • 사실 문제를 이해하고 좀 더 다양한 예제들을 생각해봤어야 한다.

결론

  • 앞으로는 제시된 예제 말고도 다양한 예제들을 생각하는 연습을 해보자.

C. 🧐 문제 해설

이해한 내용을 바탕으로 작성했습니다.

a. 처음 풀이

주석으로 작성한 방식대로 풀었다.

문자열 파싱이라 생각하고 신나게 풀었더니 틀렸다..

b. 두번째 풀이

각 문자들의 빈도를 먼저 파악하고 숫자(9~0)을 할당한다.

빈도파악은 해당하는 문자열의 자리수를 누적해서 더해주는 방식을 이용한다.

ABC라면 A는 100, B는 10, C는 1

그리고 파이썬의 딕셔너리는 정렬이 가능하다. 따라서 sorted() 빌트인 함수로 정렬을 진행하여 list를 반환받는다.

다른 언어로 진행한다면, 리스트를 만들어서 'string' - 'a' 이런 방식으로 몇 번째 인덱스인지를 알아내서 진행하면 된다.

만약 위 방식을 파이썬으로 구현하려면 ord('string') - ord('a') 으로 진행하면 몇 번째 인덱스인지를 구할 수 있다.

참고문헌

baekjoon. 1339번: 단어 수학 (acmicpc.net). Baekjoon. (accessed Dec 15, 2021)

이 글이 도움이 되었나요?

신고하기
0분 전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.