초이의 끄적끄적

프로그래머스 - 깊이/너비 우선 탐색(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]

Deque란

• 주로 큐 구현에 사용
• Deque는 double-ended queue 의 줄임말로, 앞과 뒤에서 즉, 양방향에서 데이터를 처리할 수 있는 queue형 자료구조를 의미한다. 스택과 큐의 기능을 모두 가졌다.

+ 스택(Stack)

• 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 구조(LIFO) -> 오른쪽 끝에서 입출력
• 리스트 사용해 append(), pop() 사용

stack = [1,2,3]

# 원소 추가
stack.append(4) 
stack
>>> [1, 2, 3, 4]

# 가장 마지막 원소 삭제 후 그 값 리턴
top = stack.pop() 
print(top)
stack
>>> 4
>>> [1, 2, 3]

# 스택에서 원소를 제거하지 않고 가져오기만 할 때에는 [-1] 사용
top = stack[-1] 
top
stack
>>> 3
>>> [1, 2, 3]

※ pop() : 맨 마지막 요소 삭제 / pop(x) : x번째 요소를 리턴 후 삭제 -> x는 인덱스임

 + list.remove('값') : 인덱스가 아니고 값임

+ 큐(Queue)

• 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조(FIFO) -> 오른쪽에 입력 왼쪽으로 출력
• deque를 사용해 append(), popleft() 사용
• 데이터를 입력된 순서대로 처리해야 할 때, BFS(너비 우선 탐색) 구현 할 때 사용

※ 스택과 달리 큐를 list로 이용하지 않는 이유

 스택에서 list.append와 list.pop()을 이용했던 것처럼 list.append와 list.pop(0)을 이용하면 리스트를 큐처럼 사용할 수 있다. 하지만 pop()의 시간복잡도는 O(1)인 반면 pop(0)의 시간복잡도는 O(N)이기 때문에 시간이 오래 걸린다. 따라서 시간 복잡도를 고려해 리스트는 큐로 사용하지 않는다.

디큐 함수 ( from collections import deque)

• 스택 구현(오른쪽 끝에서 입출력) : append(), pop()
• 큐 구현 : appendleft(), pop(), append(), popleft()
• depue 확장하기 : extend(), extendleft()
• 리스트 처럼 수정 삭제 : insert(), remove()
• deque 내용 좌우로 반전 : reverse()
• 회전 : rotate(n)
• 모든 원소 제거 : clear()

from collections import deque # 모듈 임포트
queue = deque([4, 5, 6]) # 디큐 생성

# append(x) : 오른쪽(마지막)에 원소 추가(삽입)
queue.append(7)
queue.append(8)
print(queue)
>>> [4, 5, 6, 7, 8]

# popleft() : 왼쪽(앞쪽)부터 차례대로 제거와 반환
queue.popleft()
>>> 4
queue.popleft()
>>> 5
print(queue)
>>> [6, 7, 8]

# rotate(n) : 요소들을 값 만큼 회전 해주는 메소드
# 음수면 왼쪽으로, 양수면 오른쪽으로 회전
deq = deque(['a', 'b', 'c', 'd', 'e'])
deq.rotate(1)
>>> e a b c d

deq2 = deque(['a', 'b', 'c', 'd', 'e'])
deq3.rotate(-1)
>>> b c d e a

+ 스택/큐 관련 문제 정리  ( 프로그래머스 )

# 다리를 지나는 트럭 (Level2) : 2021.04.17 - [알고리즘] - [ 프로그래머스 / 파이썬 ] 다리를 지나는 트럭 - deque

# 주식가격 (Level2) : 2021.03.31 - [알고리즘] - [ 프로그래머스 / 파이썬 ] 주식가격

# 기능개발 (Level2) : 

# 프린터 (Level2) : 2021.04.15 - [알고리즘] - [ 프로그래머스 / 파이썬 ] 프린터 - deque

프로그래머스 - 스택/큐

# 주식가격 (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

힙 자료구조

• 데이터를 정렬된 상태로 저장하기 위해서 사용하는 파이썬 heapq(힙큐) 내장 모듈 사용
• heapq 모듈은 이진트리(binart tree)기반의 최소 힙(min heap) 자료구조를 제공한다
• 최대, 최소값을 가져올 때 많이 사용한다

힙 관련 함수들 (import heapq)

• 힙 생성 - heap = [] 
• 힙 원소 추가 - heapq.heappush(heap, 4)
• 힙에서 원소 삭제 heapq.heappop(heap)) // 가장 작은 원소 삭제 후 그 값 리턴
• 최솟값 삭제하지 않고 얻기 - heap[0]
• 기존 리스트를 힙으로 변환 - heapq.heapify(heap)

import heapq	# 모듈 임포트
heap = []		# 힙 생성

