프로그래머스 방문길이 자바 - peulogeulaemeoseu bangmungil-i jaba

더보기

더보기

게임 캐릭터를 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 이하의 자연수입니다.

□입출력 예

🌼 JAVA 알고리즘

□초기화면

□풀이과정

오늘은 풀이과정이 많이 길다.. 코드 바로보기 이용 추천!

각 좌표에 해당하는 점의 개수만큼의 배열을 생성해서
도착한 좌표의 값을 true로 바꾸어가며 새로 이동한 좌표인지, 전에 이동했던 좌표인지 확인하는 방법을 사용했다.
배열을 사용하기 때문에 (0,-1)처럼 마이너스 좌표는 사용할 수 없었고, 대신 출발좌표를 (0,0)이 아닌 (5,5)로 잡아주었다.

class Solution {
    public int solution(String dirs) {
        int answer = 0;
        //up, down, left, right
        int U = 5, D = 5;
        int L = 5, R = 5;
        
        boolean[][] map = new boolean[11][11];
        for(int i=0;i<dirs.length();i++){
            //좌표이동
            String path = Character.toString(dirs.charAt(i));
            switch(path){
                case "U" : U++; break;
                case "D" : D++; break;
                case "L" : L++; break;
                case "R" : R++; break;
            }
            System.out.println(path+"에서 "+(U-D)+","+(R-L));
            //범위 확인
            if(U-D>10||U-D<0||R-L>10||R-L<0) continue;
            //map 확인
            if(!map[U-D][R-L]){
                map[U-D][R-L] = true;
                answer++;
            } 
            System.out.println("-> "+answer);
            
        }
        
        
        
        
        return answer;
    }
}

아무래도 L(left),R(right),U(up),D(down)의 값을 서로 계산하며 배열의 인덱스를 맞추다 보니
실수가 나온것 같아 4개의 방향이 아닌, XY좌표로 계산하도록 바꾸었다.

class Solution {
    public int solution(String dirs) {
        int answer = 0;
        //up, down, left, right
        int X = 5,Y = 5;
        
        boolean[][] map = new boolean[11][11];
        for(int i=0;i<dirs.length();i++){
            //좌표이동
            String path = Character.toString(dirs.charAt(i));
            switch(path){
                case "U" : Y++; break;
                case "D" : Y--; break;
                case "L" : X--; break;
                case "R" : X++; break;
            }
            System.out.print(path+"에서 "+(X)+","+(Y));
            //범위 확인
            if(Y>10||Y<0||X>10||X<0){
                System.out.println();
               continue; 
            } 
            //map 확인
            if(!map[Y][X]){
                map[Y][X] = true;
                answer++;
            } 
            System.out.println("-> "+answer);
            
        }
        
        
        
        
        return answer+1;
    }
}

다행히 테스트케이스에서는 잘 작동했지만, 코드를 제출하니 반 이상의 결과가 실패였다.

위의 테스트케이스(특히 테스트2)의 출력문을 잘 살펴보면, 마지막 2개의 L에서는 answer의 값이 증가하지 않는 것이 맞지만
마지막 U에서의 좌표가(-2,7)로 나왔다. 이는 2개의 L이 answer의 값만 증가시키지 않았을 뿐 실제로 좌표를 이동시켰다는 것을 알 수 있다.

위의 출력문을 통해 지금 테스트코드는 거의 운으로...맞춘것임을 알았고 다시 분석에 들어갔다.

class Solution {
    public int solution(String dirs) {
        int answer = 0;
        //up, down, left, right
        int X = 5,Y = 5;
        
        boolean[][] map = new boolean[11][11];
        for(int i=0;i<dirs.length();i++){
            //좌표이동
            String path = Character.toString(dirs.charAt(i));
            switch(path){
                case "U" : Y++; break;
                case "D" : Y--; break;
                case "L" : X--; break;
                case "R" : X++; break;
            }
            System.out.print(path+"에서 "+(X)+","+(Y));
            //범위 확인
            if(Y>10){
                Y--;
                System.out.println();
                continue;
            } 
            if(Y<0){
                Y++;
                System.out.println();
                continue;
            }   
            if(X>10){
                X--;
                System.out.println();
                continue;
            } 
            if(X<0){
                X++;
                System.out.println();
                continue;
            } 
            //map 확인
            if(!map[Y][X]){
                map[Y][X] = true;
                answer++;
            } 
            System.out.println("-> "+answer);
            
        }
        
        
        
        
        return answer+1;
    }
}

이전 코드의 문제점이엇던 2개의 L(좌표의 한계를 넘어갔을 경우)과 마지막 U를 정상적으로 작동하도록 고쳤다.

