[프로그래머스] 공원 산책

Algorithm/Programmers

[프로그래머스] 공원 산책

벨코즈

|2024. 6. 16. 05:22

728x90

🔗 공원 산책

로봇 강아지가 공원 내 이동한 최종 위치를 계산하는 문제이다.

🥊 접근 방법 🥊

단순 구현 문제이다. 주의할 점은 이동 조건이 맞지 않을 경우, 시작위치인 S로 이동하는 것이 아니라 바로 전 위치로 되돌아가야 한다. 이거때매 30점 맞고 한참을 고민했다 ㅜ

✨ 방법 1 ✨ (2024-07-08)

0. 준비

currPos : x, y의 현재좌표를 담을 Point 객체 타입의 변수
originX : 이동하기 전의 X 좌표
originY : 이동하기 전의 Y 좌표
cnt : 이동 횟수를 체크하기 위한 변수

x, y 좌표는 계속 사용되기 때문에 객체로 생성했다.

static Point currPos;
static int originX;
static int originY;
static int cnt;

static class Point {
    int x;
    int y;
    
    public Point (int x, int y){
        this.x = x;
        this.y = y;
    }
}

1. 출발 지점 찾기

park 배열을 순회하며 출발지점인 'S'를 찾는다. 출발 지점의 좌표를 'originX', 'originY'에 저장하고, 'currPos'라는 객체를 만들어 현재 위치를 저장한다.

public void FindStartPoint(String[] park, String[] routes, int x, int y){
    for(int i=0; i<park.length; i++){
        for(int j=0; j<park[i].length(); j++){
            if(park[i].charAt(j) == 'S'){  // 출발 지점이면
                originX = i;  // x좌표 저장
                originY = j;  // y좌표 저장
                currPos = new Point(originX, originY);  // 현재 위치 저장
            }
        }
    }
}

2. 이동하기

opt : 이동할 방향 (routes의 첫 번째 인덱스에 위치한 문자)
num : 이동할 칸의 수 (routes의 세 번째 인덱스에 위치한 숫자)

routes의 배열을 순회하며 명령을 처리한다. 각 명령은 방향과 이동할 칸의 수로 구성되며, 명령어대로 로봇 강아지를 이동하면서 'checkRange' 메서드를 사용해 범위 내 이동인지, 장애물('X')이 있는지 체크한다. 이동이 불가하다면 현재 위치를 원래 위치로 되돌린다.

이 문제는 분기처리가 확실하고 일반적으로 ✅ if-else문보다 switch가 더 효율적이기 때문에 if문 대신 switch문으로 구현했다.

public void MovingRoutesDirection(String[] park, String[] routes){
    // routes 배열을 순회하며 명령 처리
    for(int i=0; i<routes.length; i++){
        char opt = routes[i].charAt(0);
        int num = routes[i].charAt(2) - '0';
        
        cnt = -1;
        // 명령어대로 이동
        switch(opt) {
            case 'N' :{
                while(checkRange(park, routes, num) && cnt < num){
                    currPos.x -= 1;
                }
                
                if(cnt != num) currPos.x = originX;  // 실제로 이동한 횟수와 이동해야하는 횟수가 같지 않을 경우 이동하기 전 위치로 빠꾸시킨다.
                originX = currPos.x;  // 현재 좌표 업데이트
                break;
            }
            
            // 중략
            
        }
    }
}

3. 범위 체크

현재 위치가 공원 범위 내에 있는지, 장애물('X')이 없는지 확인한다. 이동이 가능하면 cnt를 증가시키고 이동을 계속한다. 이동이 불가하다면 false를 반환해 이동을 중단한다.

public boolean checkRange(String[] park, String[] routes, int num) {
    if(currPos.x>=0 && currPos.x<park.length && currPos.y>=0 && currPos.y<park[0].length() && park[currPos.x].charAt(currPos.y) != 'X'){
        cnt++;
        return true;
    } return false;
 }

✨ 전체코드 ✨

