손가락놀이터

문제후기

1. 문제에서 n이 1이상 100이하인 것과 경기 결과가 1개 이상 4,500개 이하인 것을 보고 완전탐색이 가능하다고 판단했습니다.
2. 입출력 예시에서처럼 5번 선수는 다른 선수와 경기를 하지 않아도 2번 선수를 통해서 결과를 유추할 수 있다는 것을 확인할 수 있습니다.
3. A선수가 B선수를 이기고 B 선수가 C선수를 이긴다면 A가 C를 이긴다는 조건이 성립합니다.( A>B이고 B > C이면 A>C)
4. 유추를 통해 이길 수 있는 선수와 지는 선수를 set 집합을 통해 저장 후 결과를 추출했습니다.

문제링크

def solution(n, results):
    # 선수 경기 결과 hash로 저장
    matrix = dict()

    # 이기는 사람 집합과 지는 사람 집합
    for i in range(1, n + 1):
        matrix[i] = [set(), set()]

    # 경기 결과 입력
    for i in results:
        matrix[i[0]][0].add(i[1])
        matrix[i[1]][1].add(i[0])

    # 만약 A > B 이고 B > C 인경우 A>C인 관계(>는 이긴다)
    # 모든 선수를 통해 경기하지 않아도 결과를 아는 경우 저장.
    for num, match in matrix.items():
        if match[0] and match[1]:
            for win in match[0]:
                matrix[win][1].update(match[1])
            for lose in match[1]:
                matrix[lose][0].update(match[0])

    # 만약 이기는 경우, 지는 경우, 자기 자신의 합이 모든 선수의 수인 경우 +1
    answer = 0
    for num, match in matrix.items():
        if len(match[0]) + len(match[1]) + 1 == n:
            answer += 1
    return answer
   

문제 후기

1. (만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.) 해당 제한사항을 가능한 이라는 것을 인지하지 못하고 단순하게 알파벳이 먼저 오면 해결하려 해서 틀리게 됐습니다.
2. DFS와 알파벳 순서 2가지를 생각해보며 다시 알고리즘을 짰고 스택을 활용하여 문제를 풀었습니다.
3. 해당 알고리즘의 경우 도착 or 항공편이 없는 경우 먼저 answer에 들어가게 했으며 마지막에 reverse를 통해 결과값을 제출했습니다.

출처 : programmers.co.kr/learn/courses/30/lessons/43164?language=python3

def solution(tickets):

    node_dict = {}      # 노드 hash화
    # 출발지를 key로 도착지를 value로 지정.
    for city in tickets:
        # dict.get(a,b) = dict에서 key가 a인 것을 찾고 없으면 b값을 넣겠다.
        node_dict[city[0]] = node_dict.get(city[0], []) + [city[1]]

    # 알파벳 역순으로 정렬
    for city in node_dict:
        node_dict[city] = sorted(node_dict[city], reverse=True)


    stack = ["ICN"]
    answer = []

    # 스택에 값이 있는동안 계속 반복
    while stack:
        now_city = stack[-1]
        # 만약 해당 도시 출발 항공표가 없을 때 answer에 추가.
        if now_city not in node_dict or node_dict[now_city] == []:
            answer.append(stack.pop())
        else:
            # 해당 도시 출발 항공표가 있을 때 다음 도시 pop해서 스택에 추가
            stack.append(node_dict[now_city].pop())
    # 역순이므로 다시 정렬
    answer.reverse()
    return answer

문제후기

1. operation에 들어있는 문자열을 판별하여 최대값과 최솟값을 찾아서 제외하고 결과적으로 최대값과 최솟값을 찾는 문제로 해석했습니다.
2. 파이썬에서 제공하는 heapq 모듈은 최소 힙을 기준으로 하므로 최대힙을 어떻게 처리할까 생각하다가 tuple로 최대힙을 만들어서 했습니다.
3. tuple로 최대힙을 만든경우 추출된 값을 다른 힙에서도 제외해야해서 시간이 오래걸린다는 것을 알고 nlargest 함수를 활용했습니다.

출처 : programmers.co.kr/learn/courses/30/lessons/42628?language=python3

import heapq


def solution(operations):
    min_heap = []       # 힙 입력 배열
    for i in operations:
        # 숫자 입력인 경우
        if i[0] == "I":
            num = int(i.split()[1])
            # 숫자를 heap에 push
            heapq.heappush(min_heap, num)
        # 최댓값 추출인 경우
        elif i == "D 1":
            # 배열 안에 값이 없으면 패쓰
            if min_heap:
                # nlargest로 가장 최댓값 추출
                min_heap.remove(heapq.nlargest(1, min_heap)[0])
        # 최솟값 추출인 경우
        elif i == "D -1":
            # 배열 안에 값이 없으면 패쓰
            if min_heap:
                # pop으로 최솟값 추출
                heapq.heappop(min_heap)
    # 배열에 값이 있는 경우 최댓값, 최솟값 추출
    # 없는 경우 [0,0]추출
    if min_heap:
        return heapq.nlargest(1, min_heap) + [heapq.heappop(min_heap)]
    return [0, 0]

