[python3] 1470. Shuffle the Array

풀이 일자: 23.02.06

난이도: [Easy]

분류: [Array]

문제 내용

[x1,x2,...,xn,y1,y2,...,yn]이 주어지면 [x1,y1,x2,y2,...,xn,yn]으로 변환하는 문제

 

문제 해결 흐름

1. 단순하게 생각

→ ans용 array를 하나 만들어서 0부터 n-1을 순회해 가면서 i번째와 i+n번째 수를 배열에 넣어가면 완성.

다른 해결 방식

1. 단순하게 생각하면 매우 쉽지만 만약 in-place로 풀어야 한다면?(만약 새로 배열을 만들 수 없는 메모리만 제공한다면?)

→ bit를 이용하자..

 

현재 숫자의 크기 조건이 (1 <= nums[i] <= 10^3) 1000 = 1111101000₍₂₎

즉 해당 숫자를 나타내는 메모리 공간 중 실질적으로 10bit만 사용하게 됨.(물론 부호비트가 있다면 11bit를 사용한다고 보겠지만)

 

2. 그렇다면 2개의 숫자를 하나의 메모리 공간에 저장을 해서 모아둔 다음에 뒤에서부터 다시 채워나가면 되지 않을까?

 

1) 기존 저장 상태

1

2

3

4

5

6

7

8

9

10

↓

2) arr[i] = ( arr[i] << 10) + arr[i+n] 을 통해 하나의 메모리 공간에 2개의 수를 저장한다.

1,6

2,7

3,8

4,9

5,10

↓

3)맨 오른쪽 10bit가 y를 나타내므로 1111111111₍₂₎ 와 and 연산을 하면 b만 나타난다. 그다음 10bit는 x를 나타내므로 10bit만큼 right shift(>>)해주면 a가 나타난다. 이를 뒤에서부터 채운다.(해당 정보를 가지고 있는 것이 앞에 있으므로 뒤에서부터 채운다면 replace 되더라도 그 데이터는 이미 쓴 데이터이기 때문에 상관없게 된다.)

nums[2*(n-i)-1] = nums[n-i-1] & 1023;
nums[2*(n-i-1)] = nums[n-i-1] >> 10;

1,6

2,7

3,8

4,9

5,10

5

10

↓

1

6

2

7

3

8

4

9

5

10

 

=> 매우 쉬운 문제로 코딩테스트에서 나올 일이 없을 것 같은 문제이긴 하지만 만약에 나온다면 숫자의 범위와 메모리 크기를 보는 등 출제의도를 파악하는 것이 중요할 것 같다.

 

문제 링크

https://leetcode.com/problems/shuffle-the-array/

Shuffle the Array - LeetCode