초이의 끄적끄적

프로그래머스 스택/큐

# 다리를 지나는 트럭 (Level2)

• 앞 쪽에 위치한 트럭이 우선적으로 다리를 건너야 하기 때문에 FIFO 구조
• 리스트의 pop(0)은 0(n)의 시간복잡도를 가지고 deque의 popleft()는 O(1)의 시간복잡도를 가지기 때문에 deque사용한다
• 1초가 지날때마다 현재 다리에 있는 트럭의 무게와 다음으로 올라갈 트럭의 무게의 합이 최대 하중을 넘는지 확인한다
• 하중을 넘지 않는다면 다음 트럭을 올리고
• 그렇지 않다면 0을 더해 다리를 왼쪽으로 밀어낸다

- 첫번째 풀이(실패)

• Point. 하나의 테스트케이스에서 시간초과가 났다 -> sum이 O(n)이라 시간초과 발생

from collections import deque
def solution(bridge_length, weight, truck_weights):
    time = 0
    truck_q = deque(truck_weights)
    q = deque([0] * bridge_length)
    
    while q:
        time += 1
        q.popleft()
        if truck_q:
            if sum(q) + truck_q[0] <= weight:
                q.append(truck_q.popleft())
            else:
                q.append(0)
    
    return time

- 두번째 풀이 (성공) -> sum대신 다리의 무게를 따로 관리해준다

from collections import deque
def solution(bridge_length, weight, truck_weights):
    time = 0
    truck_q = deque(truck_weights)
    q = deque([0] * bridge_length)
    t_weight = 0 # 현재 다리의 무게
    
    while q:
        time += 1
        # 나갈 트럭이 있다면 그 무게를 빼준다
        if q[0] != 0: t_weight -= q[0]
        q.popleft()
        if truck_q:
            # 다리의 무게와 대기하는 트럭의 크기가 weight값을 넘지 않으면 더해준다
            if t_weight + truck_q[0] <= weight:
                t_weight += truck_q[0]
                q.append(truck_q.popleft())
            else:
                q.append(0)

    return time

* 시간복잡도를 생각하는 습관을 길러야겠다

wiki.python.org/moin/TimeComplexity

프로그래머스 스택/큐

# 프린터

- 나의 풀이

• 순서를 표시할 deque와 순서에 해당하는 중요도값을 저장한 dic값을 만들어줌
• 맨 앞 대기목록의 중요도와 나머지 중요도를 비교해 중요도가 가장 높으면 출력을 아니면 뒤로 빼준다 -> deque를 써야하는 이유 앞뒤로 빠져야되니까

from collections import deque
def solution(priorities, location):
    answer = 0
    queue = deque(i for i in range(len(priorities)))
    dic = {}
    
    for i in range(len(priorities)):
        dic[i] = priorities[i]
    
    while queue:
        tmp = queue.popleft()
        dic_value = list(dic.values())
        if dic[tmp] == max(dic_value):
            del dic[tmp]
            answer+=1
            if tmp == location:
                break
        else:
            queue.append(tmp)
        
    return answer

+ (GOOD) 풀이

• deque에 중요도와 순서를 함께 저장함

from collections import deque
def solution(priorities, location):
    answer = 0
    # v : 중요도 , i : 순서
    queue = deque((v,i) for i,v in enumerate(priorities))
    
    while queue:
        item = queue.popleft()
        if item[0] < max(queue)[0]:
            queue.append(item)
        else:
            answer+=1
            if item[1] == location:
                break
        
    return answer

# 자연수 뒤집어 배열로 만들기

def solution(n):
    answer = []
    for i in str(n):
        answer.append(int(i))
    answer.reverse()
    return answer
    #return list(map(int, reversed(str(n))))

# 나누어 떨어지는 숫자 배열

def solution(arr, divisor):
    answer = []
    for i in arr:
        if i%divisor == 0:
            answer.append(i)
    
    if len(answer) == 0:
        answer = [-1]
    else:
        answer.sort()
    return answer

# 시저 암호

def solution(s, n):
    answer = ''
    alpa = 'abcdefghijklmnopqrstuvwxyz'
    Alpa = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    for i in s:
        if i in alpa:
            answer += alpa[(alpa.index(i)+n)%26]
        elif i in Alpa:
            answer += Alpa[(Alpa.index(i)+n)%26]
        else:
            answer += " "
            
    return answer

