Binary Journey

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

answer = 0    # 답
N = 0         # 던전 개수
visited = []  # 방문처리

def dfs(k, cnt, dungeons):
    global answer
    if cnt > answer: # 최대 방문 던전 수 경신
        answer = cnt
    for j in range(N):
        # 최소 피로도 조건 충족, 방문하지 않은 던전
        if k >= dungeons[j][0] and not visited[j]:
            visited[j] = 1
            dfs(k - dungeons[j][1], cnt + 1, dungeons)
            # 다른 곳부터 시작했을 때 모든 경우의 수를 따짐
            visited[j] = 0

def solution(k, dungeons):
    global N, visited
    N = len(dungeons)
    visited = [0] * N
    dfs(k, 0, dungeons)
    return answer

* 여전히 어려운 dfs

참고: https://hkim-data.tistory.com/65

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

def solution(number, k):
    answer = []
    for num in number:
        if not answer:
            answer.append(num)
            continue
        if k > 0:
            while answer[-1] < num:
                answer.pop()
                k -= 1
                if not answer or k <= 0:
                    break
        answer.append(num)
    answer = answer[:-k] if k > 0 else answer
    return ''.join(answer)

* 스택을 활용

* k 횟수가 0보다 크고 answer의 마지막보다 큰 수가 나타났을 때 pop

참고: https://velog.io/@soo5717/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%81%B0-%EC%88%98-%EB%A7%8C%EB%93%A4%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC

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

from itertools import permutations

def solution(numbers):
    answer = []
    nums = [n for n in numbers]
    per = []
    for i in range(1, len(numbers)+1):
        per += list(permutations(nums, i))
    new_nums = [int(("").join(p)) for p in per]
    for n in set(new_nums):
        if n < 2:
            continue
        check = True
        for i in range(2, int(n**0.5) + 1):
            if n % i == 0:
                check = False
                break
        if check:
            answer.append(n)
    return len(answer)

* permutations 는 분리된 숫자들을 순열로 조합해주는 함수라고 한다.. 굿

참고: https://dev-note-97.tistory.com/99

출처: https://school.programmers.co.kr/learn/courses/30/lessons/42842

def solution(brown, yellow):
    answer = []
    넓이 = brown + yellow
    for 세로 in range(1, 넓이 + 1):
        if 넓이 % 세로 == 0:
            가로 = 넓이 // 세로
            if 가로 >= 세로 and brown == 2 * 가로 + 2 * 세로 - 4:
                return [가로, 세로]
    return answer

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

def solution(citations):
    citations.sort()
    for i, citation in enumerate(citations):
        if citation >= len(citations) - i:
            return len(citations) - i
    return 0

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

import heapq
def solution(operations):
    answer = []
    while operations:
        o, num = operations.pop(0).split()
        if o == "I":
            heapq.heappush(answer, int(num))
        elif answer and o == "D" and int(num) > 0:
            answer.pop()
        elif answer and o == "D" and int(num) < 0:
            answer.pop(0)
        answer.sort()
    if answer:
        return [answer[-1], answer[0]]
    else:
        return [0,0]

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

테스트 케이스 한 곳에서 계속 시간초과 에러 남

def solution(bridge_length, weight, truck_weights):
    answer = 0
    truck_weights.reverse()
    bridge = [0 for i in range(bridge_length)]
    while bridge:
        answer += 1
        bridge.pop(0)
        if truck_weights:
            sum_weights = sum(bridge)
            if sum_weights + truck_weights[-1] > weight:
                bridge.append(0)
            else:
                bridge.append(truck_weights.pop())
    return answer

sum 때문에 시간초과 나서 바꿨다

def solution(bridge_length, weight, truck_weights):
    answer = 0
    truck_weights.reverse()
    bridge = [0 for i in range(bridge_length)]
    sum_weights = sum(bridge)
    while bridge:
        answer += 1
        off = bridge.pop(0)
        sum_weights -= off
        if truck_weights:
            if sum_weights + truck_weights[-1] > weight:
                bridge.append(0)
            else:
                on = truck_weights.pop()
                bridge.append(on)
                sum_weights += on
    return answer

def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge = [0 for i in range(bridge_length)]
    while bridge:
        answer += 1
        bridge.pop(0)
        if truck_weights:
            sum_weights = sum(bridge)
            if sum_weights + truck_weights[0] > weight:
                bridge.append(0)
            else:
                bridge.append(truck_weights.pop(0))
    return answer

레벨에 비해 쉬운 문제지만

혼자서 문제의도를 지켜서 큐 만들어 풀었다는 거에 매우 만족

예전에 풀어놨던 문제라 점수는 알 수 없지만 그래도 아주 만족

from collections import deque
def solution(progresses, speeds):
    wait_for_complete = deque()
    for progress, speed in zip(progresses, speeds):
        div, mod = divmod((100 - progress), speed)
        if mod > 0 :
            wait_for_complete.append(div + 1)
        else:
            wait_for_complete.append(div)
    기준 = [0, wait_for_complete.popleft()]
    answer = [1]
    while wait_for_complete:
        second = wait_for_complete.popleft()
        if second <= 기준[1]:
            answer[기준[0]] += 1
        else:
            기준[0] += 1
            answer.append(1)
            기준[1] = second
    return answer

