백준 3230번 [금메달, 은메달, 동메달은 누가?](C++) -yes6686- 티스토리

백준 문제 풀이: 3230 (금메달, 은메달, 동메달은 누가?)

---

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

문제 설명:

주어진 두 개의 순서 정보에 따라 금메달, 은메달, 동메달을 받을 사람을 정하는 문제입니다. 1차 순서 n명과 2차 순서 m명의 입력에 따라 메달 순위를 출력합니다. 최종 순서에서 상위 **3명**(금, 은, 동)을 출력합니다.

---

문제 해결 코드

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

vector<int> v1; // 1차 순서
vector<int> v2; // 최종 순서

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    // 1차 순서를 입력받아 v1에 저장
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        v1.insert(v1.begin() + (x - 1), i);
    }

    // v1에서 m명까지 남기기
    while (v1.size() > m) {
        v1.pop_back();
    }

    // 2차 순서에 따라 v2에 최종 순서 정리
    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        v2.insert(v2.begin() + (x - 1), v1.back());
        v1.pop_back();
    }

    // v2에서 상위 3명만 남기기
    while (v2.size() > 3) {
        v2.pop_back();
    }

    // 결과 출력
    for (auto it = v2.begin(); it != v2.end(); it++) {
        cout << *it << '\n';
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘: 1차 순서를 받아 순서를 재배치한 후, 2차 순서에 따라 최종 순서를 결정합니다.
• 구현 세부사항:
  • v1.insert(): 1차 순서에 따라 순서를 재배치합니다.
  • 1차 순서에서 **m명**만 남기기 위해 pop_back()을 사용합니다.
  • v2.insert(): 2차 순서에 따라 남은 순서를 재정렬합니다.
  • 최종 순서에서 상위 **3명**(금, 은, 동)만 남기기 위해 pop_back()을 사용합니다.
• 시간 복잡도 분석:
  • 1차 순서 재배치는 O(n),
  • 2차 순서 재배치는 O(m),
  • 결과적으로 전체 시간 복잡도는 O(n + m)입니다.

---

결과

입력된 순서에 따라 금메달, 은메달, 동메달을 받을 사람을 정확하게 출력합니다.

• 입력 예시:

  5 3  
  2 1 4 3 5  
  3 1 2

• 출력 예시:

  5  
  4  
  3

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!