# 콜라츠 추측

def solution(num):
    answer = 0
    while num!=1:
        if num % 2 == 0:
            num = num//2
        else:
            num = num*3 +1
        answer+=1
        if answer == 500:
            answer =-1
            break
        
    return answer

# 하샤드 수

def solution(x):
    answer = True
    x_sum = sum(int(i) for i in str(x))
        
    if x % x_sum != 0:
        answer = False

    return answer

# 제일 작은 수 제거하기

def solution(arr):
    answer = []
    arr.remove(min(arr))
    if len(arr)==0:
        answer = [-1]
    else:
        answer = arr
    return answer

# x만큼 간격이 있는 n개의 숫자

def solution(x, n):
    answer = []
    for i in range(1,n+1):
        answer.append(x*i)
    return answer

# 평균 구하기

def solution(arr):
    return sum(arr)/len(arr)

# 짝수와 홀수

def solution(num):
    answer = ''
    if num%2 == 0:
        answer = "Even"
    else:
        answer =  "Odd"
    return answer

# 핸드폰 번호 가리기

def solution(phone_number):
    return '*'*(len(phone_number)-4)+ phone_number[-4:]

# 직사각형 별찍기

a, b = map(int, input().strip().split(' '))
for i in range(b):
    print('*'*a)

프로그래머스 - 깊이/너비 우선 탐색(DFS/BFS)

# 여행경로 (Level 3)

• Point . dic로 그래프 만들고 DFS로 풀기

from collections import defaultdict
def solution(tickets):
    # 특정 티켓의 인접 리스트를 구하는 함수
    def init_graph():
        routes = defaultdict(list)
        for key, value in tickets:
            routes[key].append(value)
        return routes

    # 스택을 사용한 DFS
    def dfs():
        stack = ["ICN"] # 첫시작은 ICN
        path = []  # 가려고하는 경로를 저장하는 변수
        while stack:  # stack이 비어있을 때까지
            top = stack[-1]
            # 특정 공항에서 출발하는 표가 없다면 또는 있지만 티켓을 다 써버린 경우
            if top not in routes or len(routes[top]) == 0:
                path.append(stack.pop())
            else:
                stack.append(routes[top].pop(0))
        return path[::-1]

    routes = init_graph() # 그래프로 만들기
    for r in routes: # 알파벳순 정렬
        routes[r].sort() 
    answer = dfs() # 경로 구하기
    
    return answer

프로그래머스 - 깊이/너비 우선 탐색(DFS/BFS)

# 단어 변환 (Level 3)

• Point. 그래프 문제인 이유 : 한 개의 알파벳만 달라 다음에 올 수 있는 단어를 방문하여 target값을 찾는다
• 방문한(pop)한 원소 temp가 방문할 수 있는 값은 temp와 한 개의 알파벳만 다른 words 원소 값이다.

from collections import deque
def solution(begin, target, words):
    answer = 0 # 변환할 수 없는 경우 0 return
    queue = deque()

    for i in words: # 한 개의 알파벳만 다를 경우
        count = 0
        for j in range(len(begin)):
            if begin[j] != i[j]:
                count+=1
        if count == 1:
            queue.append([i,0]) 
            words.remove(i)
    
    while queue: 
        temp, idx = queue.popleft() 
        idx += 1
        if temp == target: # 변환이 가능한 경우 몇단계인지 저장
            answer = idx
        else:
            for i in words:
                count = 0
                for j in range(len(begin)):
                    if temp[j] != i[j]:
                        count+=1
                if count == 1:
                    queue.append([i,idx])
                    words.remove(i)
                    
    return answer

# 문자열을 정수로 바꾸기 

def solution(s):
    return int(s)

# 자릿수 더하기

• Point. 문자열로 변환해 한자리씩 들고온 후, 다시 정수형으로 변환해 더해준다

def solution(n):
    answer = 0
    for i in str(n):
        answer+=int(i)

    return answer

# 정수 내림차순으로 배치하기

• Tip. 리스트 합쳐서 하나의 문자열로 바꾸는 함수 : '구분자'.join(리스트) 

def solution(n):
    answer = ""
    n_list = list(str(n))
    n_list.sort(reverse=True)
    
    for i in n_list:
        answer+=i
    return int(answer)

    # return int("".join(n_list))