문제 후기

1. 제한사항에서 n이 1,000,000,000을 확인하고 O(logN)을 확인했습니다.
2. 문제를 풀면서 어느 부분에서 이분탐색을 해야하는지 헤매다 최소공배수를 기준으로 잡고 적절한 위치를 이분탐색으로 찾으려했습니다. 해당 알고리즘의 경우 테스트케이스를 만족했지만 다른 케이스에서 전부 시간초과가 발생했습니다. 시간초과가 발생한 요인으로는 최소공배수를 찾고 배열을 만드는 과정에서 발생한다고 생각했습니다.
3. 제한시간을 초과하여 다른분의 블로그(wwlee94.github.io/category/algorithm/binary-search/immigration/)를 참조했습니다.
4. 최대값을 가장 오래걸리는 심사관이 모든 n명을 심사했을 경우로 하고 최소 시간을 탐색하며 진행했습니다.

문제 설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

입출력 예

입출력 예 설명

가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

def solution(n, times):
    answer = 0      # 정답값
    start = 1       # 최소 시작
    end = n * max(times)    # 최대 시작
    
    # 이분탐색 시작
    while start <= end:
        middle = (start + end) // 2
        
        # 해당 시간 동안 몇 명을 심사할 수 있는지
        count = 0
        for time in times:
            count += middle // time
        
        # n명 이상인 경우 end값 조정
        if count >= n:
            answer = middle
            end = middle - 1
        # n명 미만인 경우 start값 조정
        else:
            start = middle + 1
    return answer

문제후기

1. 처음에는 다익스트라 알고리즘을 활용해서 해결하려 했으나 다익스트라로는 답이 나오지 않아 알고리즘 변경했습니다.

2. 찾아보다가 크루스칼이라는 알고리즘(최소비용으로 모든 노드를 연결시키는 알고리즘)이 적절한 알고리즘이라는 것을 찾았습니다.

3. union-find를 하는 방법으로 배열을 사용하는 방법을 생각해서 해결했습니다.

4. set으로도 해결가능할 것 같아 set으로도 해봤습니다.

문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

def solution(n, costs):
    answer = 0
    # 간선의 크기로 정렬
    costs.sort(key=lambda x: x[2])
    # union-find를 set으로 설정
    routes = set([costs[0][0]])

    # 모든 노드를 연결한 경우 멈춤.
    while len(routes) != n:

        for i, cost in enumerate(costs):
            # 만약 시작노드와 마지막 노드가 연결되면 싸이클이 발생하는 경우
            if cost[0] in routes and cost[1] in routes:
                continue
            # 싸이클이 발생하지 않는 경우
            if cost[0] in routes or cost[1] in routes:
                # set 새로고침
                routes.update([cost[0], cost[1]])
                answer += cost[2]
                # 반영된 간선을 시각적으로 보기 편하게 하기위해 삽입(없어도 됨)
                costs[i] = [-1, -1, -1]
                break
    return answer

def solution(n, costs):
    answer = 0
    # 간선의 크기로 정렬
    costs.sort(key=lambda x: x[2])
    # union-find를 배열로 설정
    chk_node = [i for i in range(n)]
    count = 0 # 크루스칼을 만족하는 경우 간선의 갯수는 노드 -1
    for n1, n2, cost in costs:
        # 만약 시작노드와 마지막 노드가 연결되면 싸이클이 발생하는 경우
        if chk_node[n1] != chk_node[n2]:
            # 끝 노드 union-find 실행
            temp = chk_node[n2]
            for i in range(n):
                if chk_node[i] == temp:
                    chk_node[i] = chk_node[n1]
            
            answer += cost
            count += 1
        if count == n - 1:
            break
    return answer

문제 후기

1. 문제를 보고 바로 든 생각은 DP(Dynamic Programming)을 활용해야겠다는 것입니다.

2. 위의 줄의 같은 idx or idx-1 중에서 높은 수를 더해서 더해주면서 내려오고 맨 마지막 줄에서 가장 큰 수를 구하는 방식으로 해결했습니다.

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

