[코드포스] 정적배열 사용시 주의할점

https://codeforces.com/contest/1775/problem/B

Problem - B - Codeforces

위 문제를 풀다 새로 알게 된 주의사항이 있어 포스팅하게 되었습니다.

 

[개요]

1. 해당 문제는 어느 코포문제와 마찬가지로 테스트케이스로 이루어진 문제입니다.

2. 문제에 대한 풀이로 O(k) 풀이를 작성하였습니다. "k in all tests does not exceed 10^5"

 

자신있게 제출해본 결과 

[문제의 코드]

#include<bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5 + 5;
int n, k, cnt[MAX_N];

void solve()
{
   memset(cnt, 0, sizeof(cnt));
   cin >> n;

   int x;
   vector<vector<int>> q(n);
   for(int i=0; i<n; ++i) {
      cin >> k;
      for(int j=0; j<k; ++j) {
         cin >> x;
         cnt[x]++;
         q[i].push_back(x);
      }
   }

   bool ans = false;
   for(int i=0; i<n; ++i) {
      bool flag = true;
      for(auto& x : q[i]) {
         if(cnt[x] == 1) {
            flag = false;
            break;
         }
      }

      if(flag) {
         ans = true;
         break;
      }
   }

   cout <<(ans ? "Yes" : "No") << '\n';
}

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

   int TC;
   cin >> TC;

   while(TC--) {
      solve();
   }
   return 0;
}

 

[당시의 심정]

??? TL이 뜬것이 이해가 되지 않았습니다. push_back을 emplace_back으로 수정해야하나 생각도 들었지만 2000ms라 수정해도 해결될거같지 않았습니다.

1. 해당 코드가 O(k)가 아닐  것이다.

2. 더 효율적인 풀이가 있을것이다.

둘 중 2번 위주로 생각하여 결국 시간내에 해결하지 못하였습니다.

 

[문제 해결]

대회 다음날 차분하게 문제를 다시 보니 memset 함수를 보고 배열 사이즈와 테스트 케이스를 보니 배열 사이즈는 2*10^5 이고, 테스트 케이스는 최대 10^5이었습니다. 둘을 곱하게 되면 당연히 TL....

 

memset의 시간복잡도가 O(1)이 아닌 O(n)이기에 테스트케이스로 이루어진 문제에서는 초기화가 필요하다면 해당 배열사이즈와 tc최대횟수를 고려해야하며 문제가 생길시에는 map과 같은 컨테이너를 사용해서 불필요한 메모리와 연산을 줄여야 할 것 같습니다.

 

[문제가 해결된 코드]

#include<bits/stdc++.h>

using namespace std;

map<int,int> mp;
vector<vector<int>> p;
int n, k;

void solve()
{
  mp.clear();
  p.clear();

  cin >> n;
  p.resize(n);

  for(int i=0; i<n; ++i) {
    cin >> k;
    p[i].resize(k);

    for(int j=0; j<k; ++j) {
      cin >> p[i][j];
      mp[p[i][j]]++;
    }
  }

  bool ans = false, flag;
  for(int i=0; i<n; ++i) {
    flag = true;

    for(auto& x : p[i]) {
      if(mp[x] == 1) {
        flag = false;
        break;
      }
    }

    if(flag) {
      ans = true;
      break;
    }
  }

  cout << (ans ? "Yes" : "No") << '\n';
}

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

  int TC;
  cin >> TC;

  while(TC--) {
    solve();
  }
  return 0;
}

 

O(k)라고 생각했던 코드는 정적배열과 memset함수로 인해  O(tc*p)이였고, 정적배열에서 map으로 컨테이너 수정하여 O(k*logn)으로 시간내에 해결됨을 확인하였습니다.