구름을 채우다

문제 보기 이 문제는 힙 문제이다. 힙 자료구조를 사용해서 우선순위 큐를 구현하는 것이 문제의 의도이다. 문제를 푼 로직은 다음과 같다. 주어진 스코빌 리스트를 힙으로 변경한다. (7~8번째 줄) 문제에서 주어진 방식대로 음식 2개를 섞어 새로운 음식을 만들고, 이 때의 스코빌 지수를 추가한다. (11~15번째 줄) 모든 음식의 스코빌 지수가 K보다 높아야하므로, 힙의 루트가 K보다 작을 동안(= 힙의 최소값이 K보다 커지면 모든 음식의 스코빌 지수가 K보다 크다) 반복한다. (9~10번째 줄) 더이상 섞을 음식이 없고, 스코빌 지수가 K보다 낮다면 -1을 반환한다. (17~18번째 줄) import heapq def solution(scoville, K): answer = 0 # make scovill..

문제 보기 이 문제는 스택/큐 문제이다. 주식이 시간이 지남에 따라 가격이 떨어지지 않은 시간이 얼마인지 구하는 문제이다. 현재 시간에서 미래에 가격이 떨어지는 시간까지 탐색을 해야하기 때문에 O(n^2)이 나올거라고 생각했다. 문제를 푼 로직은 다음과 같다. 각 시간에서의 주식 가격에 대해서 (5~6번째 줄) 주식 가격이 떨어지지 않는 시간을 구한다. (8~15번째 줄) 각 시점에서의 주식 가격이 떨어지지 않는 시간을 업데이트한다. (17번째 줄) 여기서 눈여겨 볼 점은, 11~15번째 줄이다. 먼저 시간부터 센 다음, 만약 주식 가격이 떨어지면 break를 통해 반복문을 벗어난다. 이는 예제 입력을 보면 알 수 있다. 주식 가격이 상승을 하던 하락을 하던 일단 1초는 지나가기 때문에 시간을 먼저 세는..

