문제 24511번: queuestack 첫째 줄에 queuestack을 구성하는 자료구조의 개수 $N$이 주어진다. ($1 \leq N \leq 100\,000$) 둘째 줄에 길이 $N$의 수열 $A$가 주어진다. $i$번 자료구조가 큐라면 $A_i = 0$, 스택이라면 $A_i = 1$이다. 셋째 줄 www.acmicpc.net 풀이 처음에는 리스트를 이용해 큐스택을 직접 구현하여 해결하려 했지만, 당연하게도 시간 초과가 발생했다. 모든 요소에서 계산을 처리하면 시간복잡도가 O(NxM)이 되는데, 문제에서 주어진 범위에 따라 N = 10만, M이 10만일 때는 100억의 계산이 필요하기 때문이다. 대신 큐와 스택의 특성을 이용해 계산하는 방법을 생각해 보아야한다. 먼저 스택은 현재 삽입된 원소가 다시 ..

문제 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net 풀이 대기열의 왼쪽에 있는 공간을 스택으로 생각하여 풀이하면 된다. 스택은 선입후출 구조이므로 왼쪽 공간에 먼저 들어간 번호는 나중에 나온다. 현재 도시락을 받을 번호를 나타내는 변수 cur을 1로 초기화하고 선언한다. 입력받은 대기열을 앞에서부터 순회하면서 cur과 같은 번호를 만나면 도시락을 받은 것으로 처리하고, cur을 1 증가시켜서 다음으로 받을 사람을 나타낸다. 만약 cur과 다른 번호를 만난 경우에는 스택에 추가한다. 이 때, 현재 스택에서 가..

문제 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X www.acmicpc.net 풀이 스택을 활용해 올바른 괄호열인지 확인하여 값의 계산까지 구현하는 문제이다. 계산은 전체를 더한 결과값 sum과 중간 단계를 나타내는 tmp로 두 개의 변수를 사용한다. 여는 괄호인 경우 괄호에 해당하는 값을 스택에 넣어주고 tmp에 곱해준다. 닫는 괄호인 경우에 스택이 비어있거나 바로 전 괄호가 짝이 맞지 않다면 잘못된 괄호열이으로 결과값을 0으로 출력해준다. 잘못된 괄호열이 아니라면 바로 전 괄호가 짝이 맞다면 tmp를 sum에 더해주고, 스택..

문제 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 풀이 주여진 수열을 만들기 위해 스택의 push와 pop 과정을 통해 구현하는 문제이다. 먼저 예제 입력 1을 예시로 수열을 만드는 방법을 살펴보자. 4를 수열에 배치하기 위해서 스택에 1, 2, 3, 4를 넣어 {1, 2, 3, 4}인 상태를 만들고 4를 빼주면 된다. 수열은 [4]이 되고 스택은 {1, 2, 3}인 상태가 된다. 다음 3을 배치하기 위해 스택에서 3을 빼준..

문제 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 풀이 Stack을 이용해 풀면 된다. 0을 입력받았을 때 pop()을 호출하고 아닐 때는 push()를 호출해준다. 입력이 끝나면 stack이 비워질 때 까지 pop()을 호출하며 sum 변수에 더해준다. 코드 import java.util.* fun main() { val br = System.`in`.bufferedReader() val bw = System.out.bufferedWriter() val case = br...