하지만 테스트2에서 다른 점으로부터 이동했던 좌표를 현재좌표로부터 이동했던 좌표와 일치하게 인식해
answer값 1이 증가되지 않았기 때문에 기댓값과 다른 결과가 나왔다.

쉽게 말하면
위 그림의 빨간점으로 좌표가 이동했을 때, 빨간점의 좌표는 이미 첫번째 좌표이동에서 true값으로 변경되었기 때문에 지나왔던 경로로 인식된 것이다.

이를 해결하기 위해 flag를 생성해서 겹치는 점을 처음 지났을 경우 map[x][y]가 true이더라도 answer을 증가시키도록 했다.

class Solution {
    public int solution(String dirs) {
        int answer = 0;
        //up, down, left, right
        int X = 5,Y = 5;
        //겹치는 점 통과여부
        boolean flag = false;
        
        boolean[][] map = new boolean[11][11];
        for(int i=0;i<dirs.length();i++){
            //좌표이동
            String path = Character.toString(dirs.charAt(i));
            switch(path){
                case "U" : Y++; break;
                case "D" : Y--; break;
                case "L" : X--; break;
                case "R" : X++; break;
            }
            System.out.print(path+"에서 "+(X)+","+(Y));
            //범위 확인
            if(Y>10){
                Y--;
                System.out.println();
                continue;
            } 
            if(Y<0){
                Y++;
                System.out.println();
                continue;
            }   
            if(X>10){
                X--;
                System.out.println();
                continue;
            } 
            if(X<0){
                X++;
                System.out.println();
                continue;
            } 
            //map 확인
            if(!map[Y][X]){
                map[Y][X] = true;
                answer++;
            } 
            else if(!flag){
                flag = true;
                answer++;
            }
            System.out.println("-> "+answer);
            
        }
        
        
        
        
        return answer;
    }
}

계속해서 테스트2에 중점을 두고 코드를 조금씩 수정했다.

class Solution {
    public int solution(String dirs) {
        int answer = 0;
        //up, down, left, right
        int X = 5,Y = 5;
        //겹치는 점 통과여부
        boolean flag = false;
        
        boolean[][] map = new boolean[11][11];
        for(int i=0;i<dirs.length();i++){
            //좌표이동
            String path = Character.toString(dirs.charAt(i));
            switch(path){
                case "U" : Y++; break;
                case "D" : Y--; break;
                case "L" : X--; break;
                case "R" : X++; break;
            }
            System.out.print(path+"에서 "+(X)+","+(Y));
            //범위 확인
            if(Y>10){
                Y--;
                System.out.println();
                continue;
            } 
            if(Y<0){
                Y++;
                System.out.println();
                continue;
            }   
            if(X>10){
                X--;
                System.out.println();
                continue;
            } 
            if(X<0){
                X++;
                System.out.println();
                continue;
            } 
            //map 확인
            if(!map[Y][X]){
                map[Y][X] = true;
                answer++;
            } 
            else if(!flag) {
                flag = true;
                answer++;
            }
            System.out.println("-> "+answer);
            
        }
        
        
        
        
        return answer;
    }
}

드디어.....! 통과가 되나 했지만 제출 후 검사하기에서 대부분의 경우에 실패했다.
더이상 코드를 수정하기에는 이미 코드가 더럽고, 길어서 코테연습의 의미가 있나 싶었다.

결국 풀이방식을 완전히 바꾸어보기로 했다.

지금 코드의 가장 큰 문제는 출발좌표와 이동좌표가 제대로 check되지 않는다는 점이다.
왜일까?

위의 테스트3의 경우를 잘 보면 L -> R -> L 의 경로로 이동했을 경우 가는 방향을 true로 체크해야하지만
나는 점의 좌표에 따라 도착점을 true로 체크했기 때문에 여러 테스트케이스에서 정상적으로 작동하지 않았다.

따라서 점의 좌표가 아닌 "경로"를 check하는 방법을 떠올렸다.

이 문제에서 경로란 출발x,y값 -> 이동할 x,y값을 말한다.

출발좌표를 sX,sY, 이동좌표를 aX,aY라고 했을 때 경로는 "sX"+"sY"+"aX"+"aY"로 표시할 수 있다.
이 경로를 arraylist에 저장해서 새로운 경로가 나올때마다 중복된 경로가 있는지 검사하고, 없을 경우 갱신시키는 방법을 사용했다.

이때 파란 경로와 초록 경로는 일치해야 하기 때문에

왼쪽으로 이동     → 경로 : 출발좌표+이동좌표
오른쪽으로 이동  → 경로 : 이동좌표+출발좌표
위쪽으로 이동     → 경로 : 출발좌표+이동좌표
아래쪽으로 이동  → 경로 : 이동좌표+출발좌표

와 같은 기준을 세웠다.

