스택으로 응용문제 풀기

*이 글은 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 만족할때까지 반복함

      1. 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;

좋은 웹페이지 즐겨찾기