그냥 코딩하는 사람의 블로그

- bfs로 최단 경로를 찾아 준다.

- visited를 따로 두어 방문했던 정점을 다시 방문하지 않도록 함.

- bfs에서는 목적지에 처음 도달하였을 때가 최단 경로이므로 목적지에 도달하기만 하면 바로 return해주면 된다.

- queue가 비었을 때는 목적지로 갈수가 없는 케이스이므로 -1 리턴

from collections import deque

def bfs(maps):
    queue = deque()
    maxX = len(maps) - 1
    maxY = len(maps[0]) - 1
    visited = [[False] * (maxY + 1) for _ in range(maxX + 1)]
    queue.append([0, 0, 1])

    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    visited[0][0] = True

    while queue:
        cx, cy, c = queue.popleft()
        if cx == maxX and cy == maxY:
            return c

        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            if 0 <= nx and nx <= maxX and 0 <= ny and ny <= maxY:
                if visited[nx][ny] == False and maps[nx][ny] == 1:
                    visited[nx][ny] = True
                    queue.append([nx, ny, c+1])

    return -1

def solution(maps):
    return bfs(maps)

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

- 한개~전체 고르는것 까지 모두 permutation으로 경우의 수 계산

- 이후 겹치는 경우들도 있으므로 방문한 케이스들을 visited에 저장 및 재방문 시 생략

- 소수 구할때는 2~n의 제곱근까지만 검사하여 시간 단축

from itertools import permutations
import math

def check_prime(n):
    if n <= 1:
        return False
    elif n == 2:
        return True
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

def solution(numbers):
    answer = 0
    visited = set()
    for i in range(1, len(numbers)+1):
        allcase = list(permutations(numbers, i))
        for case in allcase:
            temp = int("".join(case))
            if temp not in visited:
                visited.add(temp)
                if check_prime(temp):
                    answer += 1
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

- 우선 모든 요소를 최소 히프에 넣어 준다.

- 히프의 맨 앞 요소(최솟값)이 k 이상이라면 종료하고, heap의 크기가 한개이면서, k 이상도 아니라면 스코빌 지수를 k 이상으로 할 수 없는 것이므로 -1로 변경한다.

- 최소 히프에서 두개의 요소를 꺼낸다(최솟값, 그다음 최솟값)

- 공식에 따라 최솟값 + 그다음 최솟값 * 2 한 값을 최소 히프에 다시 넣는 과정을 최솟값이 k 이상이 될때까지 반복한다.

import heapq

def solution(scoville, K):
    answer = 0
    heap = []
    for s in scoville:
        heapq.heappush(heap, s)

    while True:
        if heap[0] >= K:
            break
        if len(heap) == 1:
            answer = -1
            break
        t1 = heapq.heappop(heap)
        t2 = heapq.heappop(heap)
        t = t1 + t2*2
        heapq.heappush(heap, t)
        answer += 1


    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

- 스택의 맨 위 요소가 끝나려면 몇일 걸리는지 저장(days)

- 맨 위 요소가 끝나려면 걸리는 일동안 스택 요소들 모두 진행이 되므로 전체 스택에 대하여 (진행율 * 일)을 더해줌.

- 스택의 맨 위 요소부터 진행율이 100이 넘는다면 스택과 진행율 모두 pop 해줌. (진행율도 반드시 pop 해주어야 함.)

- 하나가 아닐수도 있으므로 여러개라면 모두 pop해주면서 count 해줌.

- count 해준 값을 answer에 저장하면 종료.

def solution(progresses, speeds):
    answer = []
    progresses = progresses[::-1]
    speeds = speeds[::-1]

    while True:
        remainder = (100 - progresses[-1]) % speeds[-1]
        days = (100 - progresses[-1]) // speeds[-1] 
        if remainder != 0:
            days = days + 1

        for i in range(len(progresses)):
            progresses[i] = progresses[i] + speeds[i] * days

        count = 0
        while progresses and progresses[-1] >= 100:
            count += 1
            progresses.pop()
            speeds.pop()

        answer.append(count)
        if not progresses:
            break
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

- bfs로 구현, 왼쪽에서 순차적으로 진행하면서 현재 요소의 값이 +일때와 , -일때 각각의 누적합을 큐에 저장

