스택으로 응용문제 풀기

*이 글은 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)

• 알고리즘 구상 [초기에 구상한 개념] 팝 할 수 있는 조건을 찾고 그 중 가장 큰 숫자를 기준으로 위/아래 노드를 어떻게 처리할 것인지 생각해보기! 그러면 반복하여 풀 수 있을듯 [알고리즘]

  1. N자리 숫자의 각 자리에 해당하는 수 중 가장 큰 값을 탐색함.

  2. (N-1)-탐색한 수의 인덱스가 K보다 작은지 판별함

     3-1. 만약 같거나 작다면 탐색한 인덱스 위로 모두 pop

     3-2. 만약 크다면 탐색한 인덱스보다 큰 인덱스 중 가장 큰 값을 탐색함(그 후 2로 돌아가서 반복)

  3. 1~3반복 후 K의 값이 pop한 횟수보다 크면 위에서 탐색한 값보다 작은 인덱스를 범위로 해서 1~3 과정을 반복함.

  4. K의 값이 pop한 횟수와 같아질 때까지 반복

     [개념 수정]

  5. 벡터에 작은 자리의 수부터 노드를 쌓아줌.

  6. 벡터 내부에서 pop할 수 있는 가장 큰 값을 찾음(조건: k와 인덱스 고려)

  7. 선택한 값을 기준으로 위의 노드는 차례대로 pop한 뒤에 pop한만큼 k값을 빼줌

  8. 선택한 값은 정답vector에 담아두고 pop함. (이건 k값 수정하지 않음)

  9. 2~4과정을 k==0 만족할때까지 반복함

  • 2. 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;