[자료구조]-[스택]-문제

1. 후위 표기식(백준 1918)

2. 오아시스 재결합(백준 3015)

3. 문자열 폭발(백준 9935, 10750)

----------------

1. 후위 표기식(백준 1918)

중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오

입력

첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있다.

출력

첫째 줄에 후위표기식으로 바뀐 식을 출력하시오

예제 입력  

A*(B+C)

예제 출력  

ABC+*

풀이

- 중위표기식을 후위로 표현하는 방법은 다음과 같다.

  1)문자는 그대로 출력

  2)연산자는, 스택에 이 연산자보다 우선순위 낮은 연산자 나올때까지 pop해서 출력 후 push

  3)'('의 경우는, 스택에 넣고, ')'만날 때까지 위 규칙대로 진행

  4)')'의 경우는, 스택의 내용 중 '('만날 때까지 pop하면서 출력

  5)수식 문자열의 마지막의 경우는, 스택내용 전부 출력

소스

#include <stdio.h>

#include <string.h>

 

char s[101], st[101];

int main() {

    int i,t=0,len;

    scanf("%s",s);

    len=strlen(s);

    for(i=0;i<len;++i) {

        switch(s[i]) {

        case '(':

            st[++t]='(';

            break;

        case ')':

            while(t>0 && st[t]!='(') { printf("%c",st[t]); t--;  }

            if(st[t] == '(') t--;

            break;

         case '*': case '/':

            while(t>0 && st[t]!='+' && st[t] != '-' && st[t] != '(' ) { printf("%c", st[t]); t--; }

            st[++t]=s[i];

            break;

         case '+': case '-':

             while(t>0 && st[t]!='(') { printf("%c", st[t]); t--; }

             st[++t]=s[i];

             break;

         default:

             printf("%c",s[i]);

             break;

        }

    }

    while(t>0) { printf("%c", st[t]); t--; }

    printf("\n");

 

    return 0;

}

2. 오아시스 재결합(백준 3015)

오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.

이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다.

두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.

줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)

둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다.

사람들이 서 있는 순서대로 입력이 주어진다.

출력

서로 볼 수 있는 쌍의 수를 출력한다.

예제 입력  복사

7

2

4

1

2

2

5

1

예제 출력  복사

10

풀이

- 스택 문제에서 꽤 어려운 편

- 요령은, 스택에 내림차순으로만 값이 존재하게 만들어 나간다. (스택의 top에 있는 값은, 스택에서 가장 작은 값)

  즉, 새로운 사람의 키 크기를 a라 했을 때, 스택에서 a보다 큰 값을 만날 때까지 pop하면서 cnt++

- 개념은, 왼편에 있는 사람과 현재 새롭게 들어오는 사람들과 페어가 가능한 지 보는 것. 만약 스택의 top에 있는 키 값이 s라고 한다면,

  (s<a)의 경우에는, s는 a와의 페어만 가능하고, 그 이후의 사람과는 a에 막혀서 페어를 이룰 수 없기에, 스택에서 pop한다. 

  pop하면서 카운트는 하나 증가(a와의 페어에 대한 카운트) 이렇게 pop해 나가면서 카운트 증가하는 것을 a보다 큰거 만날때까지 지속.

- 만약 (s>a)의 경우는 그냥 push하면서, 스택에 값이 있는 경우에 카운트 하나 증가 (기존 스택에 있는 s와 a의 페어에 대한 카운트)

- 문제는 같은 키의 사람이 연속해서 들어오는 경우이다. 밑에 예를 보면,     

        

i	1		2		3		4		5		6
	4		3		3		3		1		2
cnt			1		3		5		6		8
st		4		4,3		4,3		4,3		4,3,1		4,3

      

지금까지 위에서 얘기한 루틴에 적용하면 위와 같이 최종 카운트가 8이 나온다. 그러나 실제로는 아래와 같은 값이 나와야 한다.

i	1		2		3		4		5		6
	4		3		3		3		1		2
cnt			1		3		6		7		9
st		4		4,3		4,3		4,3		4,3,1		4,3

3이 연속해서 나오기에 새로운 3으로 스택값이 교체되는데, 실제로는 교체되어 pop되어버린 3과도 페어가 가능하기 때문. 예를 들어 5번째에 있는 1과 페어 가능한 것은 2번째, 3번째, 4번째의 3과 페어가 가능.

이렇게 보면, 스택에 최종 남아 있는 '3'은 그냥 3이 아니라 같은 3에 의해 교체되면서 남은 3이라는 것을 고려해주면 될 것이다.(고려안해주면 스택에 남아 있는 '3'과의 페어 1개만 고려해서 카운트를 1 증가하는데, 3번 연속해서 나온 3이라면 3을 더해주게 되도록)

- 이렇게 짠 것이 아래 소스이다.

소 스

#include <stdio.h>

#include <algorithm>

using namespace std;

 

typedef long long ll;

typedef pair<int,int> pii;

int N,t=0;

pii st[500001];

int main(){

    int a; 

    ll cnt=0;

    scanf("%d",&N);

    while(N--){

        scanf("%d",&a);    

        pii p = make_pair(a,1);

        while(t>0 && st[t].first <= a){

            cnt += (ll)st[t].second;   

            if(st[t].first == a) p.second += st[t].second;

            t--;

        }

        if(t!=0) cnt++;

        st[++t]=p;

    }

    printf("%lld\n",cnt);

    return 0;

}

3. 문자열 폭발(백준 9935, 10750)

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.

새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.

폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이 때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

출력

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

예제 입력  

mirkovC4nizCC44

C4

예제 출력  

mirkovniz

풀이

- 문자열 s와 폭발 문자열 t가 있을 때, s의 문자들을 차례로 스택에 쌓아가다가, t의 마지막 글자와 같은것을 만났을 때, 다시 거꾸로 t문자들을 거슬러가면서 스택에 남아있으면서 문자들과 비교해서 t문자열 모두와 같다면, 스택에서 해당 문자열 pop

- 이러한 과정을 계속하면 됨

소스

include <stdio.h>

#include <stack>

#include <string.h>

 

using namespace std;

char s[1000003], t[40], st[1000003];

int top = 0;

int main() {

    int i=0,j=0, tLen;

    scanf("%s\n%s", s, t);

 

    tLen = strlen(t);

    while (s[i]) {

        if (s[i] == t[tLen - 1]) {

            j = 0;

            while (((top - j) >= 0 && (tLen - 2 - j) >= 0 && (st[top - j] == t[tLen - 2 - j]))) j++;             

            if (j == (tLen - 1)) top -= (tLen - 1);    

            else st[++top] = s[i];

        }

        else {

            st[++top] = s[i];

        }

        i++;

    }

 

    if (top == 0) printf("FRULA\n");

    else {

        for (i = 1; i <= top; ++i) printf("%c", st[i]);

        printf("\n");

    }

     

    return 0;

}

-끝-