[코드포스 / Codeforces] Round #860 (Div. 2)

Round #860 (Div. 2)

 

 

대회

https://codeforces.com/contest/1798

Dashboard - Codeforces Round 860 (Div. 2) - Codeforces

 

 

푼 문제

A. Showstopper

길이가 같은 배열 a와 b의 마지막 원소는 각 배열에서의 최댓값이어야 한다. 이때 배열 a, b에서 같은 인덱스에 위치한 원소는 서로 바꿀 수 있다. 이때 위 조건을 만족시킬 수 있는지 여부를 구하는 문제다.

 

먼저 배열 a에서 마지막 원소보다 큰 다른 원소가 있으면 배열 b의 원소와 swap 했다. 그런 다음 배열 a, b가 모두 조건을 만족하면 YES를 출력하고 만족하지 않으면 배열 b를 기준으로 다시 한번 진행한 다음 조건을 만족하면 YES, 그렇지 않으면 NO를 출력하도록 했다.

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++)
      cin >> a[i];
    for (int i = 0; i < n; i++)
      cin >> b[i];
    for (int i = 0; i < n; i++) {
      if (a[i] > a[n - 1]) {
        int tmp = a[i];
        a[i] = b[i];
        b[i] = tmp;
      }
    }
    if (a[n - 1] == *max_element(a.begin(), a.end()) && b[n - 1] == *max_element(b.begin(), b.end())) {
      cout << "YES\n";
      continue;
    }
    for (int i = 0; i < n; i++) {
      if (b[i] > b[n - 1]) {
        int tmp = a[i];
        a[i] = b[i];
        b[i] = tmp;
      }
    }
    if (a[n - 1] == *max_element(a.begin(), a.end()) && b[n - 1] == *max_element(b.begin(), b.end())) {
      cout << "YES\n";
    } else {
      cout << "NO\n";
    }
  }
  return 0;
}

 

 

B. Showstopper

이미 한 번 당첨된 사람은 다음 로또에 참가할 수 없다. 즉, 이미 참여했는데 다음 번에 다시 참여하면 해당 날에는 당첨되지 않은 것이다. map 자료구조를 사용해 누가 언제 로또를 구매했는지 저장했다. map의 특성상 key에 해당하는 value는 하나이므로 1일째에 참여한 사람이 2일째에 또 참여한다면 key=1의 value는 2가 될 것이다. 즉, 1일 차에는 절대 당첨되지 않았다는 것이다.

 

이렇게 입력을 받은 후 크기가 m+1인 배열을 만들고 -1로 초기화를 해줬다. 그리고 map의 각 key와 value에 대해 배열의 value 인덱스(날짜)에 -1이라면 key(사람)이 당첨될 수 있으므로 저장해줬다. 그러면 배열에 담긴 값은 각 날짜에 당첨될 수 있는 사람의 번호만 저장되어 있게 된다. 그러나 만약 당첨된 사람을 알 수 없는 경우 즉, -1로 초기화된 배열에서 값이 여전히 -1인 것이 있다면 -1을 출력하도록 예외처리를 해줬다.

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    int m, flag = 0;
    cin >> m;
    map<int, int> M;
    for (int i = 1; i <= m; i++) {
      int n;
      cin >> n;
      while (n--) {
        int x;
        cin >> x;
        M[x] = i;
      }
    }
    vector<int> ans(m + 1, -1);
    for (auto [n, day] : M)
      if (ans[day] == -1)
        ans[day] = n;
    for (int i = 1; i <= m; i++)
      if (ans[i] == -1) {
        flag = 1;
        break;
      }
    if (flag)
      cout << -1;
    else
      for (int i = 1; i <= m; i++)
        cout << ans[i] << ' ';
    cout << '\n';
  }
  return 0;
}

 

 

총평 및 여담

두 번째 코드포스 참여였다. 첫 참가는 Div. 4였는데 확실히 Div. 2는 난이도 차이가 컸다. A번에서 2번이나 틀리고 너무 오래 붙잡고 있어서 한 번에 맞은 B도 점수를 많이 못받았다. A는 솔루션이 떠오르지 않아 계속 붙잡고 있었고 B는 보자마자 떠올라서 바로 구현했는데 문제를 순서대로 풀기보다 A, B, C 정도는 문제를 모두 읽은 다음 솔루션이 떠오르는 것부터 풀어가는 습관을 가지면 좋을 것 같다.

 

C번부터는 이미 A에 힘을 다 써버린 상태라 집중이 되지 않아서 문제를 읽다가 포기했다. 여유가 생겼을 때 업솔빙 해봐야겠다. 그리고 확실히 백준처럼 문제를 푸는 것도 재밌지만 대회 형식으로 경쟁적 프로그래밍을 하는게 더 재미있는 것 같다.