[백준] 1339, 2812

단어 수학 (1339번)

• 사이트/난이도: 백준/골드4
• 코드

# 골드4 단어 수학
import sys
from collections import defaultdict
input = sys.stdin.readline

n = int(input())
words = [input().strip() for _ in range(n)]
# words.sort(key=lambda x: -len(x))

dic = defaultdict(int) # 알파벳: 우선순위 점수

for word in words:
    for i in range(len(word)):
        dic[word[i]] += 10**(len(word)-1-i)

dic = dict(sorted(dic.items(), key=lambda item: -item[1])) # 점수 순으로 내림차순 정렬

num = 9
answer = 0
for v in dic.values(): # 높은 점수 부터 9~1 까지 부여하면서 더하면 정답
    answer += num * v
    num -= 1

print(answer)

• 느낀점
  • 자리수 별로 우선순위 점수를 다르게 부여하여 우선순위가 높은 순서대로 9~1 까지 부여하면 풀리는 그리디 문제

크게 만들기 (2812번)

• 사이트/난이도: 백준/골드3
• 코드

# 골드3 크게 만들기
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
numbers = input().rstrip()
stack = []

for number in numbers:
    while stack and stack[-1] < number and k > 0:
        stack.pop()
        k -= 1
    stack.append(number)

if k > 0:
    print(''.join(stack[:-k]))
else:
    print(''.join(stack))

• 느낀점
  • 기존 숫자 배열과 최대로 만들 stack 배열을 따로 만들어서 관리한다.
  • 이 때 numbers의 숫자들을 하나씩 stack에 넣을 때 stack의 가장 뒤에 숫자보다 number의 숫자가 크다면 pop을 하여 앞쪽에 위치하도록 한다.
  • k개를 다 지우지 못했다면 뒤에서부터 k개를 지우고 출력한다.