목록백준/Stack, Queue (4)
mojo's Blog
문제 링크 => 1655번: 가운데를 말해요 (acmicpc.net) 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 최소힙, 최대힙을 이용하는 문제이다. 우선순위 큐를 이용하여 maxHeap, minHeap를 만들고 최소힙, 최대힙의 합한 갯수, 즉, 받아온 데이터의 갯수가 홀수일때와 짝수일때를 고려해줘야 한다. 데이터의 갯수(2n+1)가 홀수일 때 => 최대힙의 갯수 n+1 개, 최소힙의 갯수 n 개에 대하여 최대힙의 최댓값, 최소힙의 최솟값을 비교하여 더 작은 결과가 중간값이다. 데이터의..
문제 링크 => 11003번: 최솟값 찾기 (acmicpc.net) 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 우선순위 큐를 이용하는 문제이다. (덱을 활용해도 풀리는 문제) 앞과 뒷부분을 가르키도록 하는 변수 front, end를 선언하였다. 그리고 priority_queue pq 를 선언하여 첫번째에 배열값, 두번째에 인덱스값을 push하고 오름차순으로 정렬하도록 구현하였다. front ~ end 범위 내에 인덱스가 존재하는 경우 => 가장 작은 값이므로 출력한다. fr..
문제 링크 => 2504번: 괄호의 값 (acmicpc.net) 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net Stack을 활용한 문제이다. 스택 관련 문제중에 좀 어려운 문제여서 잘 안풀렸던 문제인거 같다. 이 문제를 해결하기 위해 최종값을 나타내기 위한 변수 result와 접근해가면서 괄호 안의 값들을 더하는 operation을 처리하기 위한 변수 tmp를 선언하였다. 그리고 '(', '[' 문자일때와 ')', ']' 문자일때의 operation을 다음과 같이 처리해주었다. (1) '(', '[' 문자..
문제 링크 => 5397번: 키로거 (acmicpc.net) 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L의 길이 ≤ 1,000,000) 강산이가 백스페이 www.acmicpc.net Stack을 활용한 문제이다. Stack, Queue 관련 문제를 해결하다 보면 런타임에러가 종종 일어나기 마련인데 이번에도 한번에 패스하지 못했다. 일단, '' 와 같은 화살표로 커서를 움직여서 문자를 받아올때 해당 커서의 위치에서 문자가 들어오는게 핵심이다. 또한 '-' 와 같은 문자가 들어오는 경우, 커서의 왼쪽에 위치하는 문자를 제거해준다. 이때 내가 놓쳤던 부분은 '-' 를 받아올 때,..