수학과의 개발자 도전기

-문제: https://www.acmicpc.net/problem/1339

개인적으로 어려웠던 문제. 딕셔너리를 사용해서는 처음 풀어보았다. 좀 더 공부하자!

-정답풀이: 

n=int(input())

alpha=[] #단어를 저장할 리스트
alpha_dict={} #단어 내의 알파벳별로 수를 저장할 딕셔너리
numList=[] #수를 저장할 리스트

for i in range(n):
    alpha.append(input().rstrip())
    
for i in range(n):#모든 단어에 대해서
    for j in range(len(alpha[i])): #i번째 단어의 길이만큼 실행
        if alpha[i][j] in alpha_dict: #단어의 알파벳이 이미 dict에 있다면
            alpha_dict[alpha[i][j]] += 10**(len(alpha[i])-j-1)    
        else: 
            alpha_dict[alpha[i][j]] =10**(len(alpha[i])-j-1)
        
for val in alpha_dict.values(): #dict에 저장된 수들(밸류들)을 모두 numList에 추가
    numList.append(val)
    
numList.sort(reverse=True)#수들 큰수부터(내림차순으로) 정렬

s=0
pows=9
for i in numList:
    s+= pows*i
    pows-=1
print(s)

• 입력되는 단어들을 리스트로 입력하고
• 각 알파벳의 위치에 맞는 10승을 딕셔너리에 대입한다('A': 10^5)
• 딕셔너리의 밸류들을 numList에 대입한 후 큰 순서로 정렬한다
• 그리고 큰 것부터 pows를 곱해가면서 더하면된다(이때 pows는 단계마다 1씩 줄어든다)

-문제: https://www.acmicpc.net/problem/1715

일반 리스트로 구현하는 건줄 알았는데 우선순위 큐를 사용했어야하는 문제다

-정답풀이: 

import heapq
import sys
input=sys.stdin.readline

n=int(input())
ans=[]
for _ in range(n):
    ans.append(int(input()))
result=0
heapq.heapify(ans)
while len(ans)>1:
    a=heapq.heappop(ans)
    b=heapq.heappop(ans)
    heapq.heappush(ans,a+b)
    result+=(a+b)
print(result)

-처음 보는 부분 공부:

-> heapq 모듈은 이진트리 기반의 최소 힙(min heap) 자료구조를 제공한다. 최솟값만 필요할 때 사용하면된다 

-> heapq.heappop(): 힙에서 원소를 삭제할 때 사용. 원소를 삭제할 대상 리스트를 인자로 넘기면, 가장 작은 원소를 삭제 후에 그 값을 리턴한다. 위에서는 최솟값을 a와 b에 입력한다. 

->heapq.heappush(x,y): x에 y값을 넣는다. 여기서는 최솟값인 a와 b의 합인 a+b를 넣는다 

->a,b값 없애고 a+b 값을 넣는 구조 

-틀린풀이:

• 이 풀이는 왜 안되는지 공부를 좀 해야할 것 같다 

-문제:https://www.acmicpc.net/problem/1946

이맞왜틀이었던 문제. 나중에 무엇이 문제였는지 다시 풀어봐야할 것 같다

-정답풀이:

• 20번 라인을 익혀야할 것 같다 

import sys

T = int(input()) #테스트케이스

for i in range(0,T):
    Cnt = 1
    people = []
    
    N = int(input())
    for i in range(N):
        Paper, Interview = map(int,sys.stdin.readline().split())
        people.append([Paper, Interview])

    people.sort() # 서류 기준 오름차순 정렬
    Max = people[0][1]
    
    for i in range(1,N):
        if Max > people[i][1]:
            Cnt += 1
            Max = people[i][1]

    print(Cnt)

-틀린 풀이:

-문제: https://www.acmicpc.net/problem/13305

-정답풀이:

• 지금까지 지났던 주유소의 리터아 가격 중 작은값으로 도로를 이동하는 걸 생각하면 된다
• 따라서 주유소 가격은 지금까지의 주유소 가격보다 작을 때 갱신된다

-부분 정답풀이(내 풀이):

• 약간 dp풀이처럼 푼 것 같기도 하다