bright

programmers.co.kr/learn/courses/30/lessons/12909#

from collections import deque 

def solution(s):
    
    q = deque()
    q.append(0)
    ans = 1
    
    for i in range(len(s)):
        if s[i] == '(' :
            q.append('(')
        else :
            ans = q.pop()
        
        if ans == 0 : 
            return False 
            
    if len(q) > 1 :
        return False 
    return True

만약 '(' 로 시작하지 않거나, '(' 보다 ')' 가 많으면 ans = 0 이 된다 => False 

for 문이 끝난 다음 q에 뭔가 남아 있으면 '(' 가 ')' 보다 많았다는 것이다 => False 

programmers.co.kr/learn/courses/30/lessons/42842

def solution(brown, yellow):
    answer = []
    total = brown + yellow 
    
    p = set()
    for i in range(1,total+1):
        if total % i == 0 : 
            p.add( (i, total//i))
        
    for i,j in p :
        if i >= j :
            if (i-2)*(j-2) ==yellow:
                answer.append(i)
                answer.append(j)
                break 
    
    return answer

programmers.co.kr/learn/courses/30/lessons/42626#

def solution(scoville, K):
    import heapq
    answer = 0
    heapq.heapify(scoville)

    while scoville:
        first = heapq.heappop(scoville)

        if first >= K:
            break

        if len(scoville) <= 0:
            return -1
        
        second = heapq.heappop(scoville)
        heapq.heappush(scoville, first + second * 2)
        answer += 1
    
    return answer

1) heapq 사용 

2) heapq 초기화 코드 알아두기 ( heapify 사용 ) 

  => 함수에 리스트를 인자로 넘기면 리스트 내부의 원소들의 힙 구조에 맞게 재배치되며 최소값이 0번째 인덱스에 옴

3) while scoville => 인자가 0개인 경우 거르기

4) if len(scoville) <=0  -> 인자가 1개인 경우 거르기 ( 하나 꺼냈으니까 안남으면 1개였던 것 ) 

5) 인자가 2개 이상 남았으면 합치기 도전해보기 

programmers.co.kr/learn/courses/30/lessons/43165

def solution(numbers, target):
    sup= [0]
    for i in numbers:
        sub = []
        for j in sup : 
            sub.append(j+i)
            sub.append(j-i)
        sup = sub
    return sup.count(target)

def solution(phone_book):
    phone_book.sort() 
    
    answer = True
    
    for p in range( len(phone_book)-1 ) : 
        for i in phone_book[p+1:]:
            if phone_book[p] == i[:len( phone_book[p])] :
                answer = False 
                return answer 
    
    return answer

길이가 짧은 번호가 길이가 긴 번호의 접두사로 들어갈 수 있다. 

따라서 sort 해 준 뒤, 앞에서 부터 접두사로 들어가 있는지 확인한다. 

하나라도 나오면 바로 False 를 return 하고 없으면 이중 for 문이 끝난 뒤, True 를 리턴한다. 

from collections import deque 


def solution(priorities, location):
    
    queue = deque()
    for i in range( len(priorities) ):
        queue.append( [ priorities[i], i ] )
        
    answer = [] 
        
    while queue: 
        n = queue.popleft() 
        
        for q in queue: 
            if n[0] < q[0] :
                queue.append(n)
                n = []
                break 
        
        if n : 
            answer.append( n[1] )
            
    return answer.index(location) +1 

location은 index와 동일하다. 

step 1 ) queue 자료 구조를 사용하기 위해서 deque 정의 

step 2 ) 맨 처음 대기목록에서의 순서를 사용해서 return 값에 적용할 것이므로 우선순위와 location 을 리스트로 묶어 deque에 저장

step 3 ) 문제에 주어진 대로 구현, 나보다 우선순위가 높은 값이 뒤에 있으면 빼서 큐 맨 뒤로 보내고

             없으면 answer 배열에 넣음 

step 4 ) 처음에 입력받은 location 이 answer 의 어느 위치에 있는지 출력한다. 단, 출력 순위는 1 부터 시작하므로 +1 해준다. 

def solution(prices):
    answer = [0]* len(prices)
    
    for i in range( len(prices)-1 ):
        cnt = 1
        for j in range( i+1, len(prices) ):
            if prices[i] > prices[j] : 
                answer[i] = j -i 
                break 
        
        if answer[i] == 0 : 
            answer[i] = len(prices) - i -1
            
    return answer

def solution(s):
    
    tmp = list( map(int,s.split(' ')) )
    tmp.sort()

    answer = str(tmp[0])+' '+str(tmp[-1])
    return answer

def solution(number, k):
    stack = [number[0]]
    for num in number[1:]:
        while len(stack) > 0 and stack[-1] < num and k > 0:
            k -= 1
            stack.pop()
        stack.append(num)
    if k != 0:
        stack = stack[:-k]
    return ''.join(stack)

1. 분류 : 스택 / 큐 

2. 풀이 방법 

큰 수를 앞 쪽에 배치하는 문제이다. 가장 큰 수가 나올 때 까지 스택에 넣고 빼고를 반복한다. 

programmers.co.kr/learn/courses/30/lessons/42883

def solution(n):
    answer = 0
    
    dp = [0]* ( n+1 ) 
    dp[1] = 1 
    dp[2] = 2 
    
    if n < 3 : 
        answer = dp[n]
    else: 
        for i in range(3,n+1):
            dp[i] = ( dp[i-1]+ dp[i-2]  ) % 1000000007 
        answer = dp[n]  
    
    return answer

1. 분류 : 다이나믹 프로그래밍 

2. 풀이 : 

가장 기초적인 다이나믹 프로그래밍 문제이므로 잘 이해하고 넘어간다. 

왼쪽 부터 i-1 까지의 길이가 덮여 있으면, 2x1 을 채우는 경우의 수는 1가지 밖에 없다. 

왼쪽 부터 i-2 까지의 길이가 덮여 있으면 2x2 를 채우는 경우의 수는 2가지이지만, 모두 세로인 경우는 위의 방식에서도 count 되므로 가로로 채우는 경우의 수 1가지 라고 할 수 있다. 

따라서 점화식은 An = An-2 + An-1 이 된다. 

3. 유의사항 :

수가 아주 커질 수 있으므로  % 1000000007  처리를 어디서 하느냐에 따라서 효율성 문제가 걸릴 수 있다. 

나누기 연산한 값은 항상 동일하므로 dp 리스트 안에 넣는 과정에서 나눠 주자 

( answer 에 넣을 때 나누거나 return 할 때 나누면 효율성부분 점수 받기가 어렵다 )