[알고리즘/자바스크립트] 배열에서 반대 방향 제거하기 (Directions Reduction)

-해당 문제는 codewars사이트의 level5 문제입니다. (1~8단계 중 8단계가 가장 쉬운 레벨)-

[문제] Once upon a time, on a way through the old wild west,…
… a man was given directions to go from one point to another. The directions were "NORTH", "SOUTH", "WEST", "EAST". Clearly "NORTH" and "SOUTH" are opposite, "WEST" and "EAST" too. Going to one direction and coming back the opposite direction is a needless effort. Since this is the wild west, with dreadfull weather and not much water, it's important to save yourself some energy, otherwise you might die of thirst!

How I crossed the desert the smart way.
The directions given to the man are, for example, the following:

["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"].
or

{ "NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST" };
or (haskell)

[North, South, South, East, West, North, West]
You can immediatly see that going "NORTH" and then "SOUTH" is not reasonable, better stay to the same place! So the task is to give to the man a simplified version of the plan. A better plan in this case is simply:

["WEST"]
or

{ "WEST" }
or (haskell)

[West]
or (rust)

[WEST];
Other examples:
In ["NORTH", "SOUTH", "EAST", "WEST"], the direction "NORTH" + "SOUTH" is going north and coming back right away. What a waste of time! Better to do nothing.

The path becomes ["EAST", "WEST"], now "EAST" and "WEST" annihilate each other, therefore, the final result is [] (nil in Clojure).

In ["NORTH", "EAST", "WEST", "SOUTH", "WEST", "WEST"], "NORTH" and "SOUTH" are not directly opposite but they become directly opposite after the reduction of "EAST" and "WEST" so the whole path is reducible to ["WEST", "WEST"].

Task
Write a function dirReduc which will take an array of strings and returns an array of strings with the needless directions removed (W<->E or S<->N side by side).

The Haskell version takes a list of directions with data Direction = North | East | West | South. The Clojure version returns nil when the path is reduced to nothing. The Rust version takes a slice of enum Direction {NORTH, SOUTH, EAST, WEST}.