프로그래머스 - 깊이/너비 우선 탐색(DFS/BFS)

# 타겟 넘버 (Level 2) 

• Point. 타겟 넘버가 그래프 문제인 이유 -> 다음 인덱스에 해당하는 numbers 원소를 더하거나 빼 값을 방문한다.
• 방문한(pop)한 원소 temp가 방문할 수 있는 값은 temp 다음 인덱스에 위치한 numbers원소를 +또는 - 한 값이다.

from collections import deque
def solution(numbers, target):
    answer = 0
    queue = deque()
    n = len(numbers)
    queue.append([numbers[0],0])
    queue.append([-1*numbers[0],0]) 
    #print(queue)
    while queue: # queue가 빌때가지 반복
        temp, idx = queue.popleft() 
        idx += 1
        if idx < n:
            queue.append([temp+numbers[idx], idx])
            queue.append([temp-numbers[idx], idx])
            #print(queue)
        else:
            #print(temp)
            #print(queue)
            if temp == target:
                answer += 1
                #print("count up")
        
    return answer

※ 참고 포스팅 : 프로그래머스 level2 타겟넘버(BFS/DFS)

# 문자열 내 p와 y의 개수 

• 문자열 소문자로 바꾸는 함수 : lower()
• 문자열의 특정 문자 개수 세는 함수 : count()

def solution(s):
    if s.lower().count('p') == s.lower().count('y'):
        return True
    else :
        return False

# 문자열 내림차순으로 배치하기

• 문자열 리스트로 저장 후 정렬하기 sort 소문자 -> 대문자 순으로 정렬해줌

def solution(s):
    answer = ''
    s = list(s)
    s.sort(reverse = True)

    for i in s:
        answer += i
    return answer

# 문자열 다루기 기본 

• 숫자인지 판별하는 함수 : isdigit()

def solution(s):
    if s.isdigit() and (len(s) == 4 or len(s) == 6):
        return True
    else:
        return False

# 2016년 

• datetime 모듈을 사용하여 날짜의 요일을 받아온다 
• 날짜 생성하기 : datetime(년, 월, 일, 시, 분, 초, 밀리 초)
• 요일 반환 (0:월, 1:화, 2:수, 3:목, 4:금, 5:토, 6:일) : weekday()

import datetime as dt
def solution(a, b):
    answer = ''
    week_list = ['MON','TUE','WED','THU','FRI','SAT','SUN']
    x = dt.datetime(2016, a, b,1,1,1)
    answer = week_list[x.weekday()]

    return answer

+ 다른 사람 풀이

def getDayName(a,b):
    months = [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    days = ['FRI', 'SAT', 'SUN', 'MON', 'TUE', 'WED', 'THU']
    return days[(sum(months[:a-1])+b-1)%7]

프로그래머스 - 스택/큐

# 주식가격 (Level2)

• 주식가격이 떨어졌을 때도 시간이 지났기 때문에 시간을 더해야한다. -> 예시의 prices가 3일 경우

def solution(prices):
    answer = [0] *len(prices) #prices값과 동일한 길이의 리스트로 초기화
    for i in range(len(prices)):
        for j in range(i+1,len(prices)):
            if prices[i] > prices[j]:
                answer[i] +=1
                break
            else:
                answer[i] +=1
            print(answer)
                
    return answer

프로그래머스 - 힙(Heap)

# 더 맵게 (Level2)

• Point. 파이썬 heapq 모듈 사용하기 -> 안하면 효율성 ㄴㄴ
• 최댓값, 최소값을 뽑을 때는 heap을 사용하라
• 시도 1) if문 없이 짜면 heap 갯수가 1개 일때 오류가 뜬다
• 시도 2) if answer == len(scoville)-1 : 로 할 경우 맨 마지막 원소가 K보다 클 경우를 확인하지 못하고 -1 return 

import heapq
def solution(scoville, K):
    answer = 0
    heap = []
    
    for i in scoville:
        heapq.heappush(heap, i)
    
    while heap[0] < K:
        if len(heap) >=2 : heap_min1 = heapq.heappop(heap)
        if len(heap) >=1 : heap_min2 = heapq.heappop(heap)
        heapq.heappush(heap, heap_min1 + (heap_min2*2))
        answer += 1
        if answer == len(scoville):
            return -1
    
    return answer