[알고리즘/자바스크립트] 컵 돌리기 게임 (Find Key)

[문제] 세 개의 뒤집힌 컵 중 한 개의 컵 안에 열쇠가 있습니다.

당신이 열쇠를 찾기 위해 컵을 들어올리려는 순간, Drogon이 빠르게 컵의 위치를 뒤섞기 시작합니다.

컵의 교환이 끝났을 때, 열쇠가 들어있는 컵을 찾아야 합니다.

 

• 컵의 위치는 인덱스로 표현됩니다. (0부터 시작)
• 키가 들어있는 컵의 인덱스와 교환된 컵의 인덱스를 나타내는 배열(swaps)을 입력으로 받습니다. 
• 예를들어, 열쇠가 들어있는 컵의 처음 위치가 `0`이고 컵이 교환되는 순서가 다음과 같다면 [(0, 1), (1, 2), (1, 0)]
  1. 첫 교환때 열쇠가 있는 컵은 0 에서 1로 이동하게 됩니다.
  2. 두번째 교환때 열쇠가 있는 컵은 1 에서 2로 이동하게 됩니다.
  3. 마지막 교환때 1에 있는 컵이 0으로 가지만, 열쇠가 있는 컵에는 영향을 미치지 않습니다.
  4. 따라서 열쇠가 있는 컵의 위치는 2가 됩니다.
• 컵의 갯수는 최소한 두 개 이상입니다.

 

swaps = [[0, 1], [1, 2], [1, 0]]
firstPosition = 0
findKey(firstPosition, swaps) // == 2

 

---

 

 

먼저 컵의 위치가 배열을 iterate하면서 계속 변화하므로

그 변화하는 위치를 저장할 변수가 하나 필요하다.

나는 그 변수의 이름을 hasKey로 지었다.

 

이 문제를 풀었을 때, 처음에 잘못 생각했던 것은

컵의 위치가 무조건 왼쪽에서 오른쪽으로 간다고 생각했던것이다.

그래서 처음에 아래와 같이 풀었었다.

function findKey (start, swaps) {
	// Complete the findKey function.
	var hasKey = start;
	for(var i=0; i<swaps.length; i++) {
		for(var j=0; j<swaps[i].length; j++) {
			if(swaps[i][0] === hasKey) {
				hasKey = swaps[i][1];
			}
		}
	}
	return hasKey;
}

hasKey변수는 start위치를 초기값으로 가진다.

swaps[i][0]번째 키와 hasKey의 값이 같다면 hasKey값을 swaps[i][1]로 변경한다.

 

이 코드는 0->1, 1->2로 이동하는 것은 반영할 수 있을지 몰라도 

1->0, 2->1로 이동하는 것은 반영하지 못한다.

 

만약에 문제의 배열이 [[0, 1]], 초기 위치가 1이라고 주어진다면

1번째 컵에 키가 있었으나 0번째 컵과 위치를 교환했으므로

1이 아닌 0이 return되도록 코드를 바꿔주어야 한다.

 

 

function findKey (start, swaps) {
	// Complete the findKey function.
	var hasKey = start;
	for(var i=0; i<swaps.length; i++) {
		for(var j=0; j<swaps[i].length; j++) {
			if(swaps[i][j] === hasKey) {
				if(j === 1) {
					hasKey = swaps[i][0];
				} else {
					hasKey = swaps[i][1];
					break;
				}
			}
		}
	}
	return hasKey;
}

그래서 변경한 코드는 다음과 같다.

배열의 두 값 중 하나라도 현재 위치와 일치하는 값이 있다면

그 배열은 서로 위치를 교환해주어야 한다.

만약에 j가 1이라면 hasKey에는 swaps[i][0]을 넣어주고

j가 0이라면 반대로 hasKey에는 swaps[i][1]을 넣어준다.

여기서 중요한 것은 j가 0일 경우 hasKey에 swaps[i][1]을 할당한 후에

반드시 break문을 실행시켜주어야 한다는 점이다.

왜냐면 j===0일 때, 이미 key의 위치를 할당한 상태에서

j===1일 경우로 넘어가 한 번 더 반복문을 실행하면

hasKey값이 다시 초기값으로 원상복구되기 때문이다.

 

 

근데 여기까지 풀고 다시 찬찬히 생각해보니

내가 또 쓸데없이 복잡하게 풀었다는 사실을 깨닫게 되었다.ㅋㅋㅋ

그니까 이중배열이긴 한데 안쪽 배열의 값이 2개밖에 없기 때문에

굳이 2번 반복을 안돌려도 풀 수 있닼ㅋㅋ...

 

function findKey (start, swaps){
  // Complete the findKey function.
  var hasKey = start;
	for(var i=0; i<swaps.length; i++) {
		if(swaps[i][0] === hasKey) {
			hasKey = swaps[i][1];
		} else if(swaps[i][1] === hasKey) {
			hasKey = swaps[i][0];
		}
	}
	return hasKey;
}

바로 이렇게...

그니까 맨 위에 첫번째 코드에서 else if문만 추가했으면 해결되었을 문제였는데

열심히 삽질을 했다.^^...

 

 

아오 저번에 트리보나치 수열 구할 때도 이랬던거 같은데;

제발 간단하게 생각하는 연습을 하자ㅜㅜ...