지먀

https://www.acmicpc.net/problem/1966

풀이

queue와 priority_queue를 사용하여 푸는 문제다.

예제 입력의 마지막 테스트 케이스를 예로 들면,

이므로 6개의 문서 중요도 중 0번째에 위치한 1의 출력 순서가 몇 번째인지를 출력하면 된다.

해당 문서의 중요도 뿐 만 아니라 위치(index값)도 고려해야하기 때문에, 큐에 구조체를 사용해서 중요도와 index를 함께 저장할 것이다.

큐에 구조체를 쓸 생각을 못해서 풀이 시간이 오래 걸렸다....

먼저 우선순위 큐를 사용하여 중요도를 내림차순으로 정렬한다.

9 1 1 1 1 1

큐에는 index와 중요도가 함께 저장된다.

index: 0 1 2 3 4 5

importance: 1 1 9 1 1 1

큐와 우선순위 큐의 맨 앞 값을 비교하여 일치하지 않을 경우 큐의 front 값을 pop하여 뒤로 push한다.

1 9 1 1 1 1

9 1 1 1 1 1

위와 같이 정렬 되어 큐와 우선순위 큐의 맨 앞 값이 9로 일치하면, pop해준다. 

1이 출력될 때까지 반복한다.

코드

#include <iostream>
#include <queue>

using namespace std;

struct st {
    int index;  //몇 번째인지 저장
    int importance;    //중요도 저장
};

int main() {
    int t; scanf("%d", &t);  //테스트 케이스 개수
    for (int i = 0; i < t; i++) {
        int N, M; scanf("%d %d", &N, &M);    //N: 문서 개수, M: 몇 번째로 인쇄되었는지 궁금한 문서가 놓인 위치(맨 왼쪽 0)

        priority_queue<int> p_q;    //내림차순 정렬
        queue<st> q, turn_q, turn;      //q: 숫자 저장, turn_q: 찾고자하는 문서 위치를 turn에 저장하기 위한 큐, turn: 찾고자 하는 문서의 index와 importance 저장

        for (int i = 0; i < N; i++) {
            int I; scanf("%d", &I);     //I: 중요도
            q.push({i, I});
            turn_q.push({i, I});
            p_q.push(I);
        }

        for (int i = 0; i < M; i++) {
            turn_q.push(q.front());
            turn_q.pop();
        }
        turn.push(turn_q.front());

        int count = 0;
        while(!q.empty()) {
            if (q.front().importance == p_q.top()) {
                if (q.front().index == turn.front().index) {
                    printf("%d\n", count + 1);
                    break;
                }
                else {
                    count++;
                    q.pop();   
                    p_q.pop(); 
                }
            }
            else {
                q.push(q.front());
                q.pop();
            }
        }
    }
}

https://www.acmicpc.net/problem/4949

풀이

스택을 이용해 푸는 문제. 9012번과 비슷해서 쉽게 풀릴 줄 알았는데 괄호의 종류가 많아지면서 풀이할 때 헤맸다. 괄호가 (소괄호)와 [대괄호] 두 종류이니 스택도 두 개 필요하겠지라고 단순히 생각했다가 한참 헤맸다.

입력받은 한 문장을 for문으로 읽어들이며 (, ), [, ] 네 가지 문자를 만날 때 마다 적절한 조건을 걸어 스택에 넣거나 빼주면 된다.

(와 [의 경우 추가 조건 없이 스택에 push해준다. 단, ( ]와 같이 짝지어질 경우 틀린 것이므로 두 괄호의 종류를 구분하여 push한다.

)와 ]는 각각 (, ]와 짝을 이루면 pop해서 스택에서 제거한다.

"yes"를 출력하기 위해서는 입력받은 한 문장을 for문을 돌며 끝까지 읽어야하기 때문에, "no"를 출력하는 경우를 먼저 찾아 거른다.

)를 입력받은 경우를 예로 들면, 스택이 비어있거나 스택의 top이 (가 아닌 경우 "no"를 출력하고 for문을 종료하여 다음 새로운 문장을 입력받는다. 위 조건에 걸리지 않고 for문이 종료되어도 스택이 비어있지 않다면 "no"를 출력한다. 위 조건을 모두 만족한 경우 "yes"를 출력한다.

코드

#include <iostream>		//getline 함수 (\n까지 문자열 입력 받음)   
#include <stack>
using namespace std;

int main() {
    while (1) {  
        stack<int> st;
        string tmp; getline(cin, tmp);
        if (tmp == ".") return 0;
        int flag = 0;

        for (int i = 0; i < (int)tmp.size(); i++) {
            if (tmp[i] == '(') st.push('(');

            else if (tmp[i] == '[') st.push('[');
        
            else if (tmp[i] == ')') {
                if (st.empty() || st.top() != '(') {    //st가 비어있거나 top이 )일 경우
                    flag = 1;
                    break;
                }
                else if (!st.empty() && st.top() == '(') st.pop();
            }

            else if (tmp[i] == ']') {
                if (st.empty() || st.top() != '[') {
                    flag = 1;
                    break;
                }
                else if (!st.empty() && st.top() == '[') st.pop();
            }
        }
        if (flag) printf("%s\n", "no");
        else if (st.size()) printf("%s\n", "no");
        else printf("%s\n", "yes");
    }
}

https://www.acmicpc.net/problem/4153

풀이

두 가지 방법으로 풀었다. 첫 번째 풀이는 여러 입력 테스트 케이스를 배열에 모두 입력받아 각 케이스가 직각 삼각형의 조건을 만족하는지 확인하는 것이다. 결과 또한 배열에 모두 저장한 뒤 출력한다. 여러 개의 테스트 케이스를 각각 입력해도 예제 출력처럼 한 번에 결과가 출력되도록 풀어야 한다고 생각했는데, 아니었다..! 그래서 두 번째 풀이는 테스트 케이스를 입력할 때마다 조건을 만족하는지 확인하도록 했다.

코드

//첫 번째 풀이

#include <iostream>
#include <cmath>    //pow 제곱
#include <cstring>  //strcpy 문자열 복사
#include <algorithm>    //sort 오름차순 정렬
#define MAX 50

int input[MAX];
char res[MAX][MAX];

using namespace std;

int main() {
    for (int i = 0; ; i++) {
        cin >> input[i];
        if (!input[i]) break;
    }

    for (int i = 0, j = 0; input[i]; i += 3, j++) {
        sort(&input[i], &input[i + 3]);     //sort(시작 주소, 끝 주소 + 1)
        if (pow(input[i], 2) + pow(input[i + 1], 2) == pow(input[i + 2], 2)) strcpy(res[j], "right");
        else strcpy(res[j], "wrong");
    }

    for (int i = 0; res[i][0]; i++) {
        cout << res[i] << endl;
    }
    
}

//두 번째 풀이

#include <iostream>
#include <algorithm>
#define SIZE 1000

int arr[SIZE];
using namespace std;

int main() {
    while(1) {
        for (int i = 0; i < 3; i++) {
            scanf("%d %d %d", &arr[i], &arr[i + 1], &arr[i + 2]);
            if (!arr[i] && !arr[i + 1] && !arr[i + 2]) return 0;
            sort(&arr[i], &arr[i + 3]);       //sort(시작 주소, 끝 주소 + 1) 오름차순 정렬
            if (arr[i] * arr[i] + arr[i + 1] * arr[i + 1] == arr[i + 2] * arr[i + 2]) {
                printf("right\n"); 
                break;
            }
            else {
                printf("wrong\n"); 
                break;
            }
        }
    }
}