구름을 채우다

문제 보기 이 문제는 알고리즘 분류는 되어있지 않지만, 시뮬레이션 문제라고 생각한다. 갈수록 삼성의 SW 역량 테스트가 점점 어려워지는 게 느껴진다. 개인적으로 문제를 읽자마자 스택/큐의 개념이 떠올랐지만, 막상 파이썬으로 구현하니 스택/큐를 쓸 일이 없었다. 또한 C/C++의 포인터를 쓰고 싶었지만, 파이썬에는 포인터의 개념이 없기 때문에 해결법을 구상하는데 꽤나 오랜 시간이 걸렸다. 문제를 풀기 전, 중요한 변수가 3개 있다. board_info: 체스판의 색깔 정보를 담고있는 변수 board: 체스판 위의 체스말 정보를 담고 있는 변수 chess_pieces: 체스말 리스트 (각 체스 말의 행, 열과 방향을 담고 있다.) 이를 가지고 문제를 해결하였다. 문제를 푼 로직은 다음과 같다. 체스 말이 다..

문제 보기 이 문제는 스택/큐 문제이다. 주식이 시간이 지남에 따라 가격이 떨어지지 않은 시간이 얼마인지 구하는 문제이다. 현재 시간에서 미래에 가격이 떨어지는 시간까지 탐색을 해야하기 때문에 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..