[백준] 1339번 단어수학 - 파이썬(Python)

2021. 10. 7. 12:50· 알고리즘/문제풀이
목차
  1. 문제 (링크)
  2. 나의 풀이
  3. 코드 설명 및 풀이
728x90

문제 (링크)

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

 

1339번: 단어 수학

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대

www.acmicpc.net

 

나의 풀이

# 오답
import sys
input = sys.stdin.readline
words = []
word_dict = {}
n = int(input())
for _ in range(n):
    words.append(list(str(input().rstrip())))

words = sorted(words, key=lambda x:len(x), reverse=True)
longest_words = words[0]
i = 0
num = 9
while i < len(longest_words):
    if longest_words[i] not in word_dict:
        word_dict[longest_words[i]] = num
        num -= 1

    for j in range(1, len(words)):
        len_diff = len(longest_words) - len(words[j])
        if len_diff <= i:
            if words[j][i - len_diff] not in word_dict:
                word_dict[words[j][i - len_diff]] = num
                num -= 1

    i += 1

ans = 0
for word in words:
    word_to_num = ""
    for alpha in word:
        word_to_num += str(word_dict[alpha])
    
    ans += int(word_to_num)

print(ans)

코드 설명 및 풀이

처음 생각했던 방법은 가장 자리 수가 높이 있는 알파벳부터 차례대로 9부터 숫자를 부여하는 것이었다.

 

즉, 테스트케이스 2번에서 처럼 GCF와 ACDEB라는 문자열이 있으면

 

ACDEB + GCF로, 가장 자리수가 높은 A와 C에게 각각 9와 8을 부여하고, 나머지 DEB와 GCF 마찬가지로 자리수가 높은 순서대로 나머지 숫자들을 부여하는 것이었다.

 

즉, A, C = 9, 8, D, G = 7, 6, E = 5, B, F = 4, 3 이런식으로 부여하는 것이다.

 

이 방식은 주어진 테스트케이스에서는 모두 통과를 했지만 제출했을 때는 오답이 떴다.

 

반례를 찾아보니 만약 주어진 문자열이

10

ABB

BB

BB

BB

BB

BB

BB

BB

BB

BB

 

이라면, 내가 짠 코드에 따르면 가장 높은 자리의 A가 9를 부여받고 B가 8을 부여받게 된다.

 

결국, 988 + 88 + 88 + 88 + 88 + 88 + 88 + 88 + 88 + 88= 1780이 되는데 이는 최대값이 아니다.

 

만약 B가 9를 부여받고 A가 8을 부여받게 되면 899 + 99 + 99 + 99 + 99 + 99 + 99 + 99 + 99 + 99 = 1790이 되기 때문이다.

 

즉, 단순히 알파벳의 자리 수만 보고 숫자를 부여하는 것은 잘못된 접근법이었다.

 

n = int(input())
words = []
alpha_value = {}
for _ in range(n):
    words.append(list(input().rstrip()))

for word in words:
    for i in range(len(word)):
        if word[i] not in alpha_value:
            alpha_value[word[i]] = 10 ** (len(word) - 1 - i)
        
        else:
            alpha_value[word[i]] += 10 ** (len(word) - 1 - i)

alpha_value = sorted(alpha_value.items(), key=lambda x: x[1], reverse=True)

alpha_to_num = {}

num = 9
for alpha in alpha_value:
    alpha_to_num[alpha[0]] = num
    num -= 1

ans = 0
for word in words:
    num = ""
    for alpha in word:
        num += str(alpha_to_num[alpha])
    
    ans += int(num)

print(ans)

해답은 각 알파벳의 모든 자릿수를 계산한 후 딕셔너리에 저장해 그 값을 토대로 숫자를 부여하는 것이다.

 

테스트케이스였던 GCF, ACDEB를 다시 살펴보자.

 

A은 6번째 자리에 한 번 와있다. 따라서 A의 자릿수의 합은 10^5(10000)이 된다.

 

B는 1번째 자리에 한 번 등장하기 때문에 B의 자릿수의 합은 10^0(1)이 된다.

 

C는 2번째 자리에 한 번, 5번째 자리에 한 번 등장하므로 10^1 + 10^4 = 1010이 된다.

 

이런 방식으로 등장하는 모든 알파벳에 자릿수의 합을 더해주고, 그 값이 큰 알파벳부터 큰 값을 부여해주면 된다.

 

첫 번째 풀이의 반례였던

10

ABB

BB

BB

BB

BB

BB

BB

BB

BB

BB

역시, A의 자릿수의 합은 10^2 = 100이고, B의 자릿수의 합은 10^1 * 10 + 10^0 * 10 = 110이므로 B가 9를, A가 8을 부여받아 올바른 답을 출력하게 된다.

저작자표시 (새창열림)

'알고리즘 > 문제풀이' 카테고리의 다른 글

[백준] 14499번 주사위 굴리기 - 파이썬(Python)  (0) 2021.10.14
[백준] 18808번 스티커 붙이기 - 파이썬(Python)  (0) 2021.10.12
[백준] 2170번 선 긋기 - 파이썬(Python)  (0) 2021.10.05
[백준] 1520번 내리막길 - 파이썬(Python)  (0) 2021.10.05
[백준] 2293번 동전 1 - 파이썬(Python)  (3) 2021.10.04
  1. 문제 (링크)
  2. 나의 풀이
  3. 코드 설명 및 풀이
'알고리즘/문제풀이' 카테고리의 다른 글
  • [백준] 14499번 주사위 굴리기 - 파이썬(Python)
  • [백준] 18808번 스티커 붙이기 - 파이썬(Python)
  • [백준] 2170번 선 긋기 - 파이썬(Python)
  • [백준] 1520번 내리막길 - 파이썬(Python)
SeongOnion
SeongOnion
서버는 꺼지지 않아요
SeongOnion
조무래기 코딩
SeongOnion
전체
오늘
어제
  • 분류 전체보기 (167)
    • 알고리즘 (81)
      • 이론 (8)
      • 문제풀이 (73)
    • 언어 (15)
      • Python (9)
      • JavaScript (1)
      • JAVA (5)
    • 데이터베이스 (5)
    • 프레임워크 (15)
      • Django (7)
      • Spring (8)
    • 그 외 공부 (38)
      • 운영체제 (1)
      • 자료구조 (14)
      • 네트워크 (5)
      • CS (2)
      • 기타 (7)
      • 트러블 슈팅 (9)
    • 프로젝트 (0)
    • 개발자취 (8)
    • 회고 (3)
    • 주저리주저리 (1)
    • 기타 (비개발) (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 이진탐색
  • 오픈소스
  • 에라토스테네스의 체
  • 자바
  • 알고리즘
  • spring
  • 투 포인터 알고리즘
  • 컨트리뷰트
  • 트러블 슈팅
  • 코딩테스트
  • 회고
  • BFS/DFS
  • 큐
  • 코딩
  • 파이썬
  • 웹
  • 개발자
  • 소수
  • 프로그래머스
  • 브루트포스
  • BFS
  • 백준
  • 장고
  • Django
  • 그리디알고리즘
  • 스택
  • DRF
  • 데이터베이스
  • DP
  • 정렬 알고리즘

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
SeongOnion
[백준] 1339번 단어수학 - 파이썬(Python)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.