# 힙에 원소 추가
heapq.heappush(heap, 4)	
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)
print(heap)
>>> [1, 3, 7, 4]

# 힙에서 원소 삭제
print(heapq.heappop(heap))	# 가장 작은 원소 삭제 후 그 값 리턴
print(heap)	
>>> 1
>>> [3, 4, 7]

# 최소값 삭제하지 않고 얻기
print(heap[0])
>>> 3

# 기존 리스트를 힙으로 변환
heap = [4, 1, 7, 3, 8, 5]
heapq.heapify(heap)
print(heap)
>>> [1, 3, 5, 4, 8, 7]

+ 힙 정렬

import heapq

def heap_sort(nums):
  heap = []
  for num in nums:
    heapq.heappush(heap, num)
  
  sorted_nums = []
  while heap:
    sorted_nums.append(heapq.heappop(heap))
  return sorted_nums

print(heap_sort([4, 1, 7, 3, 8, 5]))

>>> [1, 3, 4, 5, 7, 8]

+ 최대 힙

• heapq 모듈은 최소 힙만 동작하기 때문에 최대 힙으로 하기 위해 요령이 필요
• 힙에 튜플(tuple)을 원소로 추가하거나 삭제하면, 튜플 내에서 맨 앞에 있는 값을 기준으로 최소 힙이 구성되는 원리를 이용한다
• 따라서, 최대 힙을 만들려면 각 값에 대한 우선순위를 구한 후, (우선 순위, 값) 구조의 튜플(tuple)을 힙에 추가하거나 삭제하면 됩니다. 그리고 힙에서 값을 읽어올 때는 각 튜플에서 인덱스 1에 있는 값을 취하면 됩니다. (우선순위에는 관심이 없으므로 )

import heapq

nums = [4, 1, 7, 3, 8, 5]
heap = []

for num in nums:
  heapq.heappush(heap, (-num, num))  # (우선 순위, 값)

while heap:
  print(heapq.heappop(heap)[1])  # index 1
  
>>> 8
>>> 7
>>> 5
>>> 4
>>> 3
>>> 1

+ K번째 최소값/최대값

• K번째 최소값을 구하기 위해서는 주어진 배열로 힙을 만든 후, heappop() 함수를 K번 호출하면 됩니다.

import heapq

def kth_smallest(nums, k):
  heap = []
  for num in nums:
    heapq.heappush(heap, num)

  kth_min = None
  for _ in range(k):
    kth_min = heapq.heappop(heap)
  return kth_min

print(kth_smallest([4, 1, 7, 3, 8, 5], 3))

>>> 4

+ 힙 개념 문제 :

2021.03.19 - [알고리즘] - 20210319_코테공부

+ 이중우선순위큐

https://programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스 - 힙(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

기본 딕셔너리 구조 - Key와 Value를 한 쌍으로 갖는 자료형

{Key1:Value1, Key2:Value2, Key3:Value3, ...}

※ key는 고유한 값이여야 한다. 중복 시 나머지 무시함

※ key에는 리스트 쓸 수 없다. value에는 가능

딕셔너리 선언

>>> dic = {}	# 딕셔너리 선언

>>> dic[1] = 'a' # 딕셔너리 쌍 추가
>>> dic['name'] = 'pey'
>>> dic
{1: 'a', 'name': 'pey'}
>>> dic[1]		# key 사용해 value 얻기
'a'

>>> del a[1]	# 딕셔너리 삭제 del a[key값] index아님
>>> a
{2: 'b', 'name': 'pey', 3: [1, 2, 3]}

딕셔너리 관련 함수들

• key 리스트 만들기 - a.keys() # dict_keys 객체 반환
• value 리스트 만들기 - a.values() # dict_values 객체 반환
• key, value 쌍 얻기 - a.items() # 튜플로 묶은 값을 dict_items 객체로 반환
• key : value 쌍 모두 지우기 - a.clear()
• key로 value 얻기 - a.get('키값')
  • a.get('name')과 a['name']과 동일한 결과값 
  • But 키가 존재하지 않을 경우, a.get('nokey')는 None을, a['nokey']는 오류 발생
• 해당 key가 딕녀서리 안에 있는지 조사하기 - in (True, False 반환)
  • ex) 'a' in dic: ~~~

※ dict_keys 객체는 리스트 고유의 append, insert, pop, remove, sort 함수는 수행할 수 없다. 때문에 list로 변환해서 사용해야됨 -> list(a.keys())

>>> a = {'name': 'pey', 'phone': '0119993323', 'birth': '1118'}
>>> a.keys()
dict_keys(['name', 'phone', 'birth'])

>>> a.values()
dict_values(['pey', '0119993323', '1118'])