def solution(triangle):
    # DP로 2번째 줄부터 시작
    for row in range(1, len(triangle)):
        for col in range(len(triangle[row])):
            # 비교할 2가지 값.
            calculation1, calculation2 = triangle[row][col], triangle[row][col]
            # idx -1 위치에서 내려온 것.
            if 0 <= col - 1 < len(triangle[row - 1]):
                calculation1 += triangle[row - 1][col - 1]
            # idx 위치에서 내려온 것.
            if 0 <= col < len(triangle[row - 1]):
                calculation2 += triangle[row - 1][col]
            # 둘 중 큰 값 선택
            triangle[row][col] = max(calculation1, calculation2)
    # 마지막 줄에서 가장 큰 값 선택
    return max(triangle[-1])

문제후기

1. 처음 문제를 보고 단어가 순차적으로 찾아간다는 것과 최소거리를 구하는 것을 보고 word를 노드, 변환가능한 단어관계를 간선으로 생각했습니다.

2. begin을 포함한 words를 노드와 간선으로 표시한 이후 BFS를 이용해서 답을 구했습니다. DFS보다 BFS가 더 효율적이라 생각했습니다.

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 cog는 words 안에 없기 때문에 변환할 수 없습니다.

from _collections import deque


def solution(begin, target, words):

    answer = 0      # 결과값
    length = len(begin)     # 단어 길이
    word_node = {}          # 변환 가능한 단어를 노드로 변환
    words.insert(0, begin)  # begin값 words에 추가

    # words 값들을 노드변환
    for idx in range(len(words)):
        word_node[idx] = []

    # 변환가능한 단어를 간선으로 변환
    for idx in range(len(words)):
        for idx2 in range(idx + 1, len(words)):
            chk_word = 0
            for c in range(length):
                if words[idx][c] == words[idx2][c]:
                    chk_word += 1
            # 만약 다른 글자가 1개인 경우 변환가능한 단어
            if chk_word == length - 1:
                word_node[idx].append(idx2)
                word_node[idx2].append(idx)

    wait_visit = []     # 다음 거리의 노드
    visit = deque([0])  # 큐에 넣어서 순차적으로 노드 방문
    visited = [0] * len(words)      # 노드 방문 여부 체크
    visited[0] = 1      # begin값부터 시작
    

    while True:
        # 큐에 값이 있을때까지
        while visit:
            # 방문 노드
            now_word = visit.pop()
            
            # word_node에서 간선으로 방문가능한지 확인
            for idx in word_node[now_word]:

                # 이미 방문한 노드인지 확인
                if visited[idx] == 1:
                    continue
                # 만약 해당 노드가 target값이면 종료
                if words[idx] == target:
                    return answer + 1
                # 다음 큐 리스트에 추가
                wait_visit.append(idx)
                # 방문체크
                visited[idx] = 1
        # 노드간의 거리 
        answer += 1
        
        # 만약 다음 방문할 노드가 없으면 종료
        if wait_visit:
            visit = deque(wait_visit)
            wait_visit = []
        else:
            return 0

문제 후기

1. 먼저 그래프로 구성되어 있다는 것에서 DFS와 BFS 둘 중 하나로 해결겠다는 생각을 했고 문제를 읽고 가장 먼 노드의 갯수를 세는 것으로 BFS로 풀 것을 정했다.

2. 단순히 방문한 노드를 체크하는 것으로 하니 시간초과가 발생했다.

3. 배열 상태에 있는 것을 dictionary를 통해 hash형태로 변환하여 모든 vertext를 확인하지 않고 해당 노드의 간선만 확인하여 진행했더니 문제가 해결됐다.

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

from _collections import deque

def solution(n, edge):
    answer = 1      # 정답값
    now_visit = deque([])   # 방문 노드 큐
    next_visit = []         # 다음 방문 노드
    visited = [0] * (n + 1) # 노드 방문 여부 확인
    visited[1] = 1

    # dictionary를 통해 hash로 빠르게 간선을 찾음.
    node_dic = {}
    for i in range(1,n+1):
        node_dic[i] = []

    for i in edge:
        node_dic[i[0]].append(i[1])
        node_dic[i[1]].append(i[0])

    # 1번 노드부터 시작
    for i in node_dic[1]:
        now_visit.append(i)
        visited[i] = 1
        node_dic[1] = []


    while True:
        # 방문할 노드가 있을때까지 반복
        while now_visit:
            node = now_visit.pop()

            # 해당 노드의 hash값을 통해 다음 방문 노드 확인
            for i in node_dic[node]:
                # 노드 방문 여부 확인
                if visited[i] == 1:
                    continue
                visited[i] = 1
                next_visit.append(i)

        # 다음 방문할 노드가 있으면 계속 진행
        if next_visit:
            now_visit = deque(next_visit)
            answer = len(next_visit)
            next_visit = []
        else:
            # 없는 경우 결과 리턴
            return answer