boj.kr/1339 단어 수학 (gold4) 파이썬 풀이

오답풀이

- 제시된 4개 테스트 케이스는 통과했으나 제출시 틀린 케이스가 있었다.

N = int(input())
words = [input() for _ in range(N)]
words = sorted(words, key=lambda x: len(str(x)), reverse=True)
matches = [0 for _ in range(10)]
pointers = []

import heapq

for i in range(len(words)):
    heapq.heappush(pointers, (-len(words[i]), i, -len(words[i])))

mIdx = 9
while mIdx >= 0:
    (pointer, wIdx, len) = heapq.heappop(pointers)
    (pointer, wIdx, len) = (-pointer, wIdx, -len)
    if words[wIdx][len-pointer] in matches:
        pointer -= 1
        heapq.heappush(pointers, (-pointer, wIdx, -len))
    else:
        matches[mIdx] = words[wIdx][len-pointer]
        pointer -= 1
        heapq.heappush(pointers, (-pointer, wIdx, -len))
        mIdx = mIdx - 1

    tot = 0
    for item in pointers:
        tot += item[0]
    if tot == 0:
        break

numbers = [0]
for word in words:
    for c in word:
        word = word.replace(str(c), str(matches.index(c)))
    numbers.append(int(word))

print(sum(numbers))

 

정답풀이 

- 단어의 각 문자를 숫자로 바꾸는 경우 자릿수가 가장 큰 것에 우선적으로 큰 수를 부여한다. 

- 그 문자가 정확히 무엇이엇는지 기억하는 것이 아니라 총합이 최댓값이 되도록 하는 것이 목표이다. (각 문자는 인덱스로 구분만 되면 되고, 각 문자의 자릿수를 정확히 알고 계산해야 한다.)

- enumerate를 사용해 리스트를 순회하면 인덱스와 값을 동시에 얻을 수 있다. (마지막 인덱스부터 순회하면 각 문자의 자리수를 얻을 수 있다.)

- 가장 큰 자리수로 저장된 문자부터 큰 수를 부여해 총합을 계산한다.

 

1. 각 문자열을 각 문자별로 0-25의 정수로 치환

2. 알파벳 배열을 26개의 0으로 초기화

3. 각 문자열을 뒤집어 enumerate 으로 인덱스와 문자를 정수로 변환한 값(i, c)을 조회하고 순회시마다 아래를 반복

3.1. 알파벳 배열[c] 값에 i**10을 더하기

4. 알파벳 배열을 내림차순으로 정렬

5. 알파벳 배열의 0번 요소부터 8번 요소까지 9부터 1까지 정수를 큰수부터 차례대로 각각 곱한 값을 누적

6. 누적합을 출력

 

N = int(input())
words = []
for _ in range(N):
    words.append(list(map(lambda c: ord(c)-65, input())))

alphabets = [0] * 26
for word in words:
    for i, c in enumerate(word[::-1]):
        alphabets[c] += 10 ** i
alphabets.sort(reverse=True)

n = 9
tot = 0
for i in range(9):
    tot += n*alphabets[i]
    n -= 1

print(tot)

 

ord(문자) 함수를 사용하면 해당하는 아스키코드 정수값을 얻을 수 있다.

문자열을 [::-1] 의 인덱스로 조회하면 뒤집힌 문자열의 결과를 얻을 수 있다.