def solution(progresses, speeds):
    wait_for_complete = []
    for progress, speed in zip(progresses, speeds):
        div, mod = divmod((100 - progress), speed)
        if mod > 0 :
            wait_for_complete.append(div + 1)
        else:
            wait_for_complete.append(div)
    기준 = [0, wait_for_complete.pop(0)]
    answer = [1]
    while wait_for_complete:
        second = wait_for_complete.pop(0)
        if second <= 기준[1]:
            answer[기준[0]] += 1
        else:
            기준[0] += 1
            answer.append(1)
            기준[1] = second
    return answer

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

사실 조건은 4개로 보아야 함

오랜만에 +2점...!

from functools import cmp_to_key
def cmp_sum(x, y):
    return y[1] - x[1]
def cmp_by_condition(x, y):
    x_index, x_play = x
    y_index, y_play = y
    if x_play == y_play:
        return x_index - y_index
    else:
        return y_play - x_play

def solution(genres, plays):
    answer = []
    _dict1 = dict()
    _dict2 = dict()
    for i, (genre, play) in enumerate(zip(genres, plays)) :
        if genre not in _dict1.keys():
            _dict1[genre] = [(i, play)]
            _dict2[genre] = play
        else:
            _dict1[genre].append((i, play))
            _dict2[genre] += play
    tmp = sorted(_dict2.items(), key=cmp_to_key(cmp_sum))
    for (genre, _) in tmp:
        new = [x[0] for x in sorted(_dict1[genre], key=cmp_to_key(cmp_by_condition))]
        answer += new[:2]
    return answer

추천풀이 중 내가 생각했던 방법이랑 비슷했던 풀이

def solution(genres, plays):
    answer = []

    dic1 = {}
    dic2 = {}

    for i, (g, p) in enumerate(zip(genres, plays)):
        if g not in dic1:
            dic1[g] = [(i, p)]
        else:
            dic1[g].append((i, p))

        if g not in dic2:
            dic2[g] = p
        else:
            dic2[g] += p

    for (k, v) in sorted(dic2.items(), key=lambda x:x[1], reverse=True):
        for (i, p) in sorted(dic1[k], key=lambda x:x[1], reverse=True)[:2]:
            answer.append(i)

    return answer

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

머리로는 뭔가 할 수 있을 듯 말듯한데

결국 구글의 도움을 받아야 했음

def solution(rows, columns, queries):
    answer = []
    box = []
    for i in range(rows):
        row = []
        for j in range(columns):
            row.append(columns * i + j + 1)
        box.append(row)
    for querie in queries:
        행1, 열1, 행2, 열2 = querie
        
        행1 -= 1; 열1 -= 1; 행2 -= 1; 열2 -= 1
        tmp = box[행1][열1]
        small = tmp
        # left
        for i in range(행1 + 1, 행2 + 1):
            box[i-1][열1] = box[i][열1]
            small = min(small, box[i][열1])
        # bottom
        for i in range(열1 + 1, 열2 + 1):
            box[행2][i-1] = box[행2][i]
            small = min(small, box[행2][i])
        # right
        for i in range(행2 - 1, 행1 - 1, -1):
            box[i+1][열2] = box[i][열2]
            small = min(small, box[i][열2])
        # top
        for i in range(열2 - 1, 열1 - 1, -1):
            box[행1][i+1] = box[행1][i]
            small = min(small, box[행1][i])
            
        box[행1][열1+1] = tmp
        answer.append(small)
    return answer

참고:https://latte-is-horse.tistory.com/146

더 좋은 코드를 발견해서 달아 놓음

def rotate(x1, y1, x2, y2, graph, answer):
    # 오른쪽, 아래, 왼쪽, 위 순
    dx = 0, 1, 0, -1
    dy = 1, 0, -1, 0
    d, x, y, tmp = 0, x1, y1, 10000
    min_val = 10000
    while d < 4:
        nx = x + dx[d]
        ny = y + dy[d]
        min_val = min(min_val, graph[x][y])
        # 범위 안인 경우
        if x1 <= nx <= x2 and y1 <= ny <= y2:
            graph[x][y], tmp = tmp, graph[x][y]
            x, y = nx, ny
        else:
            d += 1
    graph[x1][y1] = tmp
    answer.append(min_val)


def solution(rows, columns, queries):
    answer = []
    graph = [[i + 1 for i in range(j * columns, (j + 1) * columns)] for j in range(rows)]
    for query in queries:
        x1, y1, x2, y2 = map(int, query)
        rotate(x1 - 1, y1 - 1, x2 - 1, y2 - 1, graph, answer)
    return answer

출처: https://intrepidgeeks.com/tutorial/rotate-programmer-matrix-border-python