Destructure Swap과 temp 변수를 사용한 Swap의 차이

입력값이 커서 최적화가 필요한 알고리즘 문제를 풀다가 아무리 해도 시간초과 문제가 해결되지 않아, Destructure assignment(구조 분해 할당)를 사용하는 swap의 문제인가 싶어서 찾아보니 temp 변수를 활용한 swap과 비교해서 많이 느리다고 한다.

 

Destructure assignment swap 

 

let a = 1;
let b = 2;

[a, b] = [b, a]

console.log(a) // 2
console.log(b) // 1

 

이런식으로 구조 분해 할당하여 각 변수 값을 바꾸는 방식을 말한다. 파이썬과 같은 다른 언어처럼 직관적인 교환이 가능하다. 

 

Temp variable swap

 

let temp;
let a = 1;
let b = 2;

temp = a;
a = b;
b = temp;

console.log(a) // 2
console.log(b) // 1

 

오래전부터 사용되어 오던 temp 변수를 이용한 swap이다. 간단하고 가장 눈에 익은 방식이다.

 

근데 개발에서는 실제로 어떨지 모르지만 내가 풀던 알고리즘 문제에서는 성능적으로 문제될 정도로 Destructure assignment swap이 느렸나보다, 시간초과를 도무지 해결할 수 없었다.

그래서 직접 테스트를 해봤다.

 

 

두 방식의 성능차이

 

 

반복문의 순회 횟수에 따라서 다를 것이고, 단위도 밀리 세컨드 단위일 뿐이지만 단순 계산으로는 거의 7배까지도 차이가 난다.

어이가 없었다. 아 Syntatic Sugar일 뿐이구나 싶었다.. 그래서 temp swap으로 바꿨더니 시간초과가 해결된다. 

오랜시간 동안 삽질을 했지만, 새로운 방식이 다 좋은 건 아니라는 것을 다시 한번 느꼈다. 기본에 충실하자.

 

 

Swap 방식에는 위 두가지 말고도 XOR 연산을 이용한 방식도 있다고 한다. 예전에 성능이 좋다고 쓰이기도 했다고 들었다.

 

 

XOR 연산을 통한 Swap

 

let a = 4; 
let b = 100;

a = a ^ b;
b = a ^ b;
a = a ^ b;
console.log(a); // 100
console.log(b); // 4

 

XOR은 정수 밖엔 쓰지 못한다고 한다. 문자열이나 실수의 경우에 정수로 변환된다. XOR은 비트 연산으로서 각 정수의 이진수 비트를 비교하여 둘 중 하나만 1인 경우에 1, 아니면 0으로 바꾸는 연산이다.

쓰지 않더라도 알고 있으면 좋을 듯하다. 

 

 

 

 

위에서 얘기한 알고리즘 문제이다.

 

https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요