카페인 부족

문제 링크: https://www.acmicpc.net/problem/2493

주어진 조건을 요약해보면, 어떤 탑은 그 왼쪽에 자신보다 큰 탑이 있어야 발사한 레이저 신호를 송신하는 탑이 존재한다는 것입니다.

스택과 pair를 활용하여, 탑의 위치와 높이를 저장하는 식으로 해결했습니다.

우선 입력이 들어왔을 때 스택이 비어있다면, 그 탑의 레이저를 송신할 대상이 없으므로 0을 출력하고 탑의 위치와 높이를 스택에 저장합니다.

스택이 비어있지 않을 때 입력이 들어오면, 입력된 탑의 높이와 스택에 저장된 탑의 높이를 비교합니다.

입력된 탑의 높이가 더 높으면, 기존의 탑을 스택에서 제거하고, 새 탑을 스택에 저장해둡니다.

입력된 탑의 높이가 스택에 비해 같거나 낮으면, 입력된 탑이 송신한 레이저는 스택의 탑이 수신하게 됩니다.

스택에 저장된 탑의 정보를 출력하고 다음 탑의 정보를 입력받도록 하면 됩니다.

문제에 주어진 예제 6, 9, 5, 7, 4로 설명해보면,

처음 탑은 pair<1, 6>으로 표현이 가능합니다. 왼쪽에 그 어떤 탑도 없으므로 레이저를 수신하는 탑이 없습니다. 0을 출력하고 <1, 6>을 스택에 넣습니다.

9를 입력받고, 스택에 저장된 탑의 높이 6과 비교합니다. 9가 더 크므로 두 번째 탑의 레이저도 수신할 수 있는 탑이 없습니다.

0을 출력하고 <1, 6>을 스택에서 꺼낸 다음 <2, 9>를 넣어둡니다.

5가 입력되면 9와 5를 비교하여 5가 더 작으므로, <3, 5> 탑의 레이저를 <2, 9> 탑이 수신하게 됩니다.

수신하는 탑의 번호 2를 출력하고 다음 입력을 받습니다.

같은 방법으로 <4, 7> 탑의 정보도 <2, 9> 탑이 수신하게 됩니다.

4를 입력받았을 때, 7이 4보다 크므로 스택에 <4, 7>을 저장합니다.

입력이 끝날 때, 마지막 탑의 레이저를 수신하는 탑의 번호(=스택에 저장된 탑)를 출력하고 종료합니다.

C++

#include <cstdio>
#include <stack>
#include <utility>
using namespace std;

int main() {
    int num, input;
    stack<pair<int, int> > st;

    scanf("%d", &num);
    for(int i = 0; i < num; i++) {
        scanf("%d", &input);

        while(!st.empty()) {
            if(st.top().second > input) {
                printf("%d ", st.top().first);
                break;
            }
            
            st.pop();
        }

        if(st.empty()) printf("0 ");
        st.push(make_pair(i + 1, input));
    }

    return 0;
}

원래 cin, cout을 사용하여 작성하였는데 채점할 때 시간 초과가 나와서 printf, scanf를 사용하는 방식으로 실행 시간을 줄여서 해결했습니다.

문제 링크: https://www.acmicpc.net/problem/9935

문제 분류에는 스택이라고 표기되어 있지만, 꼭 쓰지 않아도 될 것 같아서 스택 없이 풀어보았습니다.

입력 받은 문자열을 우선 한 글자씩 결과를 저장할 문자열에 옮깁니다.

계속 옮겨주다가, 폭발 문자열의 마지막 글자와 같은 문자를 발견하면 비교를 시작합니다.

결과를 저장하는 문자열에 폭발 문자열이 있다면, idx를 줄여서 폭발 문자열 위에 입력 받은 문자열을 덮어씁니다.

원래 문자열이 끝나면, 결과 문자열의 끝에 NULL 캐릭터를 삽입합니다.

문제의 조건대로, 전부 폭발한 다음 남은 문자열이 없으면 (idx가 0이면) FRULA를 출력합니다.

C++

#include <iostream>
#include <string>
using namespace std;

int main() {
    char result[1000001]; // 결과를 저장할 char 배열 
    string input, tgt;
    int tgtLen, idx = 0;

    cin >> input >> tgt;
    tgtLen = tgt.length();

    for (int i = 0; i < input.length(); ++i) {
        result[idx++] = input[i]; // 입력된 문자열을 한 글자씩 옮김

        if (result[idx - 1] == tgt[tgtLen - 1]) { // 마지막으로 입력한 글자가 tgt의 끝 글자와 같으면 
            if (idx - tgtLen < 0) continue; // 예외 처리; result가 tgt보다 짧으면 검사할 필요 없음 
            bool hasTGT = true;

            for (int j = 0; j < tgtLen; ++j) {
                // idx 앞 쪽의 문자열이 tgt와 같은지 검사 
                if (result[idx - 1 - j] != tgt[tgtLen - 1 - j]) {
                    hasTGT = false;
                    break;
                }
            }
            if (hasTGT) idx -= tgtLen; // tgt가 존재하면 idx를 줄임 
        }
    }
    result[idx] = '\0'; // 결과의 끝에 NULL 문자 삽입. 
    idx == 0? printf("FRULA"): printf("%s", result);

    return 0;
}

문제 링크: https://www.acmicpc.net/problem/9012

스택을 활용하여 풀었습니다.

'('를 만나면 모두 스택에 넣고, ')'를 만나면 스택에서 원소를 꺼냅니다.

스택이 비어있을 때 ')'를 만나면 옳은 괄호 문자열이 아니므로, 바로 false를 리턴합니다.

문자열이 끝났을 때, 스택이 비어있지 않고 '("가 남아있다면 역시 올바르지 않은 문자열이므로 false를 리턴합니다.

C++

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool vpsCheck(string);

int main() {
    int count = 0;
    string str;
    cin >> count;

    for(int i = 0; i < count; i++) {
        cin >> str;

        if(vpsCheck(str)) cout << "YES" << endl;
        else cout << "NO" << endl; 
    }

    return 0;
}

bool vpsCheck(string str) {
    stack cStack;
    int len = (int)str.length();

    for(int i = 0; i < len; i++) {
        char c = str[i];

        if(c == '(') cStack.push(c);
        else {
            if(!cStack.empty()) cStack.pop();
            else return false;
        }
    }

    return cStack.empty();
}

문제 링크: https://www.acmicpc.net/problem/10799

스택을 활용하여 풀었습니다.

주어진 조건들에서, 여는 괄호 '('를 만나면 모두 스택에 넣었다가, ')'를 만나면 레이저인지 쇠파이프의 끝인지 구분하고, 스택에서 '('를 하나 꺼냅니다.

')'가 레이저를 의미하면, 쌓여있는 쇠파이프가 모두 잘리므로 결과에 그만큼 더해줍니다. (파이프의 수가 스택에 저장된 원소의 수와 같음을 이용합니다.)

')'가 파이프의 끝을 의미하면, 결과에 파이프 한 개를 더해줍니다.

C++

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int laser(string);

int main() {
    string str;
    cin >> str;
    cout << laser(str) << endl;

    return 0;
}

int laser(string str) {
    stack cStack;
    int result = 0; // 잘려나온 조각 수를 저장할 변수 
    
    for(int i = 0; i < str.length(); i++) {
        if(str[i] == '(') cStack.push(str[i]);  // (는 stack에 push
        else {  // 여는 괄호가 아니라면: 레이저인지 파이프의 끝인지 구분해야 
            cStack.pop();

            if(str[i - 1] == '(') result += cStack.size();  // 레이저이면: 파이프 수(=스택의 수) 만큼 잘려나감  
            else result++; // 파이프의 끝이면: 한 조각 늘어남 
        }
    }

    return result; // 총 조각 수 반환 
}

문제 링크: https://www.acmicpc.net/problem/1001

두 정수를 입력 받아서, 먼저 입력된 정수에서 나중에 입력된 정수를 뺀 결과를 출력하는 문제입니다.

C

#include <stdio.h>

int main(void) {
    int A, B;
    
    scanf("%d %d", &A, &B);
    printf("%d\n", A - B);
    
    return 0;
}

문제 링크: https://www.acmicpc.net/problem/1000

두 정수를 입력 받아서, 더한 결과를 출력하는 문제입니다.

C

#include <stdio.h>

int main(void){
    int A, B;
    
    scanf("%d %d", &A, &B);
    printf("%d\n", A + B);
    
    return 0;
}