스택으로 응용문제 풀기
*이 글은 2022년 1월~2월 노션으로 진행한 스터디를 옮긴 글입니다.
220117 스택 응용 내용정리
4차시 정리한 내용 바탕으로 아래 문제에 적용
응용문제는 후위표기식 부분만 코드짜서 풀었어요^...^
- 괄호 검사 () [] {} 조건
-
여는 괄호와 닫는 괄호의 갯수가 같아야 함
-
같은 괄호에서 왼쪽 괄호가 오른쪽 괄호보다 먼저 나와야 함
-
괄호 별로 포함 관계만 있음
알고리즘
-
괄호 차례대로 조사하며 왼쪽 괄호 만나면 스택에 삽입, 오른쪽 괄호 만나면 스택에서 팝한 자료와 짝이 맞는지 검사함.
-
이 때 스택이 비었거나 짝이 맞지 않으면 false 리턴.
-
마지막 괄호까지 조사한 후에도 스택에 괄호가 남아 있으면 false 반환, 아니면 true 반환.
-
- 문자열 역순 만들기
- push/pop 이용해서 간단히 구현
- 표기법 변환(중위표기법→후위표기법) 조건은 사칙연산 조건과 같음. 이런 작업도 스택이 쓰임
-
ab+5→ab5+
-
(1+2)7→12+7
이 응용 문제는 백준에 관련 문제가 있길래 문제 새로 풀어보면서 정리했어요 (1918번)
/* 백준 1918번 오늘 해야되는 것: -switch문 정리하기 -이 코드의 스택이 어떻게 작동하는지 가시화하기 -if문으로 작성할때 고려? 수정해야할 부분 */ #include<iostream> #include<stack> using namespace std; int main() { string a; cin >> a; string result; stack<char>s; for (int i = 0; i < a.size(); i++) { //피연산자는 결과값에 바로 출력 if ('A' <= a[i] && 'Z' >= a[i]) { result += a[i]; } //연산자는 괄호연산/*/연산/+-연산 나눠서 작성 else { switch (a[i]) { case'(': s.push(a[i]); break; case'*': case'/': while (!s.empty() && (s.top() == '*' || s.top() == '/')) { result += s.top(); s.pop(); } s.push(a[i]); break; case'+': case'-': while (!s.empty() && s.top()!='(') { result += s.top(); s.pop(); } s.push(a[i]); break; case')': while (!s.empty() && s.top() != '(') { result += s.top(); s.pop(); } s.pop(); break; } } } while (!s.empty()) { result += s.top(); s.pop(); } cout << result << endl; }
-
220119 백준 크게 만들기(2812)
- 알고리즘 구상 [초기에 구상한 개념] 팝 할 수 있는 조건을 찾고 그 중 가장 큰 숫자를 기준으로 위/아래 노드를 어떻게 처리할 것인지 생각해보기! 그러면 반복하여 풀 수 있을듯 [알고리즘]
-
N자리 숫자의 각 자리에 해당하는 수 중 가장 큰 값을 탐색함.
-
(N-1)-탐색한 수의 인덱스가 K보다 작은지 판별함
3-1. 만약 같거나 작다면 탐색한 인덱스 위로 모두 pop
3-2. 만약 크다면 탐색한 인덱스보다 큰 인덱스 중 가장 큰 값을 탐색함(그 후 2로 돌아가서 반복)
-
1~3반복 후 K의 값이 pop한 횟수보다 크면 위에서 탐색한 값보다 작은 인덱스를 범위로 해서 1~3 과정을 반복함.
-
K의 값이 pop한 횟수와 같아질 때까지 반복
[개념 수정]
-
벡터에 작은 자리의 수부터 노드를 쌓아줌.
-
벡터 내부에서 pop할 수 있는 가장 큰 값을 찾음(조건: k와 인덱스 고려)
-
선택한 값을 기준으로 위의 노드는 차례대로 pop한 뒤에 pop한만큼 k값을 빼줌
-
선택한 값은 정답vector에 담아두고 pop함. (이건 k값 수정하지 않음)
-
2~4과정을 k==0 만족할때까지 반복함
-
- k와 인덱스를 고려한 조건?
-
구현이 잘 안됨ㅠ.ㅠ
[필요한 변수]
-
pop횟수를 기록할 변수
-
주어진 조건에서 가장 큰 값을 저장할 변수
-
N자리의 수를 담아낼 자료...벡터.
-
- 코드로 구현 반복문 안의 인덱스는 집가면서 생각해보기
//백준2812 #include<iostream> #include<vector> #include<cmath> using namespace std; int main() { int n, k, number; cin >> n; cin >> k; cin >> number; vector<int>num; vector<int>answer; while (number != 0) { num.push_back(number % 10); number /= 10; } int max = num[n-1-k]; int idx = n-1-k; do { for (int i = n - 1 - k; i < n - 1; i++) { if (max < num[i]) { max = num[i]; idx = i; } } cout << "현재 범위 내 가장 큰 값의 인덱스" << endl; cout << idx << endl; for (int i = num.size()-1; i > idx; i--) { num.pop_back(); k -= 1; n -= 1; } answer.push_back(num.back()); num.pop_back(); //확인용 출력문. 쓸모는 없음 cout << "범위 내 최고값 인덱스의 앞부분은 삭제" << endl; for (int i = 0; i < num.size(); i++) { cout << num[i]; } cout << endl; cout << "현재 answer의 상태" << endl; for (int i = 0; i < answer.size(); i++) { cout << answer[i]; } cout << endl; }while (answer.size() != n - k); for (int i = 0; i < answer.size(); i++) { cout << answer[i]; } cout << endl; }cout << endl;
Author And Source
이 문제에 관하여(스택으로 응용문제 풀기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ppparkta/스택으로-응용문제-풀기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)