[백준 python] 1339번 단어 수학 - 그리디

2022. 3. 10. 19:36·지난 글 모음
반응형

[백준 python] 1339번 단어 수학 - 그리디

레벨: 골드 4

언어: python


문제풀러가기

📑풀이 과정

초반에 상당히 헤매다가 질문 검색에서 힌트를 얻어서 구현하였다.
처음 아이디어는 자리수가 높은 알파벳부터 낮은 알파벳 순으로 숫자를 부여했다.
이때 문제는 아래와 같은 케이스가 들어오면 A를 9로 바꾸고 B를 8로 바꿔서 오답이 난다.

10
ABB
BB
BB
BB
BB
BB
BB
BB
BB
BB

이제 제대로 된 풀이를 설명하겠다.


자리수를 사용하면 되지만 단순히 순서만을 가지고는 풀 수 없다.
알파벳의 자리수 만큼 곱한 값을 기준으로 순서를 정해야 한다.

 

2
GCF
ACDEB


위의 예시는
A 는 만자리 10000
C 는 천자리 하나와 십의 자리 하나 1000 + 10
D 는 백자리 하나 100
G 도 백자리 하나 100
E 는 십자리 하나 10
B 는 일자리 하나 1
F 도 일자리 하나 1

 

그리고 구한 숫자가 높은 순서대로 9 ~ 0 까지 바꿔주고 모두 더해주면된다.
A 9 * 10000 
C 8 * 1010 
D 7 * 100 
G 6 * 100 
E 5 * 10 
B 4 * 1 
F 3 * 1 

위의 합은 99437
이렇게 답을 구할 수 있다.

파이썬의 딕셔너리를 이용하여 {'A' : 10000} 의 형태로 만들어주면 쉽게 할 수 있다.

📋풀이 코드

import sys

input = sys.stdin.readline

N = int(input())

dic = {}
for i in range(N):
  word = list(input().strip())

  for j in range(0, len(word)):
    alphabet = word.pop()
    if alphabet in dic:
      dic[alphabet] += 10**j
    else:
      dic[alphabet] = 10**j

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

print(dic)

total = 0
idx = 9
for k in dic:
  total += idx*k[1]
  idx-=1

print(total)

💻 코드 라인별 풀이

  for j in range(0, len(word)):
    alphabet = word.pop()
    if alphabet in dic:
      dic[alphabet] += 10**j
    else:
      dic[alphabet] = 10**j

입력 값을 배열로 저장하고 하나씩 pop() 자리수 만큼 곱한 값을 dic에 넣어준다.
입력이 ABC 이면 ['A', 'B', 'C'] 로 배열에 넣고 pop()하여 1의 자리 부터 계산한다.

 

위 계산을 끝내면
딕셔너리에 [('A', 100), ('B', 10), ('C', 1)] 로 저장이 된다.

 

그리고 value 값으로 내림차순 정렬을 한다.

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

total = 0
idx = 9
for k in dic:
  total += idx*k[1]
  idx-=1

각 알파벳의 값을 9부터 순서대로 곱하여 total에 저장하고 total을 출력하면 된다.


반응형

'지난 글 모음' 카테고리의 다른 글

[백준 python] 18352번 특정 거리의 도시 찾기- DFS/BFS  (0) 2022.03.11
[백준 python] 12904번 A와 B 그리디  (0) 2022.03.11
[백준 python] 19941번 햄버거 분배 - 그리디  (0) 2022.03.10
[백준 python] 1105번 팔 - 그리디  (0) 2022.03.09
[백준 python] 1246번 온라인 판매  (0) 2022.03.05
'지난 글 모음' 카테고리의 다른 글
  • [백준 python] 18352번 특정 거리의 도시 찾기- DFS/BFS
  • [백준 python] 12904번 A와 B 그리디
  • [백준 python] 19941번 햄버거 분배 - 그리디
  • [백준 python] 1105번 팔 - 그리디
코딩하자영아
코딩하자영아
코딩공부내용 정리
  • 코딩하자영아
    코드치고 무게치고
    코딩하자영아
  • 전체
    오늘
    어제
    • 분류 전체보기 (82)
      • 개발 (1)
      • 지난 글 모음 (81)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    회원가입 폼
    코딩테스트
    회원가입
    malloc-lab
    백준
    Coding Test
    Express
    sw 정글
    정글sw
    SW정글
    PINTOS
    템플릿 문자열
    Spring
    JavaScrpit
    자바스크립트
    목록 창 만들기
    React
    자바스크립트 문자열 변수
    conding test
    프로그래머스
    node.js
    html input
    javascript
    onChange
    python
    HTML
    dfsbfs
    사용자 정의 객체
    sw정글사관학교
    리액트
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
코딩하자영아
[백준 python] 1339번 단어 수학 - 그리디
상단으로

티스토리툴바