수학과의 개발자 도전기

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

Gold Level4 문제이고, 어려웠던 문제다 

문제 아이디어로는 왼쪽에서부터 진행하고, 각 문자에 대한 10의 자리 값을 dictionary에 저장한다. 

dictionary에 있으면 원래 값에 새로운 값을 더하고, 아니라면 값을 입력한다 

이때 range(len(alpha_dict)) 랑 len(alpha[i])-j-1 쓸때 주의하자 

여기서 많이 틀렸음

10자리 수들을 numList에 저장하고, 내림차순으로 정렬한다

9부터 하나씩 줄여가면서 값을 numList의 값에 곱해주고 더해주면 정답이다

-정답 풀이 : 

n=int(input())
alpha=[]
alpha_dict={}
numList=[]

for _ in range(n):
    alpha.append(list(input()))
    
for i in range(n):
    for j in range(len(alpha[i])):
        if alpha[i][j] in alpha_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():
    numList.append(val)
    
numList.sort(reverse=True)

power=9
answer=0
for i in range(len(numList)):
    answer += power*numList[i]
    power-=1
print(answer)

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

Silver 5 문제.  스스로 풀어서 맞힌 문제. 풀이는 그렇게 어렵지 않았다 

예제를 통해서 v가 p보다 크면 최소 l*(v//p)만큼 캠핑에서 머물 수 있고, 

나머지 날은 무조건 p보다 작으므로 l과의 크기 비교를 통해서 v를 더할지, l을 더할지 구분하면 된다 

-정답 풀이:

import sys
input = sys.stdin.readline

i=0
while True :
    l,p,v = map(int,input().split())
    if p == 0 and l ==0 and v==0 :
        break
    i+=1
    answer=0
    if v>=p :
        answer+= (v//p)*l
        v-=(v//p)*p
        
    if v < p:
        if v < l:
            answer += v
        else:
            answer += l
    print('Case {0}: {1}'.format(i,answer))

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

-정답 풀이 : 

heapq.heapify(data)를 설정해주지 않아서 틀렸었다.

입력 데이터에서 가장 작은 값을 인덱스 0에 놓아야하는데, 이를 위해선 data 리스트도 heap으로 설정해줘야 한다 

input = sys.stdin.readline이 없을 때와 있을 때 실행 시간이 20배 차이난다. 설정해주자!

처음 풀었을 때보다는 heap을 잘 다루는 것 같다

import sys
import heapq 
input = sys.stdin.readline

n=int(input())
data=[]

for _ in range(n):
    data.append(int(input()))
answer=0

#여기를 설정하지 않으면 틀린다!
heapq.heapify(data)

for _ in range(n-1): 
    a=heapq.heappop(data)
    b=heapq.heappop(data)
    heapq.heappush(data, a + b)
    answer += (a + b)
    
print(answer)

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

-정답 풀이:

0열을 기준으로 오름차순 정렬하면 서류에서 우수한 사람들을 가릴 수 있다. 

기본적으로 서류에서 0등은 뽑히므로 count=1로 시작한다. 

서류에서 우수한 사람보다 면접에서 더 우수하면 그 사람은 면접에서라도 뛰어나므로 채용이 된다. 

채용된 사람의 면접 점수를 기준으로 다음을 이어나가면 된다

for _ in range(int(input())):
    n=int(input())
    data=[]
    for _ in range(n):
        data.append(list(map(int,input().split())))
    zero=sorted(data,key=lambda x: x[0])
    #선발인원 수 
    count=1
    result = zero[0][1]
    
    for i in range(1,n):
        if zero[i][1] < result:
            count+=1
            result=zero[i][1]       
    print(count)

-시간초과 풀이: 

이중 for문으로 풀었는데 이렇게 하면 시간복잡도가 n**2가 되어서 시간초과가 발생한다 

for _ in range(int(input())):
    n=int(input())
    data=[]
    for _ in range(n):
        data.append(list(map(int,input().split())))
    zero=sorted(data,key=lambda x: x[0])
    one = sorted(data, key=lambda x: x[1])
    count=0
    
    for i in range(n):
        for j in range(i+1):
            if zero[j][1] > zero[i][1]:
                count+=1
    print(n-count)