[그리디] 1946 신입사원, 1339 단어 수학

3. 1946 신입사원

3.1. 문제유형

• 그리디, 정렬

3.2. 해결과정

• 그리디 문제지만 지원자가 10만명이므로 2중 for문으로 접근 시 10^10 연산 횟수가 필요하다.
• 따라서 O(n^2)이하의 복잡도로 문제를 해결해야 한다.
• 힌트는 서류나 면접점수 둘 중 하나로 정렬하면, 1명은 무조건 합격이라는 것을 알 수 있다.
• 이를 활용하여 서류로 정렬 후 합격자보다 면접점수가 높은 지원자를 카운트한다.
• 이전 합격자보다 면접점수가 높은 지원자가 나오면 면접 점수를 갱신한다.

3.3. 소스코드

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    apply = [list(map(int,input().split())) for _ in range(n)]
    apply = sorted(apply)
    answer = 1
    end = apply[0][1]

    for i in range(1, n):
        if end > apply[i][1]:
            end = apply[i][1]
            answer += 1

    print(answer)

4. 1339 단어 수학

4.1. 문제유형

• 그리디, 브루트포스

4.2. 해결과정

1. 좋은 접근 방법은 자리수를 생각하는 것이었다.
2. ABC, BCA인 경우 A와 B중 어디에 더 큰 수를 배정할 지 결정하기 쉽기 때문
3. 따라서 알파벳자릿수를 10의 제곱수를 활용해 알파벳별 합계를 해시맵으로 저장한다.

4.3. 소스코드

from collections import defaultdict
n = int(input())
numbers = [list(map(str, input())) for _ in range(n)]

hash=defaultdict(int)
for num in numbers:
    for i in range(len(num)):
        hash[num[i]]+=10**(len(num)-i-1)
hash = sorted(hash.items(), key=lambda x:x[1], reverse=True)

hash_map={}
value = 9
for alpha, _ in hash:
    hash_map[alpha]=value
    value-=1

answer=[]
for num in numbers:
    ans=''
    for alpha in num:
        ans+=str(hash_map[alpha])
    answer.append(int(ans))
print(sum(answer))