[백준][그리디] 단어 수학

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

https://www.acmicpc.net/problem/1339

1339번: 단어 수학

 

내가 작성한 코드

import sys
from collections import defaultdict, deque, Counter

read = sys.stdin.readline

N = int(read().rstrip())
mx = 9
number = deque()
AtoN = defaultdict()
priority = defaultdict(lambda: [0] * 8)

# set radix
for _ in range(N):
    idx = len(number) - 1
    for i, alpha in enumerate(reversed(list(read().rstrip()))):
        if idx < 0:
            number.appendleft([alpha])
        else:
            number[idx].append(alpha)
            idx -= 1
        # set priority using count each radix
        priority[alpha][7-i] += 1

# set AtoN with priority
order = sorted([(
    sum(c * 10 ** (len(v) - 1 - i) for i, c in enumerate(v))
    , k) for k, v in priority.items()], reverse=True)
for p, alpha in order:
    AtoN[alpha] = mx
    mx -= 1


# change word to number with greedy
answer = 0
for i, nums in enumerate(number):
    sum_radix = 0
    radix = 10 ** (len(number) - 1 - i)

    # check priority
    for num in nums:
        sum_radix += AtoN[num]

    answer += sum_radix * radix

print(answer)

• 자리수에 알파벳 배치
  
  • 리스트의 인덱스로 자리수를 구분하여 알파벳 배치
• 우선순위 설정
  • 알파벳마다 각 자리수에 개수 확인
  • 자리수, 개수로 값을 계산하여 우선순위 설정
• 우선순위에 따른 값 설정 및 계산
  • 우선순위에 따라 9부터 값 설정
  • 자리수를 고려하여 총 합계 계산

 

다른 사람이 작성한 코드

N=int(input())

# 입력할 단어 변수 선언
words = []

# 입력받기
for _ in range(N):
  words.append(input())

# 딕셔너리 초기화
dict = {}

# 딕셔너리에 알파벳별로 값을 집어 넣어준다.
for word in words:
  # 길이를 계산하여 10^square_root만큼 넣어주기 위해
  # -1를 하는 이유는 맨뒤는 1의자리이기 때문에
  # 0 제곱을 해야 한다.
  square_root = len(word) - 1
  for c in word:
    if c in dict: # 값이 있는경우 더해준다.
      dict[c] += pow(10, square_root)
    else: # 없는경우 그대로 넣어준다.
      dict[c] = pow(10, square_root)
    # 제곱근을 뺴준다.
    square_root -= 1 

# 딕셔너리를 큰값부터 쓰기 위해 정렬
dict = sorted(dict.values(), reverse=True)

# 값 계산할 변수 선언
result,m = 0,9

# 값 계산하기
for value in dict:
  result += value * m
  m -= 1

print(result)

• 우선순위 값에 바로 적용
  
  • 내가 작성한 코드 : 우선순위 구함 -> 9부터 값 설정 -> 설정된 값으로 계산
  • 위 코드 : 우선순위 구함 -> 9부터 값 계산
  • 내가 작성한 코드는 바로 계산하지 않고 중간과정으로 코드가 더 길어졌음

https://jokerldg.github.io/algorithm/2021/03/13/word-math.html

백준 1339번 단어 수학 (python 파이썬) - Tech

기억해야할 것

• 처음 우선순위를 잘못 설정함
  
  • 처음 우선순위 설정을 '높은 자릿수일수록' + '개수가 많을수록'으로 설정
  • 반례
    10
    ABB
    BB
    BB
    BB
    BB
    BB
    BB
    BB
    BB
    BB