코딩관계론

아이디어 도출 방법 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