[ABC250] C - Adjacent Swaps (AtCoder Beginner Contest 250 with Java)

문제 : abc250_c

  일단 단순히 swap만 하는 거였다면 별 문제가 없었을 것이다. 문제는 매번 swap해서 바뀌는 각 숫자의 위치를 유효한 시간 내에 찾아내야 한다는 점이다. 만약 매번 전체 배열을 순회하며 찾으려 한다면 O(N+QN)만큼(처음 N은 배열 입력받는 부분, QN은 각 쿼리마다 최대 N번 확인해야 하므로) 필요할 것이므로 시간내에 통과할 수 없다.

 

  따라서 배열을 2개 써서 다음과 같이 한번 생각해보자. N이 5인 경우이다.

  원래는 위의 저 '값 배열'만 가지고 해야했는데, '위치 기록용 배열'을 추가로 만들었다. B[z]는 값 z의 현재 idx를 나타낸다. 즉, A[B[z]] == z 이다. 이렇게 메모리를 더 써서 배열 하나를 더 두면 swap 시에 다음과 같이 해볼 수 있다. 현재 쿼리가 '3'이 주어졌다고 해보자. 그럼 z=3인 곳의 위치를 찾아 그 다음 idx와 값을 서로 변경해야 한다. 배열 A만 있었다면 처음부터 순회하면서 '3'을 찾고, 값을 바꿔 [1,2,4,3,5]가 되었을 것이다. 하지만 B를 둠으로써 '3'의 위치를 B[3]으로 O(1)로 찾을 수 있다. 그럼 A를 변경한 후, B는 어떻게 처리해야 할까? 마찬가지로 B도 스왑을 해줘야 한다.

 

즉, z=3일 경우 A[B[3]]과 A[B[3]+1]을 스왑해야 하고, B[3]과 B[A[B[3]+1]]을 스왑해줘야 한다. 그림으로 나타내면 다음과 같이 변경될 것이다.

  다음으로 또 '3'이 쿼리로 들어왔다면 다음과 같이 될 것이다.

 

위와 같이 연산 시 시간복잡도는 O(N+Q)로 줄어든다.

 

코드 : github

...
private void solution() throws Exception {
    int n = nextInt();
    int q = nextInt();
    int[] arr = new int[n];
    int[] pos = new int[n+1];
    for (int i = 0; i < n; i++) {
        arr[i] = i+1;
        pos[i+1] = i;
    }
    while (q-->0) {
        int cur = nextInt();
        int idx = pos[cur];
        int targetIdx = idx==n-1 ? idx-1 : idx+1;
        int targetVal = arr[targetIdx];
        arr[targetIdx] = cur;
        arr[idx] = targetVal;
        pos[cur] = targetIdx;
        pos[targetVal] = idx;
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < n; i++) {
        sb.append(arr[i]).append(' ');
    }
    System.out.println(sb);
}
...