park : 공원을 나타내는 문자열 배열
routes : 로봇 강아지가 수행할 명령이 담긴 문자열 배열

class Solution {
    
    static Point currPos;
    static int originX;
    static int originY;
    static int cnt;
    
    static class Point {
        int x;
        int y;
        
        public Point (int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    
    
    public int[] solution(String[] park, String[] routes) {
        int[] answer = new int[2];
        FindStartPoint(park, routes, 0, 0);
        MovingRoutesDirection(park, routes);

        answer[0] = currPos.x;
        answer[1] = currPos.y;
        return answer;
    }
    
    
    // 1 출발 지점 찾기
    public void FindStartPoint(String[] park, String[] routes, int x, int y){
        for(int i=0; i<park.length; i++){
            for(int j=0; j<park[i].length(); j++){
                if(park[i].charAt(j) == 'S'){
                    originX = i;
                    originY = j;
                    currPos = new Point(originX, originY);
                }
            }
        }
    }


    // 2 이동하기
    public void MovingRoutesDirection(String[] park, String[] routes){
        for(int i=0; i<routes.length; i++){
            char opt = routes[i].charAt(0);
            int num = routes[i].charAt(2) - '0';
            
            cnt = -1;
            switch(opt) {
                case 'N' :{
                    while(checkRange(park, routes, num) && cnt < num){
                        currPos.x -= 1;
                    }
                    
                    if(cnt != num) currPos.x = originX;
                    originX = currPos.x;
                    break;
                }
                
                case 'S' :{
                    while(checkRange(park, routes, num) && cnt < num){
                        currPos.x += 1;
                    }
                    
                    if(cnt != num) currPos.x = originX;
                    originX = currPos.x;
                    break;
                }
                    
                case 'W' : {
                    while(checkRange(park, routes, num) && cnt < num){
                        currPos.y -= 1;
                    }
                    
                    if(cnt != num) currPos.y = originY;
                    originY = currPos.y;
                    break;
                }
                    
                case 'E' : {
                    while(checkRange(park, routes, num) && cnt < num){
                        currPos.y += 1;
                    }
                    
                    if(cnt != num) currPos.y = originY;
                    originY = currPos.y;
                    break;
                }
            }
        }
    }
    
    // 3 범위체크
    public boolean checkRange(String[] park, String[] routes, int num) {
        if(currPos.x>=0 && currPos.x<park.length && currPos.y>=0 && currPos.y<park[0].length() && park[currPos.x].charAt(currPos.y) != 'X'){
            cnt++;
            return true;
        } return false;
    }
}

🌀 성능

메모리 : 73.6 MB
시간 : 0.27 ms

역시 시뮬 코드는 main 함수에 다 때려박는것보다 각 기능마다 메서드별로 구현하는게 가독성과 디버깅 측면에서 더 좋은 것 같다. 앞으로 습관화해야지🥺 그리고 MovingRoutesDirection에서 중복되는 코드가 많아 맘에 들진 않는데 다음에 다시 풀어봐야겠다.

다른 풀이를 참고하여 다시 풀었다.

🌟 방법 2 🌟 (2024-08-26)

1. 출발 지점 찾기

공연 배열을 순회하며 시작 지점인 'S'를 찾는다. 방법1의 구현방법만 다르고 로직은 똑같다. 다만, 'S'의 위치를 찾으면 바로 탐색을 종료하도록 return을 추가했다.

public void FindStartPoint(String[] park) {
    for(int i=0; i<park.length; i++){
        if(park[i].contains("S")){
            startX = i;
            startY = park[i].indexOf("S");
            return;
        }
    }
}

2. 명령 수행하기

routes 배열을 순회하며 명령을 처리한다. 이동하기 전에 MovingRoutesDirection 메서드를 호출해 이동이 가능한지 검사한다. 이동이 불가하면 명령을 수행하기 전의 위치로 되돌리고, 이동이 가능하면 새로운 위치로 업데이트한다.

for(String route : routes){
    String dir = route.split(" ")[0];
    int move = Integer.parseInt(route.split(" ")[1]);
    
    moveX = startX;
    moveY = startY;
    
    if(!MovingRoutesDirection(park, dir, move)){
        moveX = startX;
        moveY = startY;
    } else {
        startX = moveX;
        startY = moveY;
    }
}

3. 이동하기

이동하면서 CheckRange 메서드를 통해 이동이 가능한지 검사한다. 이동할 수 없다면 이동을 취소하고 원래 위치로 되돌아가기 위해 false를 반환한다.

public boolean MovingRoutesDirection(String[] park, String dir, int move){
    for(int i=0; i<move; i++){
        switch(dir){
            case "N": moveX--; break;
            case "S": moveX++; break;
            case "W": moveY--; break;
            case "E": moveY++; break;
        }
        
        if(!CheckRange(park)) return false;
    } return true;
}

4. 범위 체크

현재 위치가 고원의 범위를 벗어나지 않았는지, 이동하려는 위치에 장애물이 없는지 검사한다. 모든 조건을 만족해야 true를 반환한다.

public boolean CheckRange(String[] park){
    return (moveX >= 0 && moveX < park.length && moveY >= 0 && moveY < park[0].length() && park[moveX].charAt(moveY) != 'X');
}

🌟 전체코드 🌟

park : 공원을 나타내는 문자열 배열
routes : 로봇 강아지가 수행할 명령이 담긴 문자열 배열

class Solution {
    
