문제 소개
이번 글에서는 문자 하나하나로 구성된 배열 arr을 유일한 인자로 받아, 전체 이동의 최종 방향을 구하는 JavaScript 함수를 작성해 보겠습니다.
배열에는 다음 네 가지 문자만 포함될 수 있습니다.
- 'N' → 북쪽(North) 방향
- 'S' → 남쪽(South) 방향
- 'W' → 서쪽(West) 방향
- 'E' → 동쪽(East) 방향
각 문자는 해당 방향으로 단위 거리만큼 이동한다는 의미입니다. 그리고 배열 안에서 서로 반대되는 두 방향, 즉 ('S'와 'N') 또는 ('E'와 'W')가 만나면 서로의 이동을 상쇄합니다. 따라서 우리 함수는 배열 전체를 종합했을 때의 최종 이동 방향을 찾아내야 합니다.
입력 예시
예를 들어 함수에 다음과 같은 입력이 주어졌다고 가정해 봅시다.
const arr = ['N', 'S', 'S', 'E', 'W', 'N', 'W'];
그렇다면 기대하는 출력은 다음과 같습니다.
const output = 'W';
출력 설명
먼저 첫 번째 'N'과 'S'가 서로 상쇄되고, 이어서 'E'와 'W'도 상쇄됩니다. 마지막으로 남아 있던 'N'과 'S' 역시 서로 상쇄되면서 결국 'W' 하나만 남게 됩니다.
풀이 코드
다음은 위 문제를 해결하는 코드입니다.
const arr = ['N', 'S', 'S', 'E', 'W', 'N', 'W'];
const cancelDirections = (arr = []) => {
let str = arr.join('');
while(str.includes('NS') || str.includes('SN') || str.includes('EW')
|| str.includes('WE')){
str = str.replace('NS', '');
str = str.replace('SN', '');
str = str.replace('EW', '');
str = str.replace('WE', '');
};
return str.split('');
};
console.log(cancelDirections(arr));코드 동작 원리
arr.join('')으로 배열을 하나의 문자열로 합칩니다.while루프를 돌며 반대 방향 쌍('NS', 'SN', 'EW', 'WE')이 존재하는 한 계속해서 제거합니다. 제거 과정에서 새로운 반대 쌍이 인접하게 될 수 있으므로, 더 이상 없을 때까지 반복하는 것이 핵심입니다.- 모든 상쇄가 끝난 뒤
split('')으로 다시 배열 형태로 변환해 반환합니다.
실행 결과
콘솔 출력 결과는 다음과 같습니다.
['W']
더 효율적인 대안: 좌표 누적 방식
위 방식은 문자열을 반복적으로 검색하고 치환하기 때문에 배열이 길어질수록 성능이 저하될 수 있습니다. 이동은 순서와 무관하게 벡터의 합으로 표현할 수 있으므로, 각 방향의 개수를 좌표처럼 누적하면 단 한 번의 순회로 정답을 구할 수 있습니다.
const findFinalDirection = (arr = []) => {
let x = 0, y = 0;
for (const dir of arr) {
if (dir === 'N') y++;
else if (dir === 'S') y--;
else if (dir === 'E') x++;
else if (dir === 'W') x--;
}
let result = '';
if (y > 0) result += 'N';
if (y < 0) result += 'S';
if (x > 0) result += 'E';
if (x < 0) result += 'W';
return result.split('');
};
console.log(findFinalDirection(arr)); // ['W']이 방법은 시간 복잡도 O(n)으로 배열을 딱 한 번만 순회하므로, 입력 크기가 클 때 특히 유용합니다. 상쇄 로직을 직접 구현하지 않고도 동일한 최종 방향을 얻을 수 있다는 점이 장점입니다.