sugenius

https://school.programmers.co.kr/learn/challenges?tab=algorithm_practice_kit 

https://school.programmers.co.kr/learn/challenges?tab=algorithm_practice_kit 

<스택/큐>
Q.같은 숫자는 싫어 

def solution(arr):
    answer = []
    for a in arr : 
        if a not in answer or a!= answer[-1] : 
            answer.append(a)
    return answer

Q.기능개발 #***

'''
#틀림 --> x > dq[0] 에서 부등호 빠짐 ㅠ x>=q[0] 이여야함 
#반례 : [90, 90, 90, 90],[30, 1, 1, 1],[1, 3] 
from collections import deque 
def solution(progresses, speeds):
    answer = []
    dq=[]
    for p,s in zip(progresses,speeds) : 
        n=(100-p)//s 
        if n*s+p < 100 : 
            n+=1 
        dq.append(n)
        
    dq=deque(dq)
    cnt=0
    
    while True : 
        if len(dq)==0 : 
            break 
            
        x=dq.popleft()
        cnt=1
        while dq and x > dq[0] : 
            dq.popleft()
            cnt+=1
        answer.append(cnt)
    
    return answer

'''
from collections import deque 
def solution(progresses, speeds):
    answer = []
    dq=[]
    dq=deque(dq)
    
    for p,s in zip(progresses,speeds) : 
        n=(100-p)//s 
        while True : 
            if n*s+p < 100 : 
                n+=1
            else : 
                break
        
        dq.append(n)
    
    while True : 
        if len(dq)==0 : 
            break 
        if len(dq)==1 : 
            answer.append(1)
            break 
            
        x=dq.popleft()
        cnt=1
        while dq and x >= dq[0] : 
            dq.popleft()
            cnt+=1
            
        answer.append(cnt)
    
    return answer

Q.올바른 괄호 

def solution(s):
    answer = True
    stack=[] 
    
    if s[0] == ')' : 
        return False 
    
    for x in s : 
        if x=='(' : 
            stack.append(x) 
        else : #')'
            if len(stack)==0 : 
                return False 
            stack.pop()
            
    if len(stack) > 0 : 
        return False

    return True

Q.프로세스 #***

from collections import deque 
def solution(priorities, location):
    answer = 0
    dq = deque() 
    for i,p in enumerate(priorities) :  
        dq.append((i,p))
        
    while True : 
        x=dq.popleft()
        if any(x[1]<d[1] for d in dq) : 
            dq.append(x)
        else : 
            answer+=1
            if x[0] == location :
                break
    return answer
#queue =  [(i,p) for i,p in enumerate(priorities)]

Q.다리를 지나는 트럭 #***

'''
#틀림
from collections import deque 
def solution(bridge_length, weight, truck_weights):
    answer = 0
    dq=deque([0]*bridge_length)
    dq=deque(dq)
    truck_weights = deque(truck_weights)
    while True : 
        if len(truck_weights) == 0 and len(dq) == 0 : 
            break 
            
        if len(truck_weights) > 0 and (sum(dq)+truck_weights[0]) <= weight : 
            dq.append(truck_weights.popleft())
        else : 
            dq.popleft()
        answer+=1
        
    return answer

'''
from collections import deque 
def solution(bridge_length, weight, truck_weights):
    answer = 0
    
    #시간 초과 / 5번 테스트 케이스만 .. >> sum() 함수 : O(n) 이라 김  um보다는 변수를 가감하는 방식으로 변경해야 
    dq=deque([0]*bridge_length)
    truck_weights = deque(truck_weights)
    sum_truck= 0 
    
    while dq:
        answer+=1
        sum_truck-=dq.popleft()
        if truck_weights:
            #if sum(dq)+truck_weights[0]<=weight:
            if sum_truck+truck_weights[0]<=weight:
                x=truck_weights.popleft()
                sum_truck+=x
                dq.append(x)
            else:
                dq.append(0)
    
    return answer

Q.주식가격 #***

