hanbin.dev

recursion = int(input())
print("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.")

def q(recursion,cnt):
    print(cnt * "____" + "\"재귀함수가 뭔가요?\"")
    if recursion <= 0:
        print(cnt * "____" + "\"재귀함수는 자기 자신을 호출하는 함수라네\"")
    else:
        print(cnt * "____" + "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.")
        print(cnt * "____" + "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.")
        print(cnt * "____" +"그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"")
    
        q(recursion - 1, cnt + 1)
    print(cnt * "____" + "라고 답변하였지.")

q(recursion, 0)

문제 풀이 코드

def solution(board, moves):
    answer = 0
    result_stack = []

    for move in moves:
        for i, column in enumerate(board):
            if column[move - 1] != 0:
                if len(result_stack) > 0:
                    if (recent := result_stack.pop()) == column[move - 1]:  #1
                        answer += 2
                        board[i][move - 1] = 0
                        break
                    else:
                        result_stack.append(recent)
                result_stack.append(column[move - 1])
                board[i][move - 1] = 0
                break

    return answer

#1

왈러스 연산자를 사용해서 pop 한 값(recent)을 if else 네임스페이스에서 사용할 수 있도록 했다.

문제 풀이 코드

def solution(a, b):
    return sum([x*y for x,y in zip(a, b)])

졸리고 머리아파서 그냥 1단계 풀었다.

아이디어

DFS 문제이다.
예를 들어numbers : [ 1, 1, 1 ],target : 1이 들어왔다면 아래와 같은 이진 트리 구조를 갖는다.

노드의 종점에서 target 값과 비교해 같다면 answer에 +1을 해주는 것이다.

문제 풀이 코드

def solution(numbers, target):
    answer = 0
    def dfs(current_total, current_index, sign): # dfs(0,0,1)
        nonlocal answer

        current_total += numbers[current_index] * sign 

        if len(numbers) <= current_index + 1: # 1
            if current_total == target:
                answer += 1
        else: # 2
            dfs(current_total, current_index + 1, 1)
            dfs(current_total, current_index + 1, -1)
        return

    dfs(0,0,1)
    dfs(0,0,-1)
    return answer

#1

다음 인덱스가 존재하지 않을 때 (노드의 종점일때 )

#2

다음 인덱스가 존재 할 때 (노드의 종점이 아닐 때)

문제 풀이 코드

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)  #1 
    while True:
        answer += 1
        heapq.heappush(scoville,heapq.heappop(scoville) + heapq.heappop(scoville) * 2)  #2
        if scoville[0] >= K:  #3
            return answer
        elif len(scoville) <= 1:
            return -1

#1

기존 scoville배열을 heap 자료구조로 변경시킴 (O(N))

#2

맨 앞 + (앞에서 두번째 X 2) 를 heap queue에 다시 집어넣음

#3

만약 가장 작은 인자가 K보다 크다면 섞은 횟수 반환

아이디어

def solution(phone_book):
    for a in phone_book:
        for b in phone_book:
            if a.startswith(b) and a != b:
                return False
    return True

그냥 문제 보자마자 이 코드가 생각났다.
물론 정확성 테스트는 그냥 통과하는데 효율성 테스트에서 막힌다.

다른 방법을 생각해야 했다.

제한 사항을 확인하자.

문제 풀이 코드

def solution(phone_book):
    phone_book.sort()  # 1
    for a,b in zip(phone_book, phone_book[1:]): # 2
        if b.startswith(a):
            return False
    return True

#1

문자열 정렬로 접두어 번호가 비교되는 번호의 앞에 오도록 한다.

#2

바로 앞, 뒤만 체크하며 지나가 시간 복잡도가 줄어든다 O(N)

아이디어

1. 대기열의 첫번째가 나머지 보다 크다면 대기열에서 삭제 (인쇄)
   => 대기열의 첫번째 보다 나머지가 작지 않다면 대기열 맨 뒤로 보냄

2. 하나가 인쇄 될 때 마다 answer += 1

3. 만약 인쇄 된 문서의 순서(i)가 location과 일치한다면 answer return

4. 하나라도 첫번째 보다 크다면 대기열 맨 뒤로 보냄

   문제 풀이 코드

   def solution(priorities, location):
    answer = 0
    priorities = [(i,value) for i, value in enumerate(priorities)]  # 1
   
    while True:
        move_to_back = False
   
        for priority in priorities:  # 2
            if priorities[0][1] < priority[1]:
                move_to_back = True
                break
   
        if move_to_back:  # 3
            priorities.append(priorities.pop(0))
        else: # 4
            answer += 1
            if priorities[0][0] == location:
                return answer
            priorities.pop(0)

   1

   초기 location을 기억하기 위해 데이터 구조를 [index, value]로 변경

   2

   하나라도 맨 앞의 문서보다 중요도가 높다면 move_to_back = True

   3

   하나라도 맨 앞의 문서보다 중요도가 높다면 맨 앞의 문서를 맨 뒤로 이동시킴

   4

   맨 앞의 문서의 중요도가 가장 높으면 인쇄(대기열에서 삭제)하며 몇번째로 실행되었는지 알기 위해 answer에 +1을 해준다.
   또한, 내가 찾는 문서라면 answer을 반환한다

문제 풀이 코드

def solution(bridge_length, weight, truck_weights):
    # sum(다리를 건너는 트럭) + truck_weights[0] 가 weight이 안넘으면
    # 다리를 건너는 트럭.append(truck_weights[0])
    # 다리를 건너는 트럭[0][1] 을 시간이 지날때 마다 += 1 해줌
    # 다리를 건너는 트럭[0][1] 이 weight보다 크거나 같으면
    # 다리를 건너는 트럭[0] 을 다리를 지난 트럭으로 이동
    # 위 과정을 반복
    time = 0
    truck_weights = list(map(lambda x : [int(x),0],truck_weights))  #1
    current_bridge = []

    while True:
        time += 1
        current_bridge = list(map(lambda x : [x[0],x[1] + 1],current_bridge))  #2

        if len(current_bridge) > 0:
            if current_bridge[0][1] > bridge_length:  # 3
                del current_bridge[0]

        if len(truck_weights) > 0:
            if sum(map(lambda x : x[0] ,current_bridge)) + truck_weights[0][0] <= weight:  # 4
                truck = truck_weights.pop(0)
                current_bridge.append([truck[0],truck[1] + 1])

        if len(current_bridge) +  len(truck_weights) <= 0:
            break
    return time

#1

truck_weights 의 데이터 구조를 [무게, 현재 위치] 구조로 잡음
현재 위치 : 다리를 어느정도 건넜는가 (대기 상태이면 0)

#2

시간이 지날 때 마다 트럭이 다리를 1만큼 이동함 (다리 위에 올라가 있는 트럭만)

#3

트럭이 다리를 모두 건넜다면 제거해줌

#4

다리에 트럭을 더 올릴수 있다면 올림