class Solution {
    public int solution(String dirs) {
        int answer = 0;
        
        
        return answer;
    }
}

위에서 설명했던 대로 이동할 때마다 경로를 생성했다.

import java.util.ArrayList;
class Solution {
    public int solution(String dirs) {
        int answer = 0;
        ArrayList<String> route = new ArrayList<>();
        //출발좌표, 이동좌표
        int sX = 0, sY = 0, aX = 0, aY = 0;
        for(int i=0;i<dirs.length();i++){
            //좌표 갱신
            aX = sX;
            aY = sY;
            //경로
            String path = "";
            
            if(dirs.charAt(i)=='U'){ //출발좌표 먼저
                aY++;
                path = sX+""+sY+""+aX+""+aY; 
            } else if(dirs.charAt(i)=='D'){ //도착좌표 먼저
                aY--;
                path = aX+""+aY+""+sX+""+sY;         
            } else if(dirs.charAt(i)=='L'){ //출발좌표 먼저
                aX++;
                path = sX+""+sY+""+aX+""+aY;           
            } else { //도착좌표 먼저
                aX--;
                path = aX+""+aY+""+sX+""+sY;    
            }
            
            
            
        }
        
        
        return answer;
    }
}

위 코드에 도착(이동)좌표의 범위 체크를 더하면 될것이다.

확실히 배열을 사용하지 않다 보니 인덱스가 음수가 나오는것에 대해 고민할 필요가 없어 좋았다.
++ 더럽지 않은 코드!! 좋아 !! 우가우가

import java.util.ArrayList;
class Solution {
    public int solution(String dirs) {
        int answer = 0;
        ArrayList<String> route = new ArrayList<>();
        //출발좌표, 이동좌표
        int sX = 0, sY = 0, aX = 0, aY = 0;
        for(int i=0;i<dirs.length();i++){
            //도착좌표 초기화
            aX = sX;
            aY = sY;
            //경로
            String path = "";
            
            if(dirs.charAt(i)=='U'){ //출발좌표 먼저
                aY++;
                path = sX+""+sY+""+aX+""+aY; 
            } else if(dirs.charAt(i)=='D'){ //도착좌표 먼저
                aY--;
                path = aX+""+aY+""+sX+""+sY;         
            } else if(dirs.charAt(i)=='L'){ //출발좌표 먼저
                aX++;
                path = sX+""+sY+""+aX+""+aY;           
            } else { //도착좌표 먼저
                aX--;
                path = aX+""+aY+""+sX+""+sY;    
            }
            //좌표 체크
            if(aX<-5||aX>5||aY<-5||aY>5) continue;
            //경로가 존재하는지 체크 후 저장
            if(!route.contains(path)){
                route.add(path);
            }
        }
        answer = route.size();
        
        return answer;
    }
}

분명 문제해결 방법은 맞는듯 싶은데 값이 이상해서 봤더니 
반복할 때마다 출발좌표의 초기화는 했지만, 도착(이동)좌표로 이동하는 코드를 빼먹었다.
경로가 존재하는지 체크한 후 저장하는 코드 아래에 좌표이동 코드를 추가하면 완성이다.

□완성코드

import java.util.ArrayList;
class Solution {
    public int solution(String dirs) {
        int answer = 0;
        ArrayList<String> route = new ArrayList<>();
        //출발좌표, 이동좌표
        int sX = 0, sY = 0, aX = 0, aY = 0;
        for(int i=0;i<dirs.length();i++){
            //도착좌표 초기화
            aX = sX;
            aY = sY;
            //경로
            String path = "";
            
            if(dirs.charAt(i)=='U'){ //출발좌표 먼저
                aY++;
                path = sX+""+sY+""+aX+""+aY; 
            } else if(dirs.charAt(i)=='D'){ //도착좌표 먼저
                aY--;
                path = aX+""+aY+""+sX+""+sY;         
            } else if(dirs.charAt(i)=='L'){ //출발좌표 먼저
                aX++;
                path = sX+""+sY+""+aX+""+aY;           
            } else { //도착좌표 먼저
                aX--;
                path = aX+""+aY+""+sX+""+sY;    
            }
            //좌표 체크
            if(aX<-5||aX>5||aY<-5||aY>5) continue;
            //경로가 존재하는지 체크 후 저장
            if(!route.contains(path)){
                route.add(path);
            }
            //좌표 이동
            sX = aX;
            sY = aY;
        }
        answer = route.size();
        
        return answer;
    }
}

□링크

About Me

💻GitHub/KimSky904 KimSky904 - Overview Department of New Media Software. KimSky904 has 8 repositories available. Follow their code on GitHub. github.com

code-review.tistory.com

코딩테스트 연습 - 방문 길이

programmers.co.kr