- 마지막 요소까지 방문한다면 그만 하되, target과 누적합이 같다면 개수 1 증가

- 전체 개수 리턴해주는 방식으로 구현

from collections import deque

def bfs(numbers, target):
    queue = deque()
    queue.append([numbers[0], 1])
    queue.append([-numbers[0], 1])
    answer = 0
    while queue:
        currentSum, idx = queue.popleft()
        if idx == len(numbers):
            if currentSum == target:
                answer += 1
            continue
        queue.append([currentSum + numbers[idx], idx+1])
        queue.append([currentSum - numbers[idx], idx+1])
    
    return answer
            
def solution(numbers, target):
    return bfs(numbers, target)

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

- 2번의 전체 검색으로 문제 해결

- 아이디에 따라 마지막으로 변화한 닉네임을 딕셔너리로 저장함.

- 이후 순차탐색 하면서 명령어에 맞는 문자열을 출력해주는 방식으로 구현

def solution(record):
    answer = []
    username = {}
    for st in record:
        temp = st.split()
        if temp[0] == 'Enter' or temp[0] == 'Change':
            username[temp[1]] = temp[2]
    
    for st in record:
        temp = st.split()
        if temp[0] == 'Enter':
            answer.append(username[temp[1]]+'님이 들어왔습니다.')
        elif temp[0] == 'Leave':
            answer.append(username[temp[1]]+'님이 나갔습니다.')
            
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

- 아무리 생각해도 맞는거 같아서 왜 안되나 찾아본 결과 계산 순서에 따라 계산 결과가 다르게 나타날수 있다고 함.. 따라서 나누기를 할 때는 곱이 모두 끝나고 나서 나누어 주어야 함.

- 시간 초과가 나서 w == h일때를 따로 두어서 해결

- w * h - (w + h - gcd(w, h))로 구하면 훨씬 쉽게 풀수 있다는데.. 이해가 잘 안되어서 일단 해결할 수 있는 방법으로 해결함. 

import math

def solution(w,h):
    if w > h:
        w, h = h, w
    answer = w * h
    
    if w == h:
        return w * h - w
    
    for i in range(1, w+1):
        answer -= (math.ceil(h * i / w) - math.floor(h * (i-1) / w))
        
    
        
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

- 요소의 개수가 100만개여서 루프를 여러번 돌면서 검사하면 시간초과가 날 것 같았음.

- 따라서 요소를 스택에 넣어두고, 검사하는 요소와 스택의 맨 위 요소가 같다면 스택에서 빼주는 방식으로 구현

- 마지막에 stack이 비어있다면 제거 가능한 문자열이다.

from collections import deque
def solution(s):
    stack = deque()

    for c in s:
        if len(stack) == 0:
            stack.append(c)
        else:
            if stack[-1] == c:
                stack.pop()
            else:
                stack.append(c)

    answer = 0 if stack else 1
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

- 어떻게 0이 나오는지 고민하다가 너무 오랜 시간이 걸려서 다른 사람의 자료를 참고함.

- 3진법과 거의 유사하나 나누어 떨어지는 경우(0이 나오는 경우) 나오는 몫을 하나 빼고 나머지를 4로 채우는 방식으로 진행하면 해결 가능

def convert_four(n):
    s = ''
    idx = 0
    while n != 0: 
        remainder = n % 3
        q = n // 3
        if n % 3 == 0:
            remainder = 4
            q = q - 1
        s = str(remainder) + s
        n = q

    return s

def solution(n):
    answer = ''
    k = convert_four(n)
    answer = k
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

- 문제를 잘 읽어야 하는 문제. 공백이 한개일수도 있고 여러개일 수도 있어서 split 함수를 사용하여서는 안됨.

- 앞에서 순차적으로 진행하면서 문자를 만났을 때는 대/소문자 변환과정, 공백을 만났을 경우에는 그대로 출력하도록 소스코드 작성

def solution(s):
    answer = ''
    count = 0
    for c in s:
        if c == " ":
            count = 0
            answer += c
        else:
            if count % 2 == 0:
                answer += c.upper()
            else:
                answer += c.lower()
            count += 1

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges