알고리즘 백준 문제 풀이 - 4차시

9012번 - 괄호

#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;

int main() {
    char str[100];
    int n;
    cin >> n;      //입력 받는다

    for (int h = 0; h < n; h++) {
        int count = 0;
        queue<char> q;    //큐 선언

        cin >> str;  //((()))()()()()())(((()()( 입력 받기
        for (int i = 0; str[i] != '\0'; i++) {
            q.push(str[i]);     //큐에 넣어주기
        }

        int num = q.size();  
        bool no = false;  

        for (int i = 0; i < num; i++) {
            if (q.front() == '(') {
                count++;   // ( 가 나왔을떄 카운트 ++;
                q.pop();
            }
            else if (q.front() == ')') {
                if (count > 0) {
                    count--;    // 카운트가++인 상태(즉 (가 나온 상태 일때) )가 나온다면 ok;
                    q.pop();
                } else {   // 카운트가++인 상태(즉 (가 나온 상태 일때) )가 아니라면 나온다면 no;
                    printf("NO\n"); 
                    no = true;
                    break;
                }
            }
        }

        if (!no) {
            if (count == 0) printf("YES\n");  // 잘 작동이 되었다면 YES 출력
            else printf("NO\n"); //아니라면 NO 출력
        }
    }
    return 0;
}

 

3986번 - 좋은 단어

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

int main() {
    int n;
    scanf("%d", &n); // 테스트 케이스 수 입력을  받는다
    int count = 0;

    for (int i = 0; i < n; i++) {
        char str[100001];  // 좋은 단어 후보?를 입력 받는다// 좋은 단어 후보?를 입력 받는다
        scanf("%s", str);

        stack<char> s;
        int len = strlen(str); //길이 측정

        for (int j = 0; j < len; j++) {
            if (!s.empty() && s.top() == str[j]) { //비어있지 않고 맨 위의 값과 str[j]값이 같다면 맨위의 값 pop
                s.pop();
            }
            else {
                s.push(str[j]);//아니라면 str[j]값 넣어주기
            }
        }

        if (s.empty()) { //비어있는지 확인한다
            count++;
        }
    }

    printf("%d\n", count);//출력 ^^

    return 0;
}

 

 

1966번 - 프린터 큐

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstdio>

using namespace std;

struct Printer { //중요도와 인덱스를  표현 할수잇는 구조체 선언
    int jungyo;
    int idx;
};

bool compare(int a, int b) { //0과 1을 내보내는 bool로 함수 선언
    return a > b;
}

int main() {
    int t;
    cin >> t; //테스트 케이스 수를 입력 받는다

    while (t--) { //while문은 0이면 동작을 하지 않는다 그러므로 1씩 줄여 0이 되게 한다
        int n, m;
        cin >> n; // 문서 갯수
        cin >> m;// 몇번째 인지

        queue<Printer> q;
        int arr[100] = {0};

        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            q.push({x, i}); 
            arr[i] = x;
        }

        sort(arr, arr + n, compare); //정렬 해준다

        int count = 0;
        int jung = 0;

        while (q.empty() == 0) {
            Printer front = q.front(); // 아까 맨처음에 선언해준 구조체
            q.pop();

            if (front.jungyo == arr[jung]) {
                count++;
                if (front.idx == m) {
                    cout << count; //출력 해주고
                    cout << '\n';
                    break;
                }
                jung++; //중요도를 올려준다!`
            } else { 
                q.push(front); 
            }
        }
    }

    return 0;
}

 

14729번 - 칠무해

#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    int n;
    double arr[10000000]; 
    
    scanf("%d", &n); //학생수 입력 받기

    for (int i = 0; i < n; i++)
        scanf("%lf", &arr[i]); //실수형으로 입력 받기 ( 20.00등으로 나오니까 )

    sort(arr, arr + n); //정렬 함수 사용
    
    queue<double> q; //큐 선언
    
    for (int i = 0; i < n; ++i)
        q.push(arr[i]); //순서대로 큐에 집어 넣기

    for (int i = 0; i < 7; ++i) { //칠무해(즉 7명 뽑는다) 이기때문에 7번 반복
        if (q.empty()) { //만약 비어있다면  멈추기
            break;
        }
        printf("%.3lf\n", q.front()); //정렬을 했기떄문에 출력
        q.pop();
    }

    return 0;
}

 

후기

c++이 아직은 조금 어색 하지만 cin, cout, sort 등이 유용하다