11월에는 새로운 velog 시리즈 <내가 까먹을까봐 끄적이는>으로 돌아왔다.
개강하기 전, 방학 중에 알고리즘 문제를 간간히 풀면서 어느 정도 실력을 쌓았다고 생각하였지만
풀어본 문제들을 다시 살펴보면서 사용했던 아이디어나 오류 해결 방법이 잘 기억이 나지 않았다.
그래서 알고리즘 문제를 풀면서 사용한 아이디어나 디버깅 과정을 기록해보고자 한다.
💻 오늘 풀어볼 백준 문제는 !!!
백준 1339번 ( 단어 수학 )
www.acmicpc.net/problem/1339
백준 1339번, 단어 수학 문제의 알고리즘 종류는 '탐욕법(그리디)'이다.
탐욕법(그리디)란?
탐욕법은 현재 상황에서 가장 좋은 것(최선의 상황)을 고르는 알고리즘을 의미한다.
그리디 알고리즘의 특징은 현재 상황에서는 가장 좋은 결과를 도출했음에도 그 결과가 최종적인 결과의 최적해라는 보장은 없다.
필자의 경우, 해당 문제를 처음 보고 아래와 같이 코드를 작성하였다.
n = int(input())
answer = 0
saving = {'A':0, 'B':0, 'C':0, 'D':0, 'E':0, 'F':0, 'G':0, 'H':0, 'I':0, 'J':0}
values = []
num = 9
for _ in range(n):
word = input()
for s in range(len(word)):
saving[word[s]] += 10 ** (len(word) - 1 - s)
# print(saving)
for i in saving.values():
values.append(i)
values.sort(reverse = True)
# print(values)
for j in values:
if j == 0:
break
else:
answer += num * j
num -= 1
print(answer)문제 내부에 있는 테스트 코드가 문제없이 통과되었기에 문제를 채점하였다..!
하지만 결과는??
런타임 에러(KeyError)가 발생하였다!
구글링을 통해 알아보니 KeyError가 발생하는 경우는 딕셔너리에 해당하는 Key가 없을 때 접근하는 경우라고 한다.
처음 문제를 보고 알파벳의 최대 개수가 10개로 정해져 있기에 당연스럽게 입력값으로 주어지는 알파벳은 A부터 J까지라고 생각하였다.
하지만, 그렇지 않다면?
K~Z가 입력값으로 주어질 경우에는 ( 아래 코드를 보자! )
for _ in range(n):
word = input()
for s in range(len(word)):
saving[word[s]] += 10 ** (len(word) - 1 - s)10 ** (len(word) - 1 - s) 값을 기존에 있는 Key의 value에 더해주는 과정을 수행할 수 없다는 것을 알았다.
다른 개선점은 없나?
주어지는 알파벳의 개수는 '최대' 10개인 것이지 모든 경우에서 10개를 다 쓰지 않는다!
하지만 처음 작성한 코드는 딕셔너리에서 알파벳 10개를 모두 관리하며, value 값들을 리스트에 저장할 때도 answer에 value 값들을 추가할 때도 불필요한 반복이 이루어진다는 것을 알았다.
KeyError와 불필요한 반복을 개선한 코드 !
n = int(input())
answer = 0
saving = {}
values = []
num = 9
for _ in range(n):
word = input()
for s in range(len(word)):
if word[s] in saving:
saving[word[s]] += 10 ** (len(word) - 1 - s)
else:
saving[word[s]] = 10 ** (len(word) - 1 - s)
# print(saving)
for i in saving.values():
values.append(i)
values.sort(reverse = True)
#print(values)
for j in values:
answer += num * j
num -= 1
print(answer)word[s]가 saving이라는 딕셔너리에 존재하지 않는 경우에는 새로 추가해주고
존재하는 경우에는 value 값에 주어진 값들을 추가하는 방식으로 진행하였다.
또한, 이 과정에서 자연스럽게 사용되는 알파벳만 관리하기 때문에 answer에 값을 더하는 과정에서
이전 코드처럼 break를 통해 빈 value값을 갖는 경우를 따로 처리하지 않아도 된다!!
이 문제를 통해 어느 경우에 KeyError가 발생하는지, 파이썬에서 딕셔너리를 어떤 식으로 관리해주면 될 지에 대하여 알 수 있었다. 다음 포스팅은 '단어 수학'를 어떠한 아이디어를 통해 풀었는지 작성해볼 예정이다!
