[BaekJoon/백준] 3048번 개미

 

다른분들처럼 깔끔하게 코드를 짜진 못했다. 하지만 시간복잡도는 더 절약한 것 같다.

 

아마 다른분들은 문자열에 방향성을 부여해서

0 : 오른쪽 이동, 1 : 왼쪽 이동으로 정의한 뒤에

 

000 111

001 011

010 101

101 010

 

이런식으로 해서 매 초 phase마다 포문을 돌리면서 '01' 을 찾으면 swap 해주는 방식을 사용하신 것 같다.

=> reverse()를 제외한 구현에서 O(T(n + m)) 시간복잡도

 

---

 

나는

시뮬레이션을 직접 돌려보면서, 규칙성을 찾았고

그걸 토대로 구현하였다.

시간복잡도면에서 내 구현이 더 빠르다고 생각한다.

=> reverse()를 제외한 구현에서 O(n + m)에 해결된다.

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;


int main() {
    
    
    int N, M, T;
    
    int p1 = 0, p2 = 0;
    
    string A, B;
    
    cin >> N >> M >> A >> B >> T;
    
    reverse(A.begin(), A.end());
    int gap = A.length() - T;

    
    if(gap > 0) {
        
        for(p1 = 0; p1 < gap && p1 < N; p1++) {
            cout << A[p1];
        }
        
        while(p1 < N || p2 < M) {
            if(p2 < M)
                cout << B[p2++];
            if(p1 < N)
                cout << A[p1++];
        }
        
        
    } else {
        gap = abs(gap) + 1;
        
        for(p2 = 0; p2 < gap && p2 < M; p2++) {
            cout << B[p2];
        }

        while(p1 < N || p2 < M) {
            if(p1 < N)
                cout << A[p1++];
            if(p2 < M)
                cout << B[p2++];
        }

    }
    cout << "\n";
    
    
    
}

 

 

소요 시간 : 30분