    static int startX = 0;
    static int startY = 0;
    static int moveX = 0;
    static int moveY = 0;
    
    public int[] solution(String[] park, String[] routes) {
        
        FindStartPoint(park);
        
        // 2. 명령 수행하기
        for(String route : routes){
            String dir = route.split(" ")[0];
            int move = Integer.parseInt(route.split(" ")[1]);
            
            moveX = startX;
            moveY = startY;
            
            if(!MovingRoutesDirection(park, dir, move)){
                moveX = startX;
                moveY = startY;
            } else {
                startX = moveX;
                startY = moveY;
            }
        } return new int[] {startX, startY};
    }
    
    
    // 1. 출발 지점 찾기
    public void FindStartPoint(String[] park) {
        for(int i=0; i<park.length; i++){
            if(park[i].contains("S")){
                startX = i;
                startY = park[i].indexOf("S");
                return;
            }
        }
    }
    
    // 3. 이동하기
    public boolean MovingRoutesDirection(String[] park, String dir, int move){
        for(int i=0; i<move; i++){
            switch(dir){
                case "N": moveX--; break;
                case "S": moveX++; break;
                case "W": moveY--; break;
                case "E": moveY++; break;
            }
            
            if(!CheckRange(park)) return false;
        } return true;
    }
    
    // 4. 범위체크
    public boolean CheckRange(String[] park){
        return (moveX >= 0 && moveX < park.length && moveY >= 0 && moveY < park[0].length() && park[moveX].charAt(moveY) != 'X');
    }
}

🌀 성능

메모리 : 75.8 MB
시간 : 3.03 ms

전역변수로 선언해놓고 지역변수로 또 선언해서 헤맸다 ... 바보같은 실수 멈춰 .. 😓 의문인 점은, 방법1과 방법2의 시간이 10배나 차이가 난다는 것이다. 불필요하게 반복되는 코드도 없고 반복문의 개수도 줄였기 때문에 방법2가 조금이라도 시간이 더 단축될 것이라고 생각했는데 아니었다. 왜지 ?

저작자표시 비영리 변경금지

'Algorithm > Programmers' 카테고리의 다른 글

[프로그래머스] 요격 시스템 (0)	2024.06.21
[프로그래머스] 바탕화면 정리 (0)	2024.06.21
[프로그래머스] 타겟 넘버 (0)	2024.06.09
[프로그래머스] 추억 점수 (0)	2024.05.24
[프로그래머스] 달리기 경주 (0)	2024.05.23

방문자수