Examples
dirReduc(["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]) => ["WEST"]
dirReduc(["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH"]) => []

 

---

 

[해석] 아ㅏ 문제가 너무 구구절절 길어서 번역하기 귀찮으니 핵심만 얘기해보도록 하겠다.

서부 야생지대를 탐험하는 어떤 한 남자가 목적지까지 가는 방향을 배열로 쭉 나열했다고 하자. 

 

["북쪽", "남쪽", "남쪽", "동쪽", "서쪽", "북쪽", "서쪽"]

 

그런데 북쪽으로 갔다가 남쪽으로 다시 가는 건 매우 불필요하고 무의미한 일이다. 동쪽 갔다가 서쪽으로 다시 가는 것도 마찬가지.

 

그러므로 어떤 한 방향으로 갔다가 바로 다시 반대 방향으로 가게 되는 경우를 배열에서 모두 제거해보자.

 

["북쪽", "남쪽", "남쪽", "동쪽", "서쪽", "북쪽", "서쪽"]

-> ["남쪽", "동쪽", "서쪽", "북쪽", "서쪽"]

-> ["남쪽", "북쪽", "서쪽"]

-> ["서쪽"]

 

이렇게 지우고 나면 최종적으로 ['서쪽']만 남게 되는데 바로 이 알고리즘을 짜는 것이 미션이다.

 

 

---

 

 

항상 그렇듯이 무지하게 헤매다가 짠 코드는 이렇다.

function dirReduc(arr){
	for(var i=0; i<arr.length; i++) {
		if(arr[i]=='NORTH' && arr[i+1]=='SOUTH' || arr[i]=='SOUTH' && arr[i+1]=='NORTH'
		 || arr[i]=='EAST' && arr[i+1]=='WEST' || arr[i]=='WEST' && arr[i+1]=='EAST') {
			arr.splice(i, 2)
			i-=2
		}
	}
	return arr
}

일단 배열을 0번째부터 쭉 탐색하는데,

 

0번째 항목을 탐색할 때는 1번째 항목과 비교,

1번째 항목을 탐색할 때는 2번째 항목과 비교, ...

 

즉 i번째 항목을 탐색할 때 i+1번째 항목과 비교를 한다.

 

어떻게??

무식하게.

ㅋㅋㅋ

 

조건식에 구구절절 길~~~게 늘여쓴다.

 

솔직히 무식하긴 한데 젤 간단하다.ㅋ

 

i번째 항목이 'NORTH'이면서 i+1번째 항목이 'SOUTH'인 경우,

i번째 항목이 'SOUTH'이면서 i+1번째 항목이 'NORTH'인 경우,

i번째 항목이 'EAST'이면서 i+1번째 항목이 'WEST'인 경우,

i번째 항목이 'WEST'이면서 i+1번째 항목이 'EAST'인 경우

 

이걸 조건식에 다 써준다. (왼쪽 조건과 오른쪽 조건이 모두 만족해야 하므로 AND연산을 사용한다.)

 

그리고 저 조건식을 하나라도 만족하면 (4개 중 하나라도 만족하면 되니까 OR연산을 사용한다.)

배열에서 해당 항목과 바로 다음 항목을 삭제해준다.

그리고 i도 삭제한 개수: 2만큼 감소시켜준다.

 

 

 

 

근데 저 조건식에 기~일게 늘여쓴 조건식이 너무나 거슬리기 시작했다.

그래서 다른 방법을 곰곰히 생각해보았는데,

이런 방법이 떠올랐다.

 

NORTH와 SOUTH는 서로 반대 방향인데 이 2개가 합쳐졌을 때만 조건이 만족한다.

그럼 NORTH에 1, SOUTH에 -1을 부여하고 두 개의 합이 0일 때 조건이 만족하는 것으로 하면 어떨까?

 

function dirReduc(arr){
	var newArr = arr.map((x) => {
		if(x == 'NORTH') { return 1 }
		if(x == 'SOUTH') { return -1 }
		if(x == 'EAST') { return 2 }
		if(x == 'WEST') { return -2 }
	})

	for(var i=0; i<newArr.length; i++) {
		if(newArr[i]+newArr[i+1]===0) {
			newArr.splice(i, 2)
			i-=2
		}
	}
	return newArr.map((x) => {
		if(x == 1) { return 'NORTH' }
		if(x == -1) { return 'SOUTH' }
		if(x == 2) { return 'EAST' }
		if(x == -2) { return 'WEST' }
	})
}

 

그래서 생각한 코드는 위와 같다.

일단 배열을 NORTH -> 1, SOUTH -> -1, EAST -> 2, WEST -> -2

이렇게 치환해서 새로운 배열을 만들어준다.

아까와 같은 방법으로 for문을 돌린 후 i번째 요소와 i+1번째 요소의 합이 0이 되면 해당되는 항목들을 삭제한다.

그 배열을 다시 NORTH, SOUTH, EAST, WEST의 문자열로 바꿔서 리턴한다.

 

이 방법의 가장 큰 문제는 배열을 숫자로 바꾸고 다시 문자로 바꾸는 과정이 들어가서

연산 시간이 오래 걸린다는 점이다.

 

 

 

그래서 다른 더 좋은 방법을 찾아서

다른 사람들이 제출한 코드들을 구경하기 시작했는데 

거기서 매우 매우 기발한 코드를 발견했다.

캬.. 첨부터 이렇게 생각해서 짜는 사람들 존경한다.

 

function dirReduc(arr){
	var opposite = {
		'NORTH': 'SOUTH', 'SOUTH': 'NORTH', 'EAST': 'WEST', 'WEST': 'EAST'
	}

	return arr.reduce((av, cv, i, arr) => {
		if(opposite[av.slice(-1)] === cv) {
			av.pop()
		} else {
			av.push(cv)
		}
		return av
	}, [])
}

나는 정말 생각치도 못했던 신박한 방법!

객체를 이용하는 것이다.

JSON으로 { 'NORTH': 'SOUTH', 'SOUTH': 'NORTH', 'EAST': 'WEST', 'WEST': 'EAST' }

이렇게 데이터를 담아놓는다.

 

배열을 reduce() 함수로 돌려서 av에 값을 누적해서 새로운 배열을 만들어줄거다!

 

배열.slice() 함수를 사용할 때 안에 음수를 넣으면 뒤에서부터 자르게되는데

고로 배열.slice(-1)이라고 하면 배열 맨 마지막 요소를 가리키게된다.

 

그래서 opposite객체의 키값으로 배열 맨 마지막 요소를 넣고 그 값이

현재 reduce가 탐색하는 요소의 값과 같으면

(NORTH-SOUTH / SOUTH-NORTH / EAST-WEST / WEST-EASE) 이 조건을 만족한다는 얘기이니

배열에서 마지막 요소를 삭제한다.

 

반대로 값이 같지 않으면 배열에 현재 탐색 요소를 push한다.

 

 

정말 간단하면서도 너무 기발하다!

나도 한 번에 저렇게 생각해서 코드 짤 수 있을 때까지 공부해야겠다.

그런 날이 오긴 하려나ㅋㅋㅋ