is Similar? | Notion

Two arrays are called similar if one can be obtained from another by swapping at most one pair of elements in one of the arrays.

Given two arrays a and b, check whether they are similar.

Example

For a = [1, 2, 3] and b = [1, 2, 3], the output should be

solution(a, b) = true.

The arrays are equal, no need to swap any elements.
For a = [1, 2, 3] and b = [2, 1, 3], the output should be

solution(a, b) = true.

We can obtain b from a by swapping 2 and 1 in b.
For a = [1, 2, 2] and b = [2, 1, 1], the output should be

solution(a, b) = false.

Any swap of any two elements either in a or in b won't make a and b equal.

Input/Output

[execution time limit] 3 seconds (java)
[memory limit] 1 GB
[input] array.integer a

Array of integers.

Guaranteed constraints:

3 ≤ a.length ≤ 105,

1 ≤ a[i] ≤ 1000.
[input] array.integer b

Array of integers of the same length as a.

Guaranteed constraints:

b.length = a.length,

1 ≤ b[i] ≤ 1000.
[output] boolean

true if a and b are similar, false otherwise.

풀이

a 와 b 의 동일 인덱스에 위치한 값이 같아야 한다.
Swap 기회는 한 번
Swap 할 숫자를 고를 때, a[i] 와 b[j] 의 값이 같더라도 a[j] = b[j] 일 경우 다른 수를 탐색해야 한다.

boolean solution(int[] a, int[] b) {
    // Swap 은 단 한 번 사용가능.
    boolean swap = true;
    
    // 순회 시작
    for (int i = 0; i < a.length; i ++) {
        // a 와 b 배열의 같은 인덱스에 있는 숫자가 다를 경우
        if (a[i] != b[i]) {
            // Swap 기회가 있을 경우
            if (swap) {
                // Swap 기회 소멸
                swap = false;
                // 서로 다른 자리의 숫자를 바꾸기 위한 기존 자리의 수 임시 저장
                int buff = b[i];
                
                // 현재 index + 1 부터 탐색 시작
                for (int j = i + 1; j < a.length; j ++) {
                    // 기존 a 의 i 인덱스 위치의 값과 b 의 j 인덱스 위치의 값이 같고
                    // b 의 j 인덱스 위치의 값과 a 의 인덱스 위치의 값이 다르면 스왑!
                    if (a[i] == b[j] && a[j] != b[j]) {
                        b[i] = b[j];
                        b[j] = buff;
                        
                        break;
                    }
                }
                
                // 스왑한 배열 인덱스 위치의 값 재확인을 위한 i --
                i --;
            } else {
                // Swap 기회가 없다면 바로 실패
                return false;
            }
        }
    }
    
    return true;
}