>>> a.items()
dict_items([('name', 'pey'), ('phone', '0119993323'), ('birth', '1118')])

>>> a.clear()
>>> a
{}

>>> a.get('name')
'pey'

>>> 'name' in a
True

딕셔너리 정렬 -> 기본. sorted를 이용한다

- key값을 이용한 정렬

>>> dict = {'A' :1,'D' :4,'C' :3,'B' :2}
>>> sdict= sorted(dict.items()) # 오름차순 정렬
[('A', 1), ('B', 2), ('C', 3), ('D', 4)]

>>>sdict= sorted(dict.items(), reverse=True) # 내림차순 정렬
[('D', 4), ('C', 3), ('B', 2), ('A', 1)]

- value값을 이용한 정렬 

-> items()와 lamba를 사용한다

• 딕셔너리에 items() 메서드를 사용해주면 {"key" : value}의 형태를 [(key, value)]의 형태로 만들어 준다. -> 튜플
• 이를 sorted해주면 key값을 기준으로 오름차순으로 정렬해준다.
• value값으로 정렬하려면 lambda를 사용해주면 된다. ( [0]일 경우 key기준, [1]일 경우 value 기준 정렬 )
• 내림차순 정렬 시, reverse=True

>>> dict = {'A' :1,'D' :4,'C' :3,'B' :2}
>>> sdict= sorted(dict.items(), key= lamba x : x[1])
[('A', 1), ('B', 2), ('C', 3), ('D', 4)]

+ itemgetter를 사용한 정렬

• python의 내장모듈 operator를 이용한 정렬
• key = itemgetter(기준 인덱스)

>>> from operator import itemgetter
>>> dict = {'A' :1,'D' :4,'C' :3,'B' :2}
>>> sdict= sorted(dict.items(), key= itemgetter(1))
[('A', 1), ('B', 2), ('C', 3), ('D', 4)]

+ 딕셔너리 선언, 정렬 문제 : 

2021.03.16 - [알고리즘] - 20210316_코테공부

프로그래머스 - 해시

# 위장 (Level2)

def solution(clothes):
    answer = 1
    dic = {}
    for name, kind in clothes:
        if kind in dic:
            dic[kind] +=1
        else: dic[kind] = 1
    for i in dic.values():
        answer *=(i+1)

    return answer-1

# 베스트 앨범 (Level3)

• Point. 딕셔너리, 딕셔너리 정렬

1. 많이 재생된 장르 먼저 수록
2. 장르 내에서 많이 재생된 노래 먼저 수록
3. 장르별로 두 개씩(하나만 있으면 하나만)

def solution(genres, plays): 
    answer = [] 
    dic = {} # 장르 : (재생횟수, 고유번호)
    dic_count = {} # 장르별 재생횟수
    
    for i, (g,p) in enumerate(zip(genres, plays)):
        if g in dic:
            dic[g].append((p,i))
            dic_count[g] += p
        else:
            dic[g] = [(p,i)]
            dic_count[g] = p
    print(dic)
    print(dic_count)

    # 많이 재생된 장르순 정렬
    sorted_dic = sorted(dic_count.items(), key=lambda x: x[1], reverse=True) 
    print(sorted_dic) 
    
    for key in sorted_dic: # key값에 ('pop', 3100)
        play_list = dic[key[0]] #key[0]으로 해야 pop나옴
        print(play_list)

        # 많이 재생된 노래순 정렬
        play_list = sorted(play_list, key = lambda x : x[0], reverse=True)
        print(play_list)
        
        for i in range(len(play_list)): # 두개만 뽑아오기
            if i == 2: 
                break 
            answer.append(play_list[i][1]) 
            
    return answer

프로그래머스 - 해시 

# 완주하지 못한 선수

• 문자열 문제는 정렬부터 하고 보자. 

def solution(participant, completion):
    participant.sort()
    completion.sort()

    for par, com in zip(participant, completion) :
        if par != com :
            return par   # 예시 1번

    return participant[-1]         # 예시 2번

# 예시 1번
A = ['a','b','b','c'] 
B = ['a','b','c']
zip(A, B)  # [('a','a'), ('b','b'), ('b','c')]  # 차이 발생

# 예시 2번 - 1
A = ['a','b','c','c']   # 마지막 값 (중복된 값이 맨 뒤에)
B = ['a','b','c']
zip(A, B)  # [('a','a'), ('b','b'), ('c','c')]

# 예시 2번 -2
A = ['a','b','c']       # 마지막 값 (하나 다른 것이 맨 뒤에)
B = ['a','b]
zip(A, B)  # [('a','a'), ('b','b')]

+ (GOOD) 풀이 

• Point. 딕셔너리를 이용한 데이터 갯수 세기 -> collections 모듈

import collections

def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys())[0]

( collections : 참고 )