코딩관계론

아이디어 도출 방법 user_id가 최대 8개 임으로 조합을 구성해도 8 * 7 * 6이 최대로 나온다. 따라서 permutations을 사용해 나올 수 있는 모든 순열을 구성한다. 생성된 조합에서 해당 아이디가 banned_id에 대응되는지 확인한 후 중복을 확인한 후 list에 넣어주면 된다. 중복을 확인하기(순서가 상관없기 때문임) 위해서 순열에서 만든 후보 리스트를 set으로 변환하면 리스트가 정렬된 형식으로 나오게 된다. 예를 들면 (c, d, a) -> set(a, b, c)의 형식이 된다. 따라서 후보 값들의 중복을 제거할 수 있다. 최종 결과 from itertools import permutations def validate(user, ban): if len(user) != len(ban..

아이디어 도출 방법 나는 힌트를 k와 room_number의 숫자 차이로 알았다. k의 max는 10^12지만, room_number는 최대 20만이기 때문이다. 다음으로는 방의 점유 여부를 표시하기 위해서 해당 room_number을 key로 하고 value는 [점유여부, 다음 방 번호]를 가지는 dict 클래스를 생성했다. 해당하는 방 번호에 사용자가 있는지 확인하는 방법은 두 가지가 있다. 최대 O(K)만큼 돌면서 dict [room_number]을 호출하는 방식 union find 알고리즘을 사용해 O(1)에 확인하는 방법 이번 문제의 KEY는 union find short path 알고리즘을 아느냐가 제일 중요했다. Union Find short path 문제에서 초기 상태는 아래와 같이 구성된..

아이디어 도출 방법 해당하는 문제를 읽다가 보면 양방향 연결 리스트 느낌을 받을 수 있다. 왜냐하면 양방향 연결 리스트의 특징을 생각해보면 노드를 찾는 과정에서 o(n), 삭제 및 삽입 과정에서는 o(1)이 되도록 구현할 수 있기 때문이다. 또한 이번 문제에서는 특정 노드를 탐색하는 과정 없이, 지시에 따라서 현재 무슨 노드(파란색)에 위치하고 있는지만 체크하면 된다. 문제에서 원하는 복구 과정 역시 스택을 떠올리면 쉽게 해결할 수 있다, 스택은 선입 후출의 자료구조로 나중에 들어오는 것이 빨리 나간다. 한 가지 까다로운 점은 복구하는 과정이었다. 처음에는 삭제한 노드에서 가장 가까이 살아있는 노드를 찾는 방법을 사용해 삭제된 노드를 다시 삽입하려고 했지만 시간 초과가 발생했다. 하지만 다시 생각해보니 ..

아이디어 도출 방법 1. 항상 시간문제는 단위 통일하는 것이 핵심이다. 제일 작은 단위인 초로 통일하는 것을 추천합니다. 2. 초를 사용하면 시간순으로 정렬할 수 있으니 사람들이 도착하는 시간과 버스가 출발하는 시간을 비교해서 버스에 탑승 가능한 승객들을 deque에서 삭제해준다. #탑승객과 미잠 while time_table and bus_go < n: """마지막 버스전까지 모든 탑승객을 태운다. """ arrive_time = time_table.popleft() if arrive_time

아이디어 도출 방법 1. 주어진 입력에서 트리를 구성하는 방법은? 트리는 root node가 하나만 존재함으로 y축이 제일 높은 node가 root일 수 밖에 없다. nodeinfo.sort(key=lambda nodeinfo:(-nodeinfo[1], nodeinfo[0])) root 노드를 기준으로 x 값이 root보다 작으면 왼쪽, 크다면 오른쪽으로 분리해주면 된다. root_node = nodeinfo.pop(0) make_tree([node for node in node_list if node[0] root_node[0]]) 증명 y축으로 정렬하면 아래와 같은 그림이 형성되어..

아이디어 도출 방법 1. 먼저 효율성을 생각하지 않고 정확성 위주로 문제를 해결하려고 했다. 방송이 중단된 시간(k)만큼 돌면서 food_time[index]의 시간을 1초씩 감소시켜준다. idx = 0 for i in range(k): remove_food_time(food_time[idx]) idx += 1 2. 순차적으로 1초씩 줄이면 탈락하는 문제로 한번에 하나씩 삭제할 수 없을까 생각을 했다. 한 번에 FOOD_TIME [idx]의 시간을 0으로 만들 수 있다면 연산의 복잡도가 배열 길이에 따라 변한다. 그럼 어떤 Index가 먼저 0이 될까? 답은 간단하게 FOOD_TIME 중 최소 값이 먼저 사라진다 그럼 해당 Index를 0으로 만들 때 필요한 시간 계산은 어떻게 할 까? FOOD_TIME..

아이디어 도출 방법 1. 먼저 방향성, 최단 거리등의 키워드를 통해서 BFS 탐색이 떠올랐다. 하지만 이동 타입이 두 개라는 점이 생각을 어지럽게 했다. 언제는 cntrl 키를 눌러서 이동해야 하고, 언제는 한 칸만 이동하면 될까 -> 결국 4*4의 맵임으로 완전 탐색으로 진행하기로 했다. 2. 같은 카드가 두 개 있는데 무엇부터 시작해야 할까? (A:어파치 카드1, A1:어파치 카드2) 처음에는 그리디 하게 X- > A와 X -> A1 비용 중 싼 이동 가격으로 완전 탐색을 진행했다. 하지만 틀렸다. 그리디는 최적이 아니다. 따라서 모든 순서에서 시작해야 한다. X -> A -> A1로 가는 것과 X -> A1-> A로 가는 것은 종료 위치가 달라지기에 결과 값에 영향을 미칠 수 있다. 아이디어는 어렵..

이 풀이를 읽기 전 태상이의 훈련소 생활 문제를 푸시는 것을 추천드립니다(풀이:https://bjwan-career.tistory.com/4) 풀이 "재생 시간을 간단하게 구하는 방법이 없을까?" 10:43:20 ~ 12:22:57의 재생 시간을 원본 문자열 그대로 구하려면 상당히 힘들다. 한 가지 방법은 초로 통일하여 계산하면 간단하게 재생 시간을 구할 수 있다. 또한 다른 이점은 구간을 나눠서 재생 시간을 계산하지 않아도 된다. 해당 초에 몇 명이 봤는지 알 수 있다면 최종 재생시간을 구할 수 있다. '해당 초에 몇 명이 동영상을 시청하고 있다'를 빠르게 구할 수 있는 방법은 없을까?" 누적합을 사용하면 해당 초에 몇 명이 시청하는지 알 수 있다 동영상의 시작 부분과 종료 시간을 초로 변경한 후 해당..

링크 순위검색 풀이 "주어진 문자열을 어떤 방식으로 split할 것인가?" 완전탐색을 이용해 풀려고 했으니 특정 문자열을 내가 원하는 형식으로 만드는 것이 가장 중요하다. 먼저 주어진 query가 info 형식으로 변환될려면 " and" -> ""로 변경한 후 split(" ")을 하면 된다. "후보 쿼리는 어떤 방식으로 생성한 것인가?" 먼저 후보 쿼리를 직접 만들면 몇 개의 후보가 나올 수 있을지 생각을 해보자. 경우의 수는 두 가지 임으로 2 x 2 x 2 x 2 = 16개의 후보가 생성된다. 그럼 어떤 방식으로 생성할 것인가 조합함수를 이용해서 해당하는 인덱스를 '-' 문자열로 변경하면 모든 후보군을 생성할 수 있다. "정렬된 리스트에서 특정 값을 빠르게 찾는 방법" 이분 탐색을 수행하면 된다. ..

풀이 누적합을 이용해 skill을 O(n2)으로 줄여야 한다. 오랜 시간 동안 고민했던 것은 2차원 배열에서 누적 합을 어떻게 풀어야 할지 고민을 했다. 2차원 누적 합의 공식은 각 row를 먼저 다 누적해서 더한 후 col을 누적해서 더해주면 된다. 초기 배열 -2 0 2 0 0 0 map[2][3]) 2 0 -2 map[3][3] 누적합 배열 -2 -2 (psum[1][2]) 0 (psum[1][3]) -2 -2 (psum[2][2]) 0 ( psum[2][3]) 0 0 0 잘 생각하면 psum[2][3] 을 계산하면 map[2][3] + psum[1][3] + psum[2][2] -psum [1][2]의 경우는 변화량이 한번 제거된다.하지만 map[3][3]의 경우에는 변화량이 두 번 제거가 됨으로..