약 10일 전 쯤 내가 풀었던 문제 같은데, 다시 보니까 못풀고 있어서, 여기에 다시 정리해보았다.

[알고리즘] 만나는 그 순간

문제 해결 방향

  1. A와 B 각각의 매 초별 위치를 배열에 기록
  2. 시간을 1초부터 검사하면서, A와 B의 위치가 일치하는 최초의 시점을 찾기.

주의할 점

  • 전체 이동 시간이 큰 배열을 필요로 할 수 있다. (MAX_T = 1000000)
  • A와 B의 시작 위치는 0으로 초기화되어야 한다.
  • 만약 움직임이 끝날 때까지 만나지 않으면 -1을 출력해야 한다.

코드

내 코드

#include <iostream>
using namespace std;

#define MAX_T 1000000

int n, m;
int pos_a[MAX_T + 1], pos_b[MAX_T + 1];     // 1 based indexing
int total_t = 0;

int main() {
    // 시작 위치
    pos_a[0] = 0;
    pos_b[0] = 0;

    cin >> n >> m;

    // A의 이동 기록
    for(int i = 0; i < n; i++) {
        char d;
        int t;
        cin >> d >> t;

        for(int j = total_t + 1; j <= total_t + t; j++) {
            if(d == 'L') pos_a[j] = pos_a[j - 1] - 1;
            else if(d == 'R') pos_a[j] = pos_a[j - 1] + 1;
        }
        total_t += t;
    }
    total_t = 0;

    // B의 이동 기록
    for(int i = 0; i < m; i++) {
        char d;
        int t;
        cin >> d >> t;

        for(int j = total_t + 1; j <= total_t + t; j++) {
            if(d == 'L') pos_b[j] = pos_b[j - 1] - 1;
            else if(d == 'R') pos_b[j] = pos_b[j - 1] + 1;
        }
        total_t += t;
    }

    // 만나는 시점 찾기
    int ans = 0;
    for(int i = 1; i <= total_t; i++) {
        if(pos_a[i] == pos_b[i]) {
            ans = i;
            break;
        }
    }

    if(ans) cout << ans;
    else cout << -1;
    return 0;
}

해설 코드

#include <iostream>
#define MAX_T 1000000

using namespace std;

int n, m;
int pos_a[MAX_T + 1], pos_b[MAX_T + 1];

int main() {
    cin >> n >> m;

    // A의 이동 기록
    int time_a = 1;
    for(int i = 0; i < n; i++) {
        char d; int t;
        cin >> d >> t;

        while(t--) {
            pos_a[time_a] = pos_a[time_a - 1] + (d == 'R' ? 1 : -1);
            time_a++;
        }
    }

    // B의 이동 기록
    int time_b = 1;
    for(int i = 0; i < m; i++) {
        char d; int t;
        cin >> d >> t;

        while(t--) {
            pos_b[time_b] = pos_b[time_b - 1] + (d == 'R' ? 1 : -1);
            time_b++;
        }
    }

    // 최초로 만나는 시간 탐색
    int ans = -1;
    for(int i = 1; i < time_a; i++) {
        if(pos_a[i] == pos_b[i]) {
            ans = i;
            break;
        }
    }

    cout << ans;
    return 0;
}

⚡️ 시간복잡도

  • 이동 기록: O(total_time)
  • 만나는 시점 탐색: O(total_time)
  • 전체 시간복잡도: O(total_time)