목록2024/09/11 (3)
미소를뿌리는감자의 코딩
1. 접근 방법https://www.acmicpc.net/problem/1655 2. 문제 풀이최소 힙과 최대 힙 2개를 이용해서 문제를 풀었다. ( 조금 힌트를 얻긴 했다.. *^^* ) 블록이 홀수 개 일 땐, 최소 힙에 블록을 넣고, 최솟값을 pop 해 최대 힙에 옮긴다. 이후, 최대 힙에서 peek를 출력하여 준다.블록이 짝수 개 일 땐, 최소 힙에 블록을 넣고, 최솟값을 pop해 최대 힙에 옮긴다. 이후 최대 힙에서 최대를 pop하여, 최소 힙에 넣어준다.이후, 최대힙에서 peek를 출력하여 준다. 아래 그림으로 더 자세히 설명해 보겠다. 3. 코드import sysimport heapqmin_heap = []max_heap = []def find_median(i, n): global mi..
1. 문제https://www.acmicpc.net/problem/3190 2. 접근 방법이번 문제는 tail이 따라가야 할 방향과 회전 방향을 어떻게 처리하느냐가 중요한 것 같다.이들을 queue로 구현하여, 구현 가능하도록 하였다. 방향 회전은 아래와 같이 구성하였다. 위와 같이 방향을 처리해 주었다. head가 새로운 곳으로 이동하게 되면, 이를 tail_location 이라는 deque 에 뒤로 넣어주었다.또한 deque.popleft()를 통해서 tail이 따라가야할 위치를 알아내 주었다. 이 외, 다른 부분은 직관적으로 구현하였다. 3. 코드from collections import dequehead_location = [0, 0]tail_location = deque()tail_locatio..
1. 문제https://www.acmicpc.net/problem/2504 2. 접근 방법이번 문제는 올바른 괄호 찾기 + 분할 정복에 대한 적용을 필요로 하는 문제 같았다.2개의 stack을 사용하여 이번 문제를 해결하였다. 괄호들이 처음 포함 된 stack을 b_stack 하나씩, pop하여 저장해 줄 stack을 a_stack이라고 선언하였다.만약, b_stack에서 pop 된 녀석이 ) 또는 ] 라면, a_stack에 append 해주었다.그 외 ( 또는 [ 을 만나게 된다면, 3개의 경우로 나누어서 판단하였다.a_stack[-1] 이 짝이 맞게 ) 을 반환하는 경우a_stack[-1] 이 짝이 만제 ] 을 반환하는 경우a_stack[-1] 이 숫자를 반환하는 경우1번의 경우엔, )을 pop 하여..