구름을 채우다

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

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

문제 보기 이 문제는 브루트 포스 문제이다. 모든 경우의 수를 따져서 문제에 조건에 해당하는 최적의 결과를 찾아야 하는 게 목적이다. 모든 경우의 수를 따질 대상은 기준점이 되는 (x, y)와 d1, d2이다. (81~84번째 줄) 그리고 각 경우가 유효한 경우인지는 다음과 같이 문제에 명시되어 있으므로 이를 적용해서 필터링한다. (85번째 줄) 맨 처음 문제를 풀 때 다음과 같은 로직으로 문제를 해결하려고 했다. 5번 선거구의 경계를 구한다. 5번 선거구에 포함된 인구를 구한다. 1, 2, 3, 4번 선거구에 포함된 인구를 구한다. 인구가 가장 많은 선거구와 가장 적은 선거구의 차이가 최소가 되는 경우를 찾는다. 그런데 2번 과정에서 5번 선거구에 포함된 인구를 구할 방법이 떠오르지 않았다. 문제를 계..

문제 보기 이 문제는 DFS, BFS 문제이다. (DFS로는 안 풀어도 된다.) 연구소 내의 모든 바이러스 중에서 m개의 바이러스를 선택하는 과정을 DFS로 풀면 DFS 문제가 되겠지만, 나는 itertools 모듈의 combinations 함수를 사용하였다. 문제를 푼 로직은 다음과 같다. 입력으로부터 연구소 내의 빈 방의 개수와 바이러스의 위치를 저장한다. (9~17번째 줄) 모든 바이러스 중에서 m개의 바이러스를 선택하는 모든 경우의 수를 구한다. (20~21번째 줄) 2번에서 구한 m개의 바이러스를 큐에 삽입한다. (22~26번째 줄) 3번에서 큐에 삽입한 m개의 바이러스를 BFS를 통해 확산시킨다. (확산될 수 있는 경우의 수는 빈 방일 경우와 비활성 바이러스일 경우 확산될 수 있다. 빈 방의 ..

문제 보기 이 문제는 시뮬레이션 문제이다. 처음에 문제를 읽자마자 든 생각은 두 가지였다. collections 모듈의 Counter 자료구조를 사용해야겠다. 행과 열에 대한 연산이 있으므로, 열에 대한 연산은 A 행렬을 transpose 시켜야겠다. 이 두 가지 생각을 잘 구현하니 AC를 받았다. 문제를 푼 로직은 다음과 같다. 행렬 A를 초기 상태의 3 * 3 행렬로 초기화한다. (5~9번째 줄) R연산) A의 각 행마다 (숫자, 숫자가 나타난 횟수)의 리스트를 생성하고, 그 리스트에 대해 (숫자가 나타난 횟수, 숫자) 순으로 오름차순으로 정렬한다. (17번째 줄) R연산) 정렬된 0이 아닌 숫자들을 해당하는 A의 행에 새롭게 대입시킨다. (19~24번째 줄) R연산을 통해 바뀐 열의 최대 길이를 갱..

문제 보기 이 문제는 시뮬레이션 문제이다. 생각보다 쉬워보였는데 문제를 해결하는데 하루 2시간씩 총 3일이 걸렸다. (정말 바보같았다.) 처음에는 객체지향적으로 상어 클래스를 만들고 상어들의 배열을 만들어서 선형적인 시간복잡도로 문제를 해결하려고 했지만, 딱히 그럴 필요가 없을 것 같아서 그냥 2차원 배열의 각 원소들에게 상어의 정보를 할당하였다. 문제를 푼 로직은 다음과 같다. 2차원 배열에 상어에 대한 정보를 저장한다. (30~33번째 줄) 어부를 이동시킨다. (38~39번째 줄) 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다. (40~45번째 줄) 상어가 이동한다. (각 상어가 이동할 때마다 이동한 상어의 정보를 새로운 2차원 ..

문제 보기 이 문제는 시뮬레이션 문제이다. 처음에 문제를 훑고 나서 BFS 문제라고 생각했지만, 자세하게 문제를 읽어보니 나무 재테크와 비슷한 문제였다. 문제를 풀 때 주의할 점은 먼지를 확산시킬 때, 먼지를 확산시킬 칸들의 정보를 저장해두었다가, 모든 칸의 먼지의 양을 줄이고 나서 확산시켜야 한다. (이는 나무 재테크 문제에서처럼 똑같이 적용되는데, 각 칸을 순회할 때 먼지를 확산시켜 먼지의 양을 주변 칸에 더해버리면 다음 칸에서 확산시킬 먼지의 양에 영향을 끼친다.) 문제를 푼 로직은 다음과 같다. 공기청정기의 위치를 찾는다. (8~12번째 줄) 각 칸에서 미세먼지를 확산시킬 인접한 칸들을 찾고, 그만큼 현재 칸의 미세먼지의 양을 줄인다. 동시에 인접한 칸들의 위치를 큐에 저장한다. (18~32번째 ..

문제 보기 이 문제는 스택/큐 문제이다. 문제를 푼 로직은 다음과 같다. 모든 탑은 왼쪽으로 레이저 신호를 발사하므로, 각 탑에 대해서 왼쪽에 위치한 모든 탑에 대해 탐색을 진행한다. (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..