백준 17828번 파이썬 풀이: 문자열 화폐

백준 17828번 문자열 화폐

 

알고리즘 분류: 그리디 알고리즘

 

링크: www.acmicpc.net/problem/17828

 

17828번: 문자열 화폐

 

문제

작년에 소수나라에 다녀온 하나는, 올해는 문자열나라로 관광을 가려고 한다. 문자열나라에서는 특이하게 알파벳 대문자로 구성된 문자열을 화폐로 사용한다.

문자열나라에서 'A'는 1의 가치, 'B'는 2의 가치, ..., 'Z'는 26의 가치를 가지고 있으며, 이 알파벳들을 붙여 화폐로 쓰일 문자열을 만든다. 예를 들어, "HONGIK"의 가치는 8 + 15 + 14 + 7 + 9 + 11 = 64가 된다.

소수나라에서 특이한 화폐 때문에 큰 스트레스를 받았던 하나는, 이번에는 정확한 소비 계획을 세워 미리 문자열 화폐로 돈을 환전해가려고 한다. 하나가 가져갈 문자열은 딱 하나이며, 길이는 N이고, 가치는 X여야 한다. 그리고 물론 알파벳 대문자로만 이루어져 있어야 한다.

그런데 환전소에서는 사전 순으로 앞서는 문자열을 우선적으로 환전해준다고 한다! 여행 준비에 정신이 없는 하나를 위해, 조건을 만족하면서 사전 순으로 가장 앞서는 문자열 구해주자.

입력

첫 번째 줄에 문자열의 길이 N(1 ≤ N ≤ 5,000,000)과, 문자열의 가치를 나타내는 정수 X(1 ≤ X ≤ 500,000,000)가 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 조건을 만족하는 문자열 중, 사전 순으로 가장 앞서는 것을 출력한다. 만약 그런 문자열이 하나도 존재하지 않으면, "!"(따옴표 없이)를 출력한다.

 

 

문제 파악

 

숫자를 문자열로 바꾸고 이를 사전 순으로 가장 앞서는 문자열을 구하는 문제이다.

 

숫자를 문자열로 바꿔야 하는데 이를 하나하나 입력하는 것은 힘드니

 

출처 : https://namu.wiki/w/%EC%95%84%EC%8A%A4%ED%82%A4%20%EC%BD%94%EB%93%9C

아스키 코드표를 이용해서 반복문을 통해 쉽게 입력하였다.

 

만약 조건을 만족하는 문자열이 하나도 없다면 !를 출력하게 하였다.

 

그러나 사실 이 문제를 풀지 못하였는데 예제를 입력했을 때는 정상적으로 출력이 되고

 

임의로 몇가지 예를 더 실험해보았을 때는 잘 출력이 되는데 아직 반례를 찾지 못하였다.

 

워낙 문제를 푼 사람도 적고 풀이가 많이 없어서 틀린 부분을 많이 지적해주셨으면 좋겠습니다.

 

 

코드

# 17828번

import sys

n, x = map(int, sys.stdin.readline().split())

alpha_key = []
alpha_value = []

for i in range(26):
    alpha_key.append(chr(90 - i))
    alpha_value.append(26 - i)

answer_list = []

if (26 * n) < x or n > x:
    answer_list.append("!")
else:
    for i in range(len(alpha_value)):
        if x // alpha_value[i] > 0 and x % alpha_value[i] >= n - (len(answer_list) + x // alpha_value[i]):
            for j in range(x // alpha_value[i]):
                answer_list.append(alpha_key[i])
            x %= alpha_value[i]
    
    answer_list.sort()

answer = "".join(map(str, answer_list))

print(answer)

틀린 풀이지만 설명을 해보자면

 

처음에 사전으로 key, value값을 받으려고 생각하다가 반복문을 이용하려면 리스트에 담는것이 유리하다고

 

판단되어서 alpha_key 라는 문자열을 담는 리스트와 alpha_value라는 해당하는 숫자를 담는 리스트를 만들었다.

 

조건을 만족하는 문자열이 없을시에는 !를 출력하게 하고 조건을 만족하는 문자열이 있다면

 

key, value가 내림차순으로 정렬되있기 때문에 큰수부터 채워서 answer_list가 n만큼의 길이를 갖게하고

 

answer_list를 오름차순으로 정렬해서 사전순으로 나타나게했다.

 

이를 다시 문자열로 바꿔서 출력해서 예제는 통과하였는데 정답을 통과못하였다.