본문 바로가기

스택17

[백준 4889] 안정적인 문자열 www.acmicpc.net/problem/4889 4889번: 안정적인 문자열 입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우 www.acmicpc.net 스택을 사용한다. {는 무조건 푸쉬한다. }의 경우 이전에 {가 있으면 팝을 한다. => 이 경우 안정적인 문자열이다. 이전에 {가 없을 경우 문제가 발생한다. ('}'을 푸쉬하는 일은 없으므로 stack은 empty인 상태일 것이다.) 이 때 } -> {로 바꿔서 넣어주고 cnt++ 해준다. 문자열을 전부 돌고 난 후 스택에 남은 것은 제대로 처리되지 못한 { 일 것이다. 따라서 {을 처리하기 위해 스택 .. 2020. 11. 29.
[백준 5397] 키로거 www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L의 길이 ≤ 1,000,000) 강산이가 백스페이 www.acmicpc.net 1. 스택 2개 만들어서 풀기 #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; stack s1, s2; for (int i = 0; i > str; for (int j = 0.. 2020. 11. 29.
[백준 1406] 에디터 www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 연결리스트, 스택, 덱을 이용해서 풀 수 있다. 1. 스택 이용 두 개의 스택을 이용한다. 커서의 왼쪽에 있는 문자열을 s1 스택에 저장. 커서의 오른쪽에 있는 문자열은 s2스택에 저장한다. 명령어 L과 D의 경우 커서가 움직일 때마다 문자열을 옮긴다. #include #include #include using namespace std; stack s1, s2; int main(void) { ios_base::s.. 2020. 11. 29.
[leetcode 42] Trapping Rain Water Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. Example 1: Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Example 2: Input:.. 2020. 11. 10.

티스토리툴바