문제 보기 이 문제는 스택/큐 문제이다. 문제를 해결하는데 스택이 사용되긴 했지만, 오히려 개념은 DP에 가까운 느낌이다. 문자열을 하나씩 읽을 때마다, 레이저를 만나게 되면 잘린 막대기가 몇 개인지 판단하였다. 문제를 푼 로직은 다음과 같다. 레이저는 "()"로 구분되므로, 더 쉬운 이해를 위해서 다른 문자 하나로 치환한다. (나의 경우 '.'로 치환했다.) 문자열을 읽으면서 '('를 만나면 막대기를 현재에서 한 개 더 올린다는 뜻이므로, '('를 만날 때마다 스택에 추가하고, 쇠막대기의 개수를 한 개 더한다. (7~9번째 줄) 문자열을 읽으면서 ')'를 만나면 젤 위의 막대기가 끝이 났다는 뜻이다. 그러므로 스택에 추가한 '('를 한 개 뺀다. (10~11번째 줄) '.'를 만나면 (=레이저를 만나면..

문제 보기 이 문제는 스택/큐 문제이다. 쉬운 문제인 줄 알았는데, 자꾸 한 가지 생각에 꽂히다 보니 문제를 푸는데 시간이 걸렸다. 문제를 푼 로직은 다음과 같다. 다리 위를 지나고 있는 트럭에 대해, 다리 위에서 소요한 시간을 센다. (나의 경우 다리 길이에서부터 1씩 감소시켰다.) (12~14번째 줄) 만약 다리 위를 지나고 있는 트럭 중 가장 첫 번째 트럭이 다리의 길이만큼 시간을 소모했으면, 다리를 통과시킨다. (16~19번째줄) 만약 대기하고 있는 트럭이 있고, 다리를 지나갈 공간이 있으면 트럭을 출발시킨다. (21~27번째 줄) 소요된 시간을 센다. (28번째 줄) 다리 위를 지나고 있는 트럭부터 계산을 하고 대기하고 있는 트럭을 신경써야 했지만, 나는 대기하고 있는 트럭부터 신경을 써서 출발..

문제 보기 이 문제는 스택/큐 문제이다. 문제를 푼 로직은 다음과 같다. 모든 탑은 왼쪽으로 레이저 신호를 발사하므로, 각 탑에 대해서 왼쪽에 위치한 모든 탑에 대해 탐색을 진행한다. (4~7번째 줄) 만약 현재 탑에서 왼쪽에 위치한 탑들 중에 높이가 높은 탑이 있다면, 그 탑의 위치를 기록한다. (8~11번째 줄) 만약 왼쪽에 위치한 탑들 중에 높이가 높은 탑이 없다면 0을 기록한다. (12~14번째 줄) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 def solution(heights): answer = [] for i, height in enumerate(heights): found = False # for all front towers from the nearest tow..

문제 보기 이 문제는 스택/큐 문제이다. 문제를 읽다보면 처음에 중요도가 더 높은 문서를 인쇄해야한다고 해서, 우선순위 큐를 생각했었지만, 입력값의 범위가 100보다 작다고 명시되어 있어서 그냥 n^2의 복잡도로 문제를 풀었다. 문제를 푼 로직은 다음과 같다. 빠른 삽입과 제거를 위해 주어진 대기목록의 list형 변수를 deque로 변환한다. (7~10번째 줄) 대기 목록의 가장 앞에 있는 문서를 꺼내고, 대기 목록 중에 우선순위가 더 높은 문서가 있는지 확인한다. (13~21번째 줄) 만약 대기 목록 중, 우선순위가 더 높은 문서가 있다면 대기 목록의 맨 뒤에 현재 문서를 추가한다. (17~21번째 줄) 만약 문서가 추가되었다면, 1번으로 되돌아간다. (23~25번째 줄) 만약 문서가 출력되었다면, 횟..

문제 보기 이 문제는 스택/큐 문제이다. (난 덱(deque)을 사용해서 문제를 풀었다..) 문제를 푼 로직은 다음과 같다. progress와 speed 리스트를 deque 자료형으로 변환한다. (7~8번째 줄) 각 진행속도만큼 progress를 증가시킨다. (12~14번째 줄) 만약 맨 첫 번째 작업이 끝이 나면, 연속된 작업 중 완료된 작업들의 개수를 구한다. (16~22번째 줄) 만약 배포된 작업이 있으면 정답 배열에 추가한다. (24~26번째 줄) 작업이 남아있는 동안 2~4번을 반복해서 실행한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 from collections import deque def sol..

문제 보기 이 문제는 해쉬 문제이다. 문제를 해결하기 위해 2가지의 dictionary 자료형 변수가 필요하다. 첫 번째는 각 장르별 재생 횟수를 위해, 두 번째는 각 노래별 재생 횟수를 위해서이다. 문제를 푼 로직은 다음과 같다. 각 장르별 총 재생 횟수를 구한다. (10~13번째 줄) 모든 노래에 대해 장르별로 해쉬 맵을 구성한다. (14~17번째 줄) 총 재생 횟수가 많은 순서대로 장르의 순서를 구한다. (19~20번째 줄) 재생 횟수가 많은 순서대로 각 장르에 속한 노래들의 순서를 구한다. (21~23번째 줄) 3번에서 구한 장르의 순서대로, 그 장르에 속한 노래들을 4번에서 구한 순서에서 첫 번째와 두 번째 노래를 베스트 앨범에 추가한다. (노래가 1곡이면 1곡만 추가한다.) (25~32번째 줄..

문제 보기 이 문제는 해쉬 문제이다. (그런데 정작 해쉬는 잘 안 쓰인 것 같다..) 처음엔 간단해 보였는데 경우의 수를 잘 못해서 한참 헤맸다.. 문제를 푼 로직은 다음과 같다. 먼저 옷의 각 종류에 대해서 옷의 개수를 센다. (옷의 이름은 중요하지 않다. 개수만 알면 된다.) (7~11번째 줄) 만약 옷의 종류가 한 가지라면 옷의 개수만큼 반환한다. (스파이는 최소 1개 이상의 옷을 입어야하기 때문) (13~16번째 줄) 만약 옷의 종류가 한 가지 이상이라면, (종류 1의 개수 + 1) * (종류 2의 개수 + 1) * ... - 1을 반환한다. (옷의 종류에서 1을 더하는 이유는 해당 종류의 옷을 안 입을 수 있기 때문이고, 마지막에 - 1을 하는 이유는 스파이는 최소 1개 이상의 옷을 입어야 하므..

문제 보기 이 문제는 해쉬 문제이다. 그런데 접두사라는 특징이 보여서 지금까지 한 번도 해본 적 없는 트라이로 풀어보았다. 문제를 푼 로직은 다음과 같다. 전화번호부에 있는 전화번호들을 정렬한다. (26번째 줄) 정렬이 끝나면 길이가 짧은 문자열부터 차례대로 나열되는데, 이 때 트라이에 삽입하면서 확장시켜나간다. 트라이에 삽입할 때, 문자열의 마지막 노드에 end라는 불리언 변수를 True로 설정한다. (21번째 줄) 만약 어떤 문자열을 트라이에 삽입할 때, end가 True인 노드를 만난다면 이전에 같은 문자열이 삽입되었다는 뜻이므로 False를 반환한다. (18~20번째, 29~30번째 줄) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2..