등반

https://www.acmicpc.net/problem/5957 5957번: Cleaning the Dishes Bessie and Canmuu are teaming up to wash the massive pile of N (1 > N; int num = 1; stack washed; stack finished; int C, D; while(cin >> C >> D){ if(C == 1){ while(D--){ washed.push(num++); } }else{ while(D--){ finished.push(washed.top()); washed.pop(); } } } while(!finished.empty()){ cout

https://www.acmicpc.net/problem/18241 18241번: 문자열 게임 첫 번째 줄에 성공한 명령의 개수를, 두 번째 줄에 프로그램을 실행한 후의 문자열 S를 출력한다. 프로그램 실행 후에 문자열이 비어있는 경우는 존재하지 않는다. 세 번째 줄에 프로그램을 실 www.acmicpc.net 3111문제와 크게 다르지않다. (3111 해설 : https://daan.tistory.com/19) 3111이 자동으로 방향을 바꾸며 필요한 문자열을 검색했다면, 해당 문제 18241은 명령(L or R)에 따라 방향을 바꿔 문자열을 검색하는 문제다. 명령의 수가 모자라 단어를 덜 찾은 경우가 있으므로, deque에 남은 문자(char)도 옮겨주는 과정이 필요하다. 위의 3111해설 페이지에서..

https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 두개의 스택을 이용해 스택의 top을 커서로 생각하고 구현하는 문제다. #include #define fio cin.tie(0)->sync_with_stdio(0) using namespace std; #include int main(){ fio; int TC; cin >> TC; for(int tc = 1; tc > S; for(int i=0; i

https://www.acmicpc.net/problem/3111 3111번: 검열 첫째 줄에 단어 A가, 둘째 줄에 텍스트 T가 주어진다. A와 T는 알파벳 소문자로만 이루어져 있고, A는 최대 25자, T는 최대 300,000자이다. www.acmicpc.net 문자열 T에서 처음 등장하는 문자열 A, 마지막으로 등장하는 A를 찾아 A가 등장하지 않을 때까지 삭제하는 문제다. 양방향으로 탐색을 해야 하기 때문에 스택이 두 개 필요하다. 시간 초과(틀린 풀이) / 맞는 풀이는 아래에 1. 스택 left, right를 준비하고, 문자열 T를 right에 모두 삽입한다. 2. left right) 2-2. A가 존재하지 않는다면, 과정을 중단한다. 3. 남은 문자열을 출력한다. 시간초과가 나오는 이유 : ..

https://www.acmicpc.net/problem/2841 2841번: 외계인의 기타 연주 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수 www.acmicpc.net 복수의 스택을 이용한 문제다. 특정 스택의 top과 원하는 프렛을 비교하면 된다. #include #define fio cin.tie(0)->sync_with_stdio(0) using namespace std; #include #include #include stack stack_[7];//1번 줄 to 6번줄 int main(){ fio; int N, P..

https://www.acmicpc.net/problem/5964 5964번: Best Parenthesis Recently, the cows have been competing with strings of balanced parentheses and comparing them with each other to see who has the best one. Such strings are scored as follows (all strings are balanced): the string "()" has score 1; if "A" has score s(A) th www.acmicpc.net 이전의 2504 문제와 크게 다르지않은 문제다. 여기선 올바른 문자인지 확인하지않아도 되며, 계산만 하면 된다. #..

https://www.acmicpc.net/problem/4889 4889번: 안정적인 문자열 입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우 www.acmicpc.net 스택을 이용해서 올바른 문자열인지 확인할 수 있는지에 관한 문제다. '{'는 그대로 스택에 넣어주면 되고, '}'의 경우를 생각해야한다. 1) 스택이 비어있는 경우엔 '{'으로 바꿔넣어야한다. 2) '{'가 스택의 top에 있는 경우(스택의 top에 '}'는 있을 수 없다), pop해준다. #include #define fio cin.tie(0)->sync_with_stdio(0) using ..

https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 1. 올바른 괄호인지 확인하기 2. 스택을 이용해서 괄호 계산하기 두가지를 해결하는 문제다. 한 번에 1, 2를 해결할 수 있지만, 본인은 역할을 구분하였다. #include #define fio cin.tie(0)->sync_with_stdio(0) using namespace std; #include #include bool is_stack_right(const string& S){ stac..

https://www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net K(Q)와 같이 압축된 문자열이 주어질 때(K는 한자리 정수이고, Q는 0자리 이상의 문자열), 압축을 푼 문자열의 길이를 구하는 문제다. 스택을 이용해서 괄호 안의 값(Q)를 계산하고, K번 반복시키는 방법으로 문제를 풀어봤다. ※메모리 초과(틀린 코드) #include #define fio cin.tie(0)->sync_with_stdio(0) using namespace std; #in..

https://www.acmicpc.net/problem/12789 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net 스택을 하나 이용해서 주어진 N개의 수들을 순서대로(오름차순) 만들 수 있는지를 판단하는 문제다. 줄서있는 사람의 차례인 경우 통과시키고 차례가 아닌 경우 스택에 집어넣는다. 스택에 쌓다보면, 현재 차례인 사람을 1)줄 서있는사람, 2)스택에 쌓인사람 두 경우 모두 비교해줘야한다. 둘 중 한명의 차례라면 그대로 내보내면 되고, 둘 다 아닌 경우엔 일단 스택에 넣어주는 수밖에 없다. #includ..