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

- 처음엔 그냥 bfs로 하려고 하였으나 시간초과 문제로 인해 실패.

- 다른 방식으로 고안 : 가로축으로 한칸씩 늘려가면 노란색 칸은 한칸, 갈색 칸은 두칸씩 증가한다.

- 세로축으로 이동한다면 노란색 칸은 현재 노란색 한줄만큼 늘고, 갈색 칸은 두칸씩 증가한다.

- 따라서, 현재 가로축 길이에서 세로축으로 늘렸을 때, 문제의 조건에 맞는지 검사해주면 된다.

- yellow % y == 0으로 세로로 늘렸을때 노란색 개수가 나누어 떨어지는지 확인하고, b + 2 * ( yellow // y - 1) == brown으로 노란색 개수가 yellow에 도달할 정도로 세로로 늘렸을 때, brown도 도달하는지 확인한다.

- 여기에 추가적으로 늘렸을때 가로축이 더 긴지 확인하면 된다. (cy >= cx + yellow // y - 1)

from collections import deque

def solution(brown, yellow):
    answer = []
    queue = deque([[3, 3, 8, 1]])
    loopcount = 0
    while queue:
        cx, cy, b, y,= queue.popleft()
        if b == brown and y == yellow:
            answer = [cy, cx]
            break
        if yellow % y == 0 and b + 2 * (yellow // y - 1) == brown:
            if cy >= cx + yellow // y - 1:
                answer = [cy, cx + yellow // y - 1]
                break
        queue.append([cx, cy+1, b+2, y+1]) # 오른쪽 이동


    return answer

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

- itertools의 combinations 썼다가 시간초과가 났는데 간단하게 풀 수 있었음.

- 그냥 옷을 입거나 입지 않는 경우가 있으므로 옷의 종류별로 모든 경우를 곱해준다.

- 마지막에 옷을 입지 않는 경우를 -1 해주면 된다.

def solution(clothes):
    answer = 1
    clo = {}
    for cloth, types in clothes:
        if clo.get(types) == None: 
            clo[types] = 0
        clo[types] += 1

    p = clo.values()
    for i in p:
        answer *= (i+1)

    return answer - 1

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

- 처음에는 그냥 구간 나누어서 구간의 최댓값으로 맨 앞자리부터 채우는 방식으로 구현하였음.

- 10번에서 무한정 시간초과가 나서 잘 안되어서 다른 방식으로 구현.

- 다음은 잘 안됬던 소스

def get_max(number, src, dest):
    num = number[src]
    idx = src
    for i in range(src, dest):
        if num < number[i]:
            num = number[i]
            idx = i
        if number[i] == 9:
            break
    
    return (num, idx+1)

def solution(number, k):
    length = len(number)
    nex = 0
    c = length-k
    answer = ''
    
    while True:
        m, nex = get_max(number,nex,length-c+1)
        answer += m
        if len(answer) == length-k:
            break
        c = c - 1
        
    return answer
    from collections import deque

- 개수가 최대 100만개라 그런거 같았음. 따라서 풀이 방식을 스택으로 그리디하게 구현

- 매 순간 스택에 넣을때 스택 맨 위 요소가 넣으려는 요소보다 작다면 계속 빼주다가 맨 위 요소가 더 커지면 그때 넣어줌, 단 빼줄 때 몇개 빼주었는지 카운팅 해주어야 함. 최대 k개 빼야 하므로.

- 번외로 k개를 빼지 못하였다면 마지막에 맨 뒤에서 k개 빼줌

def solution(number, k):
    stack = deque()
    delcnt = 0
    for i, n in enumerate(number):
        while stack and delcnt != k:
            if stack[-1] < n:
                delcnt += 1
                stack.pop()
            else:
                break
        stack.append(n)
    
    answer = "".join(stack)
    if delcnt < k: # 충분히 지우지 못한 경우 뒤에서부터 지워줌.
        answer = answer[:-(k-delcnt)]
        
    return answer

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

- 각각의 회전 케이스에 대해서 스택으로 괄호 검사를 하면 된다.

- {, [, (를 만나면 스택에 넣어주고, }, ], )를 만나면 스택에서 빼주면 되는데, 넣을때는 그냥 넣으면 되지만 뺄때는 스택이 비어 있는지, 뺀 괄호가 }, ], )에 매칭이 되는지를 검사해야 한다.

- for문을 빠져 나오고 나서는 괄호가 비어 있는지 확인해야 함. '{{{{{{' 같은 경우는 넣기만 하고 빠져나올 수 있음.

- 조건을 만족하는 모든 개수를 구하면 된다.

from collections import deque

def check(s):
    st = deque()
    for t in s:
        if t in ['[', '(', '{']:
            st.append(t)
        else:
            if len(st) == 0:
                return False
            temp = st.pop()
            if (temp == '[' and t == ']') or (temp == '(' and t == ')') or (temp == '{' and t == '}'):
                continue
            return False
    if st: # 스택에 차있으면 False임! 이거 처리 안해서 13번 통과 못했었음.
        return False

    return True

def solution(s):
    answer = 0
    for i in range(len(s)):
        temp = s[i:] + s[:i] # 회전
        if check(temp):
            answer += 1
    return answer

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

- Floyd 알고리즘을 적용하여 모든 정점에서 다른 정점에 도달하는 최소 거리를 구해준다.(최대 50개의 마을까지이므로, 더 늘어나면 dijkstra 알고리즘 적용)

- 이후 distance[1]을 조사하여 1번 마을에서 K 거리 이내의 마을들의 개수를 출력해주면 된다.

import copy
def solution(N, road, K):
    INT_MAX = 9999999999
    matrix = [[INT_MAX] * (N+1) for _ in range(N+1)]
    for a, b, c in road:
        if matrix[a][b] > c:
            matrix[a][b] = c
            matrix[b][a] = c

    distance = copy.deepcopy(matrix) 

    for i in range(1, N+1):
        distance[i][i] = 0

    # floyd Algorithm
    for i in range(1, N+1):
        for j in range(1, N+1):
            for k in range(1, N+1):
                distance[j][k] = min(distance[j][k], distance[j][i] + distance[i][k])


    # 1에서 도달 가능한 개수 출력
    answer = len(list(filter(lambda x:x<=K, distance[1])))

    return answer

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

- 정렬 문제인데 정렬로 하면 좀 복잡해지는거 같아서 이진 탐색으로 구현함.

- 최대 나올수있는 결과값을 citations의 최댓값으로 잡아두고, 절반씩 나눠가면서 h값의 조건과 맞는지 조사하고, 조건이 맞다면 결과를 저장해 둔 뒤 오른쪽 구간을 검사

- 조건이 맞지 않다면 왼쪽 구간을 검사한다.

def solution(citations):
    answer = 0
    visited = set()
    left = 0
    right = max(citations)

    while left <= right:
        temp = (left + right) // 2
        larger = 0

        for c in citations:
            larger = larger + 1 if c >= temp else larger

        if len(citations) - larger <= temp and temp <= larger:
            answer = temp
            left = temp + 1
        else:
            right = temp - 1

    return answer

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

- get_distance로 현재 알파벳에서 얼마나 돌려야 목표 알파벳이 나오는지 최소 이동거리 구해 준다.

- get_next로 왼쪽/오른쪽 얼마나 이동해야하는지 구하는데.. 그리디를 사용해야 된다고 해서 0이 아닌 수까지의 거리가 짧은 방향으로 이동하게끔 구현을 하였음. 하지만 왼쪽-오른쪽 위치가 같은 경우를 따로 처리하지 않았음에도 정답이 나와서 이상함..

- 여튼, 매 순간 최소 이동거리와 돌려야 하는 횟수를 더해주면 된다.

def get_distance(c):
    p1 = abs(ord(c) - ord('A')) # 정방향
    p2 = abs(ord('Z') - ord(c) + 1) # 역방향
    return min(p1, p2)

def get_next(arr, idx):
    p = idx
    right_move = 0
    while True:
        p = (p + 1) % len(arr)
        right_move += 1
        if arr[p] != 0:
            break

    t = idx
    left_move = 0
    while True:
        t = (t - 1) % len(arr)
        left_move += 1
        if arr[t] != 0:
            break

    if right_move <= left_move:
        return (p, right_move)
    else:    
        return (t, left_move)



def solution(name):
    answer = 0

    distance = [0] * len(name)
    for i, p in enumerate(name):
        distance[i] = get_distance(p)

    answer = distance[0]
    distance[0] = 0
    idx = 0
    while sum(distance) != 0:
        idx, movement = get_next(distance, idx)
        answer += movement
        answer += distance[idx]
        distance[idx] = 0

    return answer

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

- 1, 2, 3, 4, 5, 6, 7, 8을 예시로 들었을때, 다음 라운드에서는 (1, 2 승자), (3, 4 승자), (5, 6 승자), (7, 8 승자)가 도달한다.

- 즉, 본인의 위치가 큰 순서 // 2로 줄게 된다. 따라서 작은 순위인 경우에는 큰 순위로 맞춰준 다음(+1) 2로 나눈다.

- 진행하다가 a == b, 즉, 작은 순위 + 1 = 큰 순위가 될 때 맞붙게 되므로, 그때의 라운드를 리턴해주면 된다.

def solution(n,a,b):
    answer = 1

    while True:
        if a % 2 == 1:
            a = a + 1
        if b % 2 == 1:
            b = b + 1
        if a == b:
            break
        answer += 1
        a = a // 2
        b = b // 2


    return answer

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

- 전화번호 전체를 자릿수 기준으로 정렬

- 자릿수가 낮은 전화번호부터 자리수를 늘려가면서 딕셔너리에 있는지 없는지 조사

- 딕셔너리에 있다면 접두사가 있는것이므로 false로 바꾸고 리턴

- 모든 케이스에서 없다면 true 리턴

def solution(phone_book):
    answer = True
    dic = {}
    phone_book.sort(key=lambda x:len(x))
    for phone in phone_book:
        for i in range(len(phone)):
            if dic.get(phone[:i]) != None:
                answer = False
        if answer == False:
            break
        dic[phone] = 1

    return answer

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

- 우선순위를 저장해둘 prior_copy를 만들어 둔 다음에 오름차순으로 정렬을 시킨다.

- 즉, prior_copy의 마지막 요소가 출력되어야 하는 요소의 우선순위

- queue를 돌면서 우선순위가 가장 높으면 출력하고, 아니라면 큐의 마지막에 넣어야 한다, 하지만 우선순위가 같은 케이스도 있으므로 우선순위와 인덱스를 같이 queue에 넣어둔다.

- 우선순위가 가장 높은걸 출력하되, 문제의 location을 프린터가 출력할 때, 해당 location이 몇번째로 출력되는지 나타내면 된다.

import copy
from collections import deque

def solution(priorities, location):
    prior_copy = copy.deepcopy(priorities)
    prior_copy.sort()
    queue = deque()
    for i, pr in enumerate(priorities):
        queue.append([pr, i]) # 우선순위랑 해당 인덱스 같이 삽입
    answer = 0

    while queue:
        pr, idx = queue.popleft()
        if pr == prior_copy[-1]:
            answer += 1
            if idx == location:
                break
            prior_copy.pop()
        else:
            queue.append([pr, idx])

    return answer

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