[SWEA_모의SW역량테스트] 5648번 - 원자 소멸 시뮬레이션

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRFInKex8DFAUo#

SW Expert Academy

이 사이트 기준 정답률 16%의 문제다.

내가 낸건 2차원/3차원 배열 이런거 사용 안하고

1차원 벡터만 사용해서 푼 답안이다. 근데 Pass는 아니고 0/50 테케통과라는데 문제의 테케와 댓글의 테케들은 모두 맞는다. 단순히 정답을 못맞춰서 0/50이 아니고 시간 초과라는데 이해가 안간다. N=10짜리 10개 돌려봤는데 10ms걸리는 것으로 봐서는 한개에 보통 1ms정도 걸리는건데 왜 안될까. 시간 초과보다는 어떤 다른 문제가 있는듯하다.

 

일단 코드를 올려본다. (제출 테케 제외하면 다 맞음)

나는 다른사람들과 좀 다르게 벡터의 삭제 함수를 활용해서 풀었다. (47~70라인 중요)

#include <iostream>
#include <vector>
 
using namespace std;
int T, N, K, d;
double x, y;
typedef struct dir{
    double dr, dc;
}dir;
dir direction[4] = { { 0, 0.5 }, { 0, -0.5 }, { -0.5, 0 }, { 0.5, 0 } }; // 북, 남, 서, 동
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    for (int tc = 1; tc <= T; tc++){
        vector<pair<pair<double, double>, pair<int, int> > > atoms;
        cin >> N;
        for (int i = 0; i < N; i++){
            cin >> x >> y >> d >> K;
            atoms.push_back(make_pair(make_pair(x, y), make_pair(d, K))); // 행,열,방향,에너지 저장.
        }
        int EnergySum = 0;
        int cnt = 0;
        while (1){
            // 1. 이동
            for (int i = 0; i < atoms.size(); i++){
                int d_atom = atoms[i].second.first;
                atoms[i].first.first += direction[d_atom].dr;
                atoms[i].first.second += direction[d_atom].dc;
            }
            // 2. 범위밖 원소 제거
            int lp_cnt = atoms.size();
            for (int i = 0; i < lp_cnt; i++){
                double cr = atoms[i].first.first, cc = atoms[i].first.second;
                if (cr < -1000.0 || cr > 1000.0 || cc < -1000.0 || cc > 1000.0){
                    atoms.erase(atoms.begin() + i);
                    i--;
                    lp_cnt--;
                }
            }
            // 3. 원소 수 검사 및 종료 조건 확인
            if (atoms.size() <= 1) break;
 
            // 4. 동일위치 원소 검사 및 에너지 방출계산
            int lpt_cnt = atoms.size();
            for (int i = 0; i < lpt_cnt; i++){
                bool more = false;
                double fir = atoms[i].first.first;
                double sec = atoms[i].first.second;
                for (int j = i + 1; j < lpt_cnt; j++){
                    double nfir = atoms[j].first.first;
                    double nsec = atoms[j].first.second;
                    if (fir == nfir && sec == nsec){
                        more = true;
                        EnergySum += atoms[j].second.second;
                        atoms.erase(atoms.begin() + j);
                        j--;
                        lpt_cnt--;
                    }
                }
                if (more){
                    EnergySum += atoms[i].second.second;
                    atoms.erase(atoms.begin() + i);
                    i--;
                    lpt_cnt--;
                }
            }            
        }
        // 5. 현재 테케 정답 출력
        cout << "#" << tc << " " << EnergySum << '\n';
    }
    return 0;
}

 

아래는 벡터 내 동일 요소 제거에 대한 내 실험코드와 실행결과다.

비슷한 연산을 PS하면서 많이 해본거같은데 이번 기회에 제대로 체화했다. 꽤 편리한 모듈이므로 잘 익혀두고 쓰면 좋은 도구가 되겠다.

#include <iostream>
#include <vector>
 
using namespace std;
typedef pair<int, int> pii;
 
int main(){
    vector<pair<pii, pii> > v;
    v.push_back(make_pair(make_pair(7, 7), make_pair(-1, 1)));
    v.push_back(make_pair(make_pair(2, 1), make_pair(-1, 1)));
    v.push_back(make_pair(make_pair(1, 1), make_pair(-1, 1)));
    v.push_back(make_pair(make_pair(1, 1), make_pair(-1, 1)));
    v.push_back(make_pair(make_pair(2, 2), make_pair(-1, 1)));
    v.push_back(make_pair(make_pair(2, 2), make_pair(-1, 1)));
    v.push_back(make_pair(make_pair(3, 3), make_pair(-1, 1)));
    v.push_back(make_pair(make_pair(2, 2), make_pair(-1, 1)));
    v.push_back(make_pair(make_pair(3, 3), make_pair(-1, 1)));
    v.push_back(make_pair(make_pair(3, 3), make_pair(-1, 1)));
 
    int lpt_cnt = v.size();
    for (int i = 0; i < lpt_cnt; i++){
        int fir = v[i].first.first;
        int sec = v[i].first.second;
        bool more = false;
        for (int j = i+1; j < lpt_cnt; j++){
            int n_fir = v[j].first.first;
            int n_sec = v[j].first.second;
            if (fir == n_fir && sec == n_sec){
                more = true;
                v.erase(v.begin() + j);
                j--;
                lpt_cnt--;
            }
        }
        if (more){
            v.erase(v.begin() + i);
            i--;
            lpt_cnt--;
        }
        for (int k = 0; k < v.size(); k++){
            cout << v[k].first.first << " " << v[k].first.second << " " << v[k].second.first << " " << v[k].second.second << '\n';
        }
        cout << '\n';
    }
    if (v.size() == 0) cout << "다지움!";
    return 0;
}

실행결과. 가장 좌측의 요소부터 검사를 해서 검사기준의 인덱스 좌측으로는 당연히 동일 요소는 이미 지워졌으므로 검사를 안하고, 오른쪽의 요소부터 계속해서 검사해서 지우고, for문의 인덱스 ++를 고려해 -- 해주는 것과 전체 루프 범위의 크기를 --해주는 것이 핵심이다.