BOJ 23970 알고리즘 수업 - 버블 정렬 3

출처:  https://www.acmicpc.net/problem/23970

---

문제 설명

길이 N 인 두개의 배열 A, B 가 있고, 배열 A 를 버블정렬로 정렬하는 과정에서 배열 B 와 같은 경우가 있는지 확인하는 문제

---

입력

배열 크기 N 과 두 개의 크기 N 인 정수 배열  A, B

출력

정렬하는 과정에서 같은 경우가 있으면 1 , 없으면 0

---

입력 예

6
4 6 5 1 3 2
4 1 3 2 5 6

출력 예

1

제약조건

5 <= N <= 1e4, 1 <= a_i, b_i <= 1e9

---

문제 풀이

Brute force 를 적용하면 bubble sort - O(N^2) 이고, 한번 swap 을 할 때 마다 길이 N 인 두 배열을 비교한다면 추가로 O(N) 이 필요해서, 전체는 O(N^3) 이 되고, 필요시간이 길어져서, 제한시간안에 해결할 수 없다.  ( N=10000 인 경우 O(N^3) 이면 1e12 정도의 계산이 필요하고, 보통 1e9 정도의 계산이 제한시간의 경계이다.)

 

먼저 확인할 것은 주어진 배열이 서로 순서만 다른 배열인지 아니면 내부에 값들이 다른 서로 다른 배열인지 구분해야 한다. 서로 다른 배열이라면, 정렬과정에서 같은 경우가 나올 수는 없다.

 

 

다음으로 순서만 서로 다른 배열이라고 하면 제일 앞에서부터 어디까지가 같은지 비교한 위치를 기록해서 그 이후 값들의 비교를 중심으로 비교하는 과정에서 중복을 줄일 수 있다. 앞에서부터 배열 A 와 배열 B 를 비교해서 일치하는 위치를 m_end로 기억한다. 배열 A를 정렬하는 과정에서 서로 바뀌는 위치를 k 라고 할 때,  k < m_end 인 경우는 계속되는 정렬과정에서 원래 있던 값으로 돌아 갈 수 없으므로 실패가 된다. 또한 m_end < k 인 경우에는 배열 A 와 배열 B 를 비교하면서, 마지막 일치하는 위치 이후의 값들만 비교하고, 계속해서 m_end 값을 갱신해서, 추가적으로 비교해야 하는 경우를 줄 일 수 있다.

프로그램 내용

..
    if(j < m_end)
    {
        cout << 0;
        return 0;
    }

    for(int k = m_end; k<tN; ++k)
    {
        if(vals[k] == refs[k])
        {
            m_end++;
        }
        else
        {
            break;
        }
    }

    if(m_end == tN)
    {
        cout << 1;
        return 0;
    }
...
...

 

관련된 문제