[99클럽 코테 스터디 30일차 TIL] #정렬5

30일 차입니다. 벌써 30 일대가 됐다는 게 너무 신기하네요. 시간이 참 빠른 것 같습니다.

오늘도 열심히 공부해 봐야겠죠. 파이팅 해보겠습니다.

문제 설명

---

 

테스트 케이스 t가 주어지고 세준이와 세비의 병사수 n, m이 각각 주어집니다.

그리고 세준, 세비의 병사들의 전투력이 차례대로 주어지며 이들의 전투력을 비교해서 끝내 누가 이기는지를 출력하는 문제입니다.

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

 

 

생각 흐름

---

음.. 처음에 이 문제를 봤을 때, 뭐랄까.. 굉장히 쉬운 문제구나 싶었습니다.

 

문제의 조건을 주어진 대로 코드를 작성해 나가면 쉽게 풀 수 있겠구나 싶어서 무작정 코드를 작성했던 것 같습니다.

 

테스트 개수가 주어졌으니 t라는 변수를 선언해서 받고 while (t--)을 통해 반복문을 돌려준 다음, n, m 변수를 선언 그리고 각각의 병사 전투력들을 받아오도록 작성했습니다.

 

보니까 가장 약한 병사들이 하나씩 죽는 조건이 문제에 있었어서 오름차순 정렬이 필요하다는 생각을 하였고 이를 위해 우선순위 큐를 오름차순으로 선언해 주었습니다.

 

priority_queue <int, vector <int>, greater <int>> sejun, sebi; 이런 식으로 greater <int>을 이용해 오름차순 우선순위 큐를 2개 선언해 주었습니다.

 

병사들의 전투력을 일일이 집어넣고 top()들을 서로 비교해서 sejun보다 sebi보다 작으면 sejun.top()을 pop 반대의 경우에는 sebi의 top이 pop 하게 하여서 조건문을 완성했습니다.

 

그리고 병사들이 다 죽은 경우 S, B를 조건에 따라 출력하여 마무리하였습니다.

 

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

int main () {
    ios_base::sync_with_stdio();
    cin.tie(); cout.tie();

    int t; // 테스트 개수 t
    cin >> t;

    while (t--) {
        int n, m;
        cin >> n >> m;
        priority_queue <int, vector<int>, greater<int>> sejun, sebi;
        // 오름차순으로 정렬을 해 가장 작은 수가 top()에 위치하도록 함

        for (int i = 0; i < n; i++) {
            int temp;
            cin >> temp;
            sejun.push(temp);
        }
        for (int i = 0; i < m; i++) {
            int temp;
            cin >> temp;
            sebi.push(temp);
        }

        bool flag = true;
        while (flag) {
            int minsejun = sejun.top();
            int minsebi = sebi.top();

            if (minsejun < minsebi) {
                sejun.pop();
            }
            else {
                sebi.pop();
            }

            if (sebi.empty()) {
                flag = false;
                cout << "S" << "\n";
            }
            else if (sejun.empty()) {
                flag = false;
                cout << "B" << "\n";
            }
        }

        
    }

    return 0;
}

 

음.. 뭐랄까 세준, 세비가 모두 이기지 않은 경우에 C를 출력을 하라는데 ,, 그런 경우는 없어 보여서 일단 이렇게 작성하고 제출을 했는데 맞아서 신기했던 문제였습니다.

 

 

공부한 내용 정리

---

뭔가 문제를 풀어놓고 찜찜한 느낌이 들어서 다른 사람들의 코드를 찾아보았습니다.

항상 짧고 간결하게 코드를 작성하고 싶은 마음이랄까요,,

 

찾아보니까 다른 분들의 코드도 저와 비슷하게 짠 것 같아서 제가 예상외로 잘 풀었다는 생각을 하였습니다.

벡터, sort()로 푸신분들이 많았는데 오히려 우선순위 큐로 푼 제가 더 간결하게 잘 풀었다는 생각을 했습니다.

 

역시 우선순위 큐는 좋은 자료구조인 것 같습니다.