백준 1339 단어 수학

문제 설명

이번 문제는 N개의 알파벳 단어가 주어질 경우 알파벳을 숫자 0~9 중 하나로 바꿔서 각 단어의 합을 구할 때, 이 합의 최대를 구하는 문제입니다.

• 모든 단어에 포함된 알파벳의 종류는 10개입니다.
• 각 단어의 길이는 8입니다.

 

문제 풀이

아이디어

최대값

각 알파벳을 숫자로 바꾼 뒤의 합을 구할 때, 높은 자리수의 알파벳이 큰 숫자가 되어야 합의 최대가 될 수 있습니다.

그러므로 가장 높은 자리에 위치한 알파벳이 큰 숫자가 되어야 합니다.

 

만약 여러 단어에서 같은 자리수의 알파벳 중 더 높은 숫자를 줘야 하는 알파벳을 고려해야 한다면, 이후에 또 등장하고 등장하는 자리수가 더 높은 알파벳에 더 높은 숫자를 부여해주어야 합니다.

 

등장하는 자리수 구하기

각 알파벳이 등장하는 자리수를 저장해두어야지만, 어떤 알파벳에 높은 숫자를 부여할지 알 수 있습니다.

각 알파벳을 딕셔너리에 저장해두고 등장하는 자리수를 10의 단위로 나타내어 줍니다.

예를 들어 ABBAA와 ACC가 있다면 각 단어에서 등장하는 A,B,C를 딕셔너리에 저장하여 자리수를 파악한다면,

dict = { A:10111, B:1100, C:11 }

이와 같이 표시해줄 수 있습니다.

 

풀이

자리수 표시

반복문을 통해 단어마다 등장하는 알파벳의 자리수를 표시해줍니다.

단어의 인덱스와 같은 경우 자리값으로 나타낼 경우에는 거꾸로 표시해줘야하기 때문에 주의해줍니다. ('ABCDE'에서 A의 인덱스는 0이지만, 실제 자리수는 5)

 

'ABCDE'에서 A의 자리수를 딕셔너리에 저장할 경우 dict['A'] = 10 ** {자리수}로 저장합니다.

이후 다른 단어에서 A가 또 나오게 된다면 dict['A'] += 10 ** {자리수} 와 같은 형식으로 더해줍니다.

 

합의 최대값 구하기

위를 통해 각 알파벳을 10의 자리 숫자로 표기했다면, 이를 내림차순으로 정렬해줍니다.

높은 자리수에서 등장하는 알파벳일 경우 해당 알파벳에 높은 숫자를 부여해줘야 합의 최대값을 구할 수 있기 때문입니다.

이를 통해서, 같은 자리수에서 등장하는 알파벳의 경우 어떤 알파벳에 높은 숫자를 부여해야할지도 정해줄 수 있습니다.

 

예를 들어, C가 1010이고 D가 1001일 경우 C와 D가 모두 1000의 자리수에서 등장함으로 등장하는 가장 높은 자리수는 같지만, 그 다음 등장하는 자리수가 C가 D보다 더 높은 자리수에서 등장하므로 C에 더 높은 숫자를 부여해줘야 합니다.

 

내림차순으로 정렬된 숫자를 가장 높은 숫자인 9부터 차례대로 곱한 뒤 최종 합에 더해주면 답이 됩니다.

numList = sorted(alpha_dict.values(),reverse=True)
total = 0
n = 9
for num in numList: 
    total += n * num
    n -= 1

 

 

해결

이번 문제는 그리드 문제였습니다. 각 단어마다 최대한 큰 숫자를 부여함으로써 단어 합의 최대값을 구할 수 있도록 했습니다. 각 단어가 등장하는 자리수에 따라 숫자를 부여해야 됐으므로 자리수에 따른 숫자를 우선 10의 자리수로 부여해주는 것이 문제를 푸는데 도움이 됐습니다.

앞으로 한 두 문제 정도 더 그리디 관련 문제를 풀어봄으로써 감을 더 찾아야될 것 같습니다.

 

문제 링크 : https://www.acmicpc.net/problem/1339

1339번: 단어 수학

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/1339.py