초이의 끄적끄적

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