알고리즘 연습 / 잃어버린 수열 찾기

예를 들어 3, 8, x, 18... 이 있을 때 빠진 등차 수열 x를 찾아서 반환해야한다.

초항은 3이다.

 

 

 

1. x의 등차 값을 찾는 방법은?

[0] [1] [2] 배열의 인덱스로 생각하면 [0] [1], [1] [2] 의 등차 값을 구해서 더하고 나누기 3을 해준다.

3과 8의 등차는 5.

8과 18의 등차는 10.

(5 + 7) / 3은? 5

let y;
for (let i = 1; i < num.length; i++){
	y += num[i] - num[i - 1]
	}
y /= num.length;

- y값에 배열의 인덱스를 하나씩 빼가면서 값을 더해준다.

ex) num[1] - num[0]

      num [2] - num[1]

- 더한 y의 값에 배열의 길이만큼 나누어서 공차를 구한다.

 

 

 

2. 빈 index 찾기

빈 index를 찾으려면 공차가 높은 인덱스를 찾아서 반환 시킨다.

--- 여기서 왜 인덱스를 반환 시킬까?

--- 인덱스를 반환시켜 이전 값을 구할 때 인덱스만큼 곱하기를 해주면 없어진 x값을 구할 수 있다.

let index = num[2] - num[1] > num[1] - num[0] ? 2 : 1;

2와 1사이의 공차가 크면 2를 반환 1과 0 사이의 공차가 크면 1을 반환하도록 한다.

 

 

 

3. 이전 값과 x의 값 구하기

x = num[0] + y * index;

ex) 3, 8, x, 18... 

1. y = 5

2. 18 - 8 > 8 - 3 = 2가 반환

3. x = 3 + 5 * 2 = 13

3, 8, 13, 18 을 찾을 수 있다.