프로그래머스 lv2 > 방문 길이 (자바/JAVA)

문제출처 : 

https://school.programmers.co.kr/learn/courses/30/lessons/49994

프로그래머스

 

 

문제설명 :

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

입출력 예

dirsanswer

"ULURRDLLU"	7
"LULLLLLLU"	7

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
문제의 예시와 같습니다.

 

 

 

 

---

 

1. 첫번째 코드 (정확성 35)

 

이동 전 좌표와 이동 후 좌표를 문자열로 만든 후

이동한 적 없는 길(way)일 때 걸어본 길로 체크하려고 했는데

돌려보니 정확성이 35로 나왔다..

 

일단 가장 큰 패착은 양방향으로 생각을 안 한 것

 

ex) 

(0,0) -> (1,0) 과 (1,0) -> (0,0) 은 같은 길을 의미하기 때문에 

양방향을 체크해줬어야 했다.

 

그리고 경로를 탐색할때 문자열로 하는 것은 시간이 오래걸리고,

--> 문자열에서 특정 서브스트링을 찾는 것은 **O(n)**의 시간

 

메모리 사용량과 연산 비용을 증가시킨다 

--> 문자열은 불변 객체이기 때문에 moved += way에서 계속 객체를 만들어야 함.

import java.util.*;
class Solution {
    public int solution(String dirs) {
        int answer = 0;
        String moved = "";
        
        //이동 전 현재 위치
        Loc currLoc = new Loc(0,0);
        
        for (int i = 0; i < dirs.length(); i++) {
            char dir = dirs.charAt(i);
            Loc moveLoc = move(dir, currLoc.getX(), currLoc.getY());
            
            if (checkRange(moveLoc)) { //이동 범위 유효여부 체크
                String curXY = currLoc.getXY();
                String moveXY = moveLoc.getXY();
                String way = curXY.concat(moveXY).concat("/");
                if (!moved.contains(way)) {
                    answer++;
                    moved += way;
                }
                currLoc = moveLoc;
            }
        }
        
     
        return answer;
    }
    
    public Loc move (char dir, int x, int y) {
        Loc loc =  new Loc(x,y);
        
        switch(dir) {
            case 'U' : 
                loc = new Loc(x,y+1);
                break;
            case 'D' : 
                loc = new Loc(x,y-1);
                break;
            case 'R' : 
                loc = new Loc(x+1,y);
                break;
            case 'L' : 
                loc = new Loc(x-1,y);
                break;
            default:
                break;
        }
        
        return loc;
        
    }
    
    public boolean checkRange(Loc loc) {
        int x = loc.getX();
        int y = loc.getY();
        if (x >= -5 && x <= 5 && y >= -5 && y <= 5) {
            return true;
        } 
        return false;
    }
}
class Loc {
    private int x;
    private int y;
    public Loc (int x, int y) {
        this.x = x;
        this.y = y;
    }
    public int getX() {
        return x;
    }
    public int getY() {
        return y;
    }
    public String getXY() {
        return String.valueOf(this.x) + "," + String.valueOf(this.y);
    }
}

 

 

 

 

 

 

 

 

2. 개선코드 (HashSet 사용)

 

문자열 대신 Set을 사용해 중복을 제거하고 탐색하는 데 용이하도록 수정하였다 (Set 시간복잡도 O(1))

import java.util.*;
class Solution {
    public int solution(String dirs) {
        int answer = 0;
        
        Set<String> moved = new HashSet<>();
        
        Loc currLoc = new Loc(0,0);
        
        for (int i = 0; i < dirs.length(); i++) {
            char dir = dirs.charAt(i);
            Loc moveLoc = move(dir, currLoc.getX(), currLoc.getY());
            
            if (checkRange(moveLoc)) { //이동 범위 xy체크
                String curXY = currLoc.getXY();
                String moveXY = moveLoc.getXY();
                // 경로를 양방향으로 저장 (예: 00->10과 10->00는 같은 경로로 처리)
                String way1 = curXY.concat(moveXY);
                String way2 = moveXY.concat(curXY);
                
                if (!moved.contains(way1) && !moved.contains(way2)) {
                    answer++;
                    moved.add(way1); // 경로를 Set에 추가
                    moved.add(way2); // 반대 방향도 추가
                }
                currLoc = moveLoc;
            }
            
        }
        
     
        return answer;
    }
    
    public Loc move (char dir, int x, int y) {
        Loc loc =  new Loc(x,y);
        
        switch(dir) {
            case 'U' : 
                loc = new Loc(x,y+1);
                break;
            case 'D' : 
                loc = new Loc(x,y-1);
                break;
            case 'R' : 
                loc = new Loc(x+1,y);
                break;
            case 'L' : 
                loc = new Loc(x-1,y);
                break;
            default:
                break;
        }
        
        return loc;
        
    }
    
    public boolean checkRange(Loc loc) {
        int x = loc.getX();
        int y = loc.getY();
        if (x >= -5 && x <= 5 && y >= -5 && y <= 5) {
            return true;
        } 
        return false;
    }
}
class Loc {
    private int x;
    private int y;
    public Loc (int x, int y) {
        this.x = x;
        this.y = y;
    }
    public int getX() {
        return x;
    }
    public int getY() {
        return y;
    }
    public String getXY() {
        return String.valueOf(this.x) + "," + String.valueOf(this.y);
    }
}