[Programmers] 공원 산책 - Java

문제

프로그래머스

 

풀이

기존 풀이

이 문제는 로봇 강아지가 산책을 하는데, 방향과 거리에 대한 정보로 이동을 시켜서 최종 로봇 강아지의 좌표를 구하는 문제이다.

 

1. 방향 문자열에 대한 인덱스를 Map을 사용한다.

Map을 사용하면 String에 대한 Integer값을 저장할 수 있어서 용이했고,

String값(방향 문자열)에 대한 인덱스를 찾는데 O(1)연산이 걸려서 사용했다.

 

2. 2차원 String 배열 map을 만들고, 로봇 강아지의 시작점(sx, sy)을 기록한다.

 

3. String의 split 메소드를 사용해서 방향과 거리에 대한 값을 가져온다.

 

4. 좌표를 움직여서, 장애물을 만나지 않고, 지도 밖으로 나가지 않는다면, 로봇 강아지를 이동시킨다.

 

5. 로봇 강아지의 좌표를 배열로 리턴한다.

 

소스코드

import java.util.HashMap;

class Solution {
    static HashMap<String, Integer> dirIdxMap;
    
    static final int[] dx = {-1, 1, 0, 0};
    static final int[] dy = {0, 0, -1, 1};
    
    public int[] solution(String[] park, String[] routes) {
        int sx = -1;
        int sy = -1;
        
        int n = park.length;
        int m = park[0].length();
        
        String[][] map = new String[n][m];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = String.valueOf(park[i].charAt(j));    
                
                if (map[i][j].equals("S")) {
                    sx = i;
                    sy = j;
                }
            }
        }
        
        dirIdxMap = new HashMap<>();
        
        dirIdxMap.put("N", 0);
        dirIdxMap.put("S", 1);
        dirIdxMap.put("W", 2);
        dirIdxMap.put("E", 3);
        
        for (String routeInfo : routes) {
            String[] s = routeInfo.split(" ");
            
            String dir = s[0];
            int moveCnt = Integer.parseInt(s[1]);
            
            int mx = sx;
            int my = sy;
            int cnt = moveCnt;
            int dirIdx = dirIdxMap.get(dir);
            
            boolean isMove = true;
            
            while (cnt > 0) {
                mx += dx[dirIdx];
                my += dy[dirIdx];
                
                if (mx < 0 || mx >= n || my < 0 || my >= m || map[mx][my].equals("X")) {
                    isMove = false;
                    break;
                }
                
                cnt--;
            }
            
            if (isMove) {
                sx += (moveCnt * dx[dirIdx]);
                sy += (moveCnt * dy[dirIdx]);
            }
        }
        
        return new int[] {sx, sy};
    }
}

 

성능 개선

1. 코드를 보면, String에 있는 값을 빼서, char로 변환하고 다시 String으로 만드는 작업이 필요없다.

2. 기존 park 배열로, map 2차원 배열처럼 사용할 수 있다.

map[i][j] = String.valueOf(park[i].charAt(j));

 

3. 방향 문자열에 대한 인덱스를 찾는 작업을 HashMap을 사용했는데, 해시를 계산해서 그 key값을 접근하는게 시간적으로 더 손해가 있을 수 있다는 생각이 들어서 if-else문이나 switch 문을 사용해서 바로 인덱스를 구하는 연산을 비교해보고 싶었다.

switch (cmd[0].charAt(0)) {
    case 'N': dir = 0; break;
    case 'S': dir = 1; break;
    case 'W': dir = 2; break;
    case 'E': dir = 3; break;
}

 

4. static 영역은 컴파일이 되기 이전에, 값이 이미 할당 되어 있는데, 전역으로 사용하지 않는 배열이라고 생각해, 메소드 내부에 배열로 선언했다.

 

소스코드

class Solution {
    public int[] solution(String[] park, String[] routes) {
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        int n = park.length;
        int m = park[0].length();

        int x = 0;
        int y = 0;
        
        for (int i = 0; i < n; i++) {
            int idx = park[i].indexOf('S');
            if (idx != -1) {
                x = i;
                y = idx;
                break;
            }
        }

        for (String route : routes) {
            String[] cmd = route.split(" ");
            int dir = 0;
            
            switch (cmd[0].charAt(0)) {
                case 'N': dir = 0; break;
                case 'S': dir = 1; break;
                case 'W': dir = 2; break;
                case 'E': dir = 3; break;
            }
            
            int cnt = Integer.parseInt(cmd[1]);
            
            int nx = x;
            int ny = y;
            boolean canMove = true;
            
            for (int i = 0; i < cnt; i++) {
                nx += dx[dir];
                ny += dy[dir];
                
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || park[nx].charAt(ny) == 'X') {
                    canMove = false;
                    break;
                }
            }
            
            if (canMove) {
                x = nx;
                y = ny;
            }
        }

        return new int[]{x, y};
    }
}

실행결과

HashMap 사용

switch문 사용

성능 비교

풀이 구분	시간복잡도(ms)	공간복잡도(MB)
HashMap 사용	1.27	85
Switch 사용	0.31	73

 

실행 속도는 75.6% 빨라졌고,

메모리: 14.1% 절감했다.