def solution(prices):
    answer = []
    
    '''
    #테스트 케이스 1번 제외 하고 틀림 
    #반례 [4,5,1,2,6,1,1], [2,1,4,2,1,1,0] 
    for i, p in enumerate (prices) : 
        cnt=0
        print(p, prices[i+1:])
        for j in prices[i+1:] : 
            if p <= j : 
                cnt+=1
        answer.append(cnt)
    
    '''

    '''
    #효율성 테스트 모두 실패 
    for i,p in enumerate (prices) : 
        cnt=0
        stack=[]
        for t in prices[i+1:] : 
            stack.append(t)
            if stack[-1] < p :
                cnt=len(stack)
                break
            else : 
                cnt+=1
        answer.append(cnt)
    '''

    return answer

from collections import deque 
def solution(prices):
    answer = []
    dq=deque(prices)
    
    while dq : 
        x=dq.popleft()
        cnt=0
        for i in dq : 
            cnt+=1 
            if i < x :
                break 
        answer.append(cnt)
    return answer

https://school.programmers.co.kr/learn/challenges?tab=algorithm_practice_kit 

<해시> 
Q.완주하지 못한 선수 #***

def solution(participant, completion):
    answer = ''
    '''
    #틀림. 효율성 테스트 모두 실패 
    for c in completion : 
        participant.remove(c)
    answer=participant[0]
    '''
    tmp=dict() 
    for p in participant : 
        tmp[p]=tmp.get(p,0) +1
    for c in completion :
        tmp[c]=tmp[c]-1
    
    for t in tmp.keys() :
        if tmp[t] > 0 :
            answer=t
            break
    
    return answer

'''
import collections
def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys())[0]
'''
'''
    participant.sort()
    completion.sort()
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
    return participant[len(participant)-1]
'''

Q.폰켓몬

def solution(nums):
    answer = 0
    cnt=len(nums)
    nums=set(nums)
    if len(nums) > cnt/2 :
        answer = cnt/2 
    else : 
        answer=len(nums)
    return answer
    #return min(len(ls)/2, len(set(ls)))

Q.전화번호 목록 #***

def solution(phone_book):
    '''
    #틀림 ㅠ 
    answer = True
    x = min(phone_book) 
    for p in phone_book : 
        if x in p and p!=x: 
            answer=False
            break
    '''
    answer=True
    phone_book = sorted(phone_book)
    for p1, p2 in zip(phone_book, phone_book[1:]):
        if p2.startswith(p1): 
            answer=False
            break
    return answer

Q.의상 #*** 

'''
A 종류 N개,B 종류 M개 일 때 가능한 모든 경우의 수는 (N+1)(M+1)
(N+1)(M+1) = NM + N + M + 1
NM: N과 M을 모두 사용하는 경우
N: N만 사용하는 경우
M: M만 사용하는 경우
1: 모두 사용하지 않는 경우 
따라서, 결괏값 리턴시 -1을 통해 아무것도 입지 않는 경우를 제외하여 
최소 1개 이상의 의상을 입는 경우의 수만 리턴할 수 있도록 함 
(출처 구글링)
'''
def solution(clothes):
    answer = 0
    tmp=dict() 
    for c in clothes : 
        type=c[1]
        tmp[type] = tmp.get(type,0) + 1 
        
    answer=1
    for type,cnt in tmp.items() : 
        answer*=(cnt+1)
    answer-=1
    
    return answer

Q.베스트 앨범 #*** 

def solution(genres, plays):
    answer = []
    dic1={}
    dic2={}
    for i , (g,p) in enumerate(zip(genres, plays)) : #dic1 : 장르 인덱스 , 값 정리 (리스트로 저장)
        #print(i,g,p)
        if g not in dic1 : 
            dic1[g] = [(i,p)]
        else :
            dic1[g].append((i,p))
        #print(dic1) #{'classic': [(0, 500), (2, 150), (3, 800)], 'pop': [(1, 600), (4, 2500)]}
        
        if g not in dic2 : #dic2 : 장르별 합계
            dic2[g] = p 
        else : 
            dic2[g] += p 
        #print(dic2) #{'classic': 1450, 'pop': 3100} 
        
    for (k,v) in sorted(dic2.items(), key=lambda x:x[1], reverse=True) : #같은 장르 내에서는 최대 2곡까지 
        for (i,p) in sorted(dic1[k], key=lambda x:x[1], reverse=True)[:2]: 
            answer.append(i)
    return answer