문제설명
각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다.
- 빛이 "S"가 써진 칸에 도달한 경우, 직진합니다.
- 빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다.
- 빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다.
- 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다.
당신은 이 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의 길이가 얼마인지 알고 싶습니다. 경로 사이클이란, 빛이 이동하는 순환 경로를 의미합니다.
예를 들어, 다음 그림은 격자 ["SL","LR"]에서 1행 1열에서 2행 1열 방향으로 빛을 쏠 경우, 해당 빛이 이동하는 경로 사이클을 표현한 것입니다.
이 격자에는 길이가 16인 사이클 1개가 있으며, 다른 사이클은 존재하지 않습니다.
격자의 정보를 나타내는 1차원 문자열 배열 grid가 매개변수로 주어집니다. 주어진 격자를 통해 만들어지는 빛의 경로 사이클의 모든 길이들을 배열에 담아 오름차순으로 정렬하여 return 하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤
grid의 길이 ≤ 500- 1 ≤
grid의 각 문자열의 길이 ≤ 500 grid의 모든 문자열의 길이는 서로 같습니다.grid의 모든 문자열은'L', 'R', 'S'로 이루어져 있습니다.
- 1 ≤
입출력 예
| grid | result |
|---|---|
["SL","LR"] |
[16] |
["S"] |
[1,1,1,1] |
["R","R"] |
[4,4] |
입출력 예 설명
입출력 예 #1
- 문제 예시와 같습니다.
- 길이가 16인 사이클이 하나 존재하므로(다른 사이클은 없습니다.),
[16]을 return 해야 합니다.
입출력 예 #2
- 주어진 격자를 통해 만들 수 있는 사이클들은 다음 그림과 같습니다.
- 4개의 사이클의 길이가 모두 1이므로,
[1,1,1,1]을 return 해야 합니다.
입출력 예 #3
- 주어진 격자를 통해 만들 수 있는 사이클들은 다음 그림과 같습니다.
- 2개의 사이클의 길이가 모두 4이므로,
[4,4]를 return 해야 합니다.
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
설계 과정
이번 문제는 우선 배열을 아래와 같이 정의한다.
[x,y,방향]
여기서 방향은 내가 어디로 움직있는지 상하좌우
인덱스 0 => 우, 1 => 상, 2=> 좌 3 => 하 로 정의
- 여기서 추가적으로 보면 좌회전 하면 저 인덱스를 +1로 바꿔주면 된다.
원래는 우측으로 가고 있는데 좌회전이라면 인덱스 +1 에 해당하는 상이 된다.
우회전에 경우는 -1을 해주면 된다.- 위의 찾은 규칙을 통해서 아래와 같이 규현
- coorFun(좌표) 함수 생성 => 이 함수는 현재 좌표를 넣어주면 방향을 알아서 틀어줌과 통시에 그 뱡향으로 한칸 이동한 좌표를 리턴하는 함수이다.
- visitArr 생성
=> 이는 3차원 배열로 x,y,방향으로 3차원으로 만들어주면서 기본값은 false로 해준다. (true라면 방문한것으로 정의)- 이제 순환을 해줄껀데 총 3중 for문을 써야한다.
-> x,y,방향 => ex) 2,3,1 => x=2,y=3,방향=오른쪽으로 움직임.
3중 for문의 값을 var current = [dx,dy,dirIndex] 로 받고 아래 과정 시행
1) 만약 그 값이 visitArr에 true라면 pass -> 건너뜀
2) 아니라면 방문한 것을 만날때까지 아래 반복
우선 그 x,y,방향에 해당하는 visitArr에 값을 true로 바꾼다.
그 값을 plusArr 에 따로 모아둔다.
그 후에, 위에 만든 함수를 이용하여 좌표를 이동한다.
3) 이렇게 해서 나온 plusArr의 length를 answer에 추가해준다.- 마지막에는 answer을 오름차순 정렬해서 리턴한다.
정답 코드
function solution(grid) {
var answer = [];
//0 => 우측으로 이동, 1=>위로 이동, 2=> 좌측으르 이동, 3=> 아래로 이동
var dirIndex = 0;
grid = grid.map((element)=>{
return element.split("");
})
var xLen = grid[0].length;
var yLen = grid.length;
//함수에 현재 위치 좌표를 주면 그 다음 좌표를 리턴
// 방향을 틀고 글로 이동한다.
// ex) current = [0,0]
function coorFun(current){
// 방향을 트는 과정
if(grid[current[1]][current[0]]==="S"){
}
else if(grid[current[1]][current[0]]==="L"){
// L에 걸리면 index 를 +1 해준다. 단, 3을 넘어가면 0으로 초기화
dirIndex = dirIndex>=3? 0:dirIndex+1;
current[2] = dirIndex;
}
else if(grid[current[1]][current[0]]==="R"){
dirIndex = dirIndex<=0? 3:dirIndex-1;
current[2] = dirIndex;
}
// dirIndex ===0 => 우측으로 이동
if(dirIndex === 0){
//x좌표에 1 증가
current[0] = current[0] >= xLen -1 ? 0 : current[0]+1;
}
// 위로 이동
else if(dirIndex===1){
current[1] = current[1] >= yLen -1 ? 0 : current[1]+1;
}
// 좌측으로 이동
else if(dirIndex===2){
//x좌표에 1 감소
current[0] = current[0] <=0 ? xLen - 1 : current[0]-1;
}
// 아래로 이동
else if(dirIndex===3){
//y좌표에 1 감소
current[1] = current[1] <=0 ? yLen - 1 : current[1]-1;
}
return current;
}
var visitArr = Array.from(Array(yLen), () => Array.from(Array(xLen), () => Array(4).fill(false)));
for(var dx = 0; dx<xLen;dx++){
for(var dy = 0; dy<yLen;dy++){
for(var i =0;i<4;i++){
dirIndex = i;
var plusArr = [];
// 0,0, 방향
var current = [dx,dy,dirIndex];
if(visitArr[current[1]][current[0]][current[2]]){
continue;
}
while(!visitArr[current[1]][current[0]][current[2]]){
visitArr[current[1]][current[0]][current[2]] = true;
plusArr.push([...current]);
current = coorFun([...current]);
}
plusArr.forEach((element)=>{
visitArr[element[1]][element[0]][element[2]] = true;
})
answer.push(plusArr.length);
}
}
}
return answer.sort((a,b)=>a-b);
}결과
집돌이 FE개발자의 노트