문제 설명
게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.
- U: 위쪽으로 한 칸 가기
- D: 아래쪽으로 한 칸 가기
- R: 오른쪽으로 한 칸 가기
- L: 왼쪽으로 한 칸 가기
캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.
예를 들어, "ULURRDLLU"로 명령했다면
-
1번 명령어부터 7번 명령어까지 다음과 같이 움직입니다.
-
8번 명령어부터 9번 명령어까지 다음과 같이 움직입니다.
이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다. 예를 들어 위의 예시에서 게임 캐릭터가 움직인 길이는 9이지만, 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다. (8, 9번 명령어에서 움직인 길은 2, 3번 명령어에서 이미 거쳐 간 길입니다)
단, 좌표평면의 경계를 넘어가는 명령어는 무시합니다.
예를 들어, "LULLLLLLU"로 명령했다면
- 1번 명령어부터 6번 명령어대로 움직인 후, 7, 8번 명령어는 무시합니다. 다시 9번 명령어대로 움직입니다.
이때 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다.
명령어가 매개변수 dirs로 주어질 때, 게임 캐릭터가 처음 걸어본 길의 길이를 구하여 return 하는 solution 함수를 완성해 주세요.
제한사항
- dirs는 string형으로 주어지며, 'U', 'D', 'R', 'L' 이외에 문자는 주어지지 않습니다.
- dirs의 길이는 500 이하의 자연수입니다.
입출력 예
| dirs | answer |
|---|---|
| "ULURRDLLU" | 7 |
| "LULLLLLLU" | 7 |
풀이 과정
나는 좌표평면의 각 점을 인덱싱해서 풀었다.
만일 좌표평면의 너비, 높이가 4라고 했을 경우 점들을 인덱싱하면 다음과 같다.
이렇게 인덱싱을 해놓은 다음에는 캐릭터가 이동한 경로의 중복 여부를 확인해줘야 한다.
나는 중복 여부를 확인하기 위해서 객체를 사용했다.
중복 여부 확인 과정
- [이동하기 전 X, 이동하기 전 Y], [이동한 뒤 X, 이동한 뒤 Y]를 문자열로 변환한 뒤에 다시 숫자로 변환한다.
- 숫자로 변환한 값들의 크기를 비교해 최댓값, 최솟값을 구한다.
- 객체에 최솟값 key가 있는지 확인한다. (value는 배열 형태)
- key가 있으면 최댓값이 value 배열에 있는지 확인한다.
- 배열에 없으면 최댓값을 배열에 넣어주고 처음 걸어본 길의 길이를 증가시킨다.
- 최솟값 key가 없으면 최솟값을 key, value를 [최댓값]으로 지정해서 객체에 저장하고 길의 길이를 증가시킨다.
좌표의 최솟값을 key로 지정해야
(2, 5) -> (3, 5), (3, 5) -> (2, 5)가 같은 길인 것으로 판단할 수 있다.
이것보다 더 좋은 방법이 있겠지만 나는 이 방법밖에 생각이 안 나서 이렇게 짰다..!
** 그리고 좌표를 이동하면서 이동한 좌표가 좌표 평면의 경계 내부에 있는지 확인해줘야 한다.
이 논리를 코드로 구현한 결과는 다음과 같다.
const solution = (dirs) => {
// 상하좌우 이동하는데 사용할 변수들 담은 배열
const direction = [[-1, 0], [0, 1], [1, 0], [0, -1]];
// `시작x시작y`, `끝x끝y`를 각각 숫자로 변환한 뒤
// "최소값"을 key로 지정, "최댓값"을 value로 넣는데
// 배열 형태로 넣음
const visited = {};
const dirsLength = dirs.length;
// 처음 시작 위치는 (0, 0) => (5, 5) 로 수정
let previousLocation = [5, 5];
let answer = 0;
// 현재 좌표가 좌표평면 경계 내에 있는지 확인
const isCorrect = (currentLocation) => {
const [currentX, currentY] = currentLocation;
return !(currentX < 0 || currentX > 10 || currentY < 0 || currentY > 10);
}
// 이전 좌표에서 상하좌우로 이동했을 때의 현재 좌표를 얻는 함수
const getCurrentLocation = (previousLocation, dir) => {
const [previousX, previousY] = previousLocation;
let currentX, currentY;
if(dir === "U") {
currentX = previousX + direction[0][0];
currentY = previousY + direction[0][1];
}
else if(dir === "R") {
currentX = previousX + direction[1][0];
currentY = previousY + direction[1][1];
}
else if(dir === "D") {
currentX = previousX + direction[2][0];
currentY = previousY + direction[2][1];
}
else {
currentX = previousX + direction[3][0];
currentY = previousY + direction[3][1];
}
return [currentX, currentY]
}
for(let i = 0; i < dirsLength; i++) {
// 현재 좌표
const currentLocation = getCurrentLocation(previousLocation, dirs[i]);
// 이전 좌표를 문자열로 변경하고 그걸 또 숫자로 변환함
const preivousLocationJoinNum = parseInt(previousLocation.join(""));
// 현재 좌표를 숫자로 변환한 값, 좌표 최대, 최소값
let currentLocationJoinNum, maxJoinNum, minJoinNum;
// 현재 좌표가 좌표 경계를 벗어난다면 continue
if(!isCorrect(currentLocation)) {
continue;
}
currentLocationJoinNum = parseInt(currentLocation.join(""));
maxJoinNum = Math.max(preivousLocationJoinNum, currentLocationJoinNum);
minJoinNum = Math.min(preivousLocationJoinNum, currentLocationJoinNum);
// visited의 key는 이전 좌표, 현재 좌표의 최소값
// minJoinNum이 이미 key로 등록되어 있을 경우
if(visited.hasOwnProperty(minJoinNum)) {
// 아직 이전좌표 - 현재좌표 길을 캐릭터가 걷지 않았다면
if(visited[minJoinNum].indexOf(maxJoinNum) === -1) {
// maxJoinNum을 추가
visited[minJoinNum].push(maxJoinNum);
answer++;
}
} // minJoinNum과 연결된 길을 처음 걸어본다면
else {
// maxJoinNum을 배열 형태로 넣어줌
visited[minJoinNum] = [maxJoinNum];
answer++;
}
// 이전 좌표는 현재 좌표로 갱신
previousLocation = currentLocation
}
return answer;
}실행 결과
0개의 댓글
