문제 링크 https://www.acmicpc.net/problem/1021 문제 정보 입력 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다. 출력 첫째 줄에 문제의 정답을 출력한다. 풀이 문제를 이해하는 것이 상당히 힘들었다. 양방향 순환 큐라는 것을 통해 덱을 이용해서 풀이할 수 있다는 것을 생각할 수 있다. 예시를 들어서 문제를 이해해보자. 만약 n = 10에서 4를 뽑아야 한다고 생각해보자. 덱 : 1 2 3 4 5 6 7 8 9 10 여기에서 4를 뽑을려면 왼쪽으로 이동해..

문제 링크 https://www.acmicpc.net/problem/10866 문제 정보 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. 출력 출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다. 풀이 STL Deque를 이해하면 쉽게 해결할 수 있다! 소스 코드 #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; deque DQ; while (n--) { stri..

문제 링크 https://www.acmicpc.net/problem/2164 문제 정보 입력 첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다. 출력 첫째 줄에 남게 되는 카드의 번호를 출력한다. 풀이 문제의 조건을 잘 읽어서 큐로 풀어야 한다는 것을 파악하면 쉽게 해결할 수 있다. 문제에서 1부터 n까지의 카드를 1이 제일 위로 오게 순서대로 밑으로 놓여져 있고, 제일 위에 있는 카드를 버린다는 것을 통해 먼저 들어간 것이 먼저 나오는 (FIFO) 구조를 떠올릴 수 있다. 소스 코드 #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; queue Q; for (int..

문제 링크 https://www.acmicpc.net/problem/10845 문제 정보 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. 출력 출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다. 풀이 STL Queue를 이해하면 쉽게 해결할 수 있다! 소스 코드 #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; queue Q; while (n--) { strin..

문제 링크 https://www.acmicpc.net/problem/2493 문제 정보 입력 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다. 출력 첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다. 풀이 이 문제도 어려운 문제여서 해결하는데 힘들었다. 현재 입력하는 탑의 높이가 기존 스택의 탑의 높이보다 크거나 작을때를 잘 생각해주면 된다. 만약 스택의 top이 현..

문제 링크 https://www.acmicpc.net/problem/1874 문제 정보 입력 첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다. 출력 입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다. 풀이 굉장히 해결하기 어려운 문제였다. 예제 1번을 보고 문제를 이해해보자. 8 4 3 6 8 7 5 2 1 을 입력했다고 하자. 따라서 처음에 4를 수열에 넣어야 한다. 그 과정은 아래와 같다. 1 2 3 4를 스택에 push 한다. 스택에서 4를 pop 해..

문제 링크 https://www.acmicpc.net/problem/10773 문제 정보 입력 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다. 정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다. 출력 재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다. 풀이 정수가 0인 경우에 가장 최근에 쓴 수를 지워야 하는 문제다. 스택은 LIFO 구조를 가지고 있으므로 스택을 이용하면 해결 할 수 있다는 것을 알 수 있다. 소스 코드 #i..

문제 링크 https://www.acmicpc.net/problem/10828 문제 정보 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. 출력 출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다. 풀이 STL Stack을 이해하면 쉽게 해결 할 수 있다! 소스 코드 #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; stack S; while (n--) { stri..