[알고리즘] 구현 : 상하좌우

[문제]

https://velog.io/@sugenius77/%EC%9D%B4%EA%B2%83%EC%9D%B4-%EC%BD%94%EB%94%A9-%ED%85%8C%EC%8A%A4%ED%8A%B8%EB%8B%A4-with-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EA%B5%AC%ED%98%84-%EC%83%81%ED%95%98%EC%A2%8C%EC%9A%B0

 

 

[회고]

• StringTokenizer에는 hasMoreTokens() / countTokens()라는 메서드가 있다.
• 쉬운 문제라고 생각했고, 델타 배열을 사용하는 완전탐색으로 풀었다.

public class 상하좌우 {
    static int[] dy4 = {-1, 1, 0, 0};
    static int[] dx4 = {0, 0, -1, 1};

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int sizeOfMap = Integer.parseInt(br.readLine());
        int[][] map = new int[sizeOfMap][sizeOfMap]; 
        
        int x = 1;
        int y = 1;
        String str = br.readLine(); 
        StringTokenizer st = new StringTokenizer(str);
        while(st.hasMoreTokens()) {
            String token = st.nextToken();
            int nx = x;
            int ny = y;

            switch (token) {
                case "U":
                    ny += dy4[0];
                    break;
                case "D":
                    ny += dy4[1];
                    break; 
                case "L":
                    nx += dx4[2];
                    break;
                case "R":
                    nx += dx4[3];
                    break;
            }
            x = nx;
            y = ny;
        }
        System.out.println(x + " " + y);
    }
}

• sizeOfMap은 명확한 변수명이지만, 알고리즘 퓰아에서는 n,m,i,j,k 정도의 변수명을 활용하는 게 좋아보인다.
• 쓰이지도 않은 map은 삭제해야겠다.
• 이동 후 위치가 지도 범위를 벗어나는지 확인하지 않는다. → 수정 필요
• switch 문을 사용하여 방향을 처리하는 부분이 불필요하게 느껴진다.
• 두 가지 제안을 할 수 있어 보인다. 1) 델타 없이 푼다면? 2) UDRL을 스트링 배열에 미리 넣어 놓는다면? 어차피 방향은 네 가지밖에 없고, fori 로 처리가 간편해질 것 같다.

 

[수정 코드 : 델타 없이 하드 코딩하는 버전]

public class 상하좌우_2 {
    static int n;
    static char[] plans;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int count = st.countTokens(); 
        plans = new char[count];

        int y = 1, x = 1;

        for (int i = 0; i < count; i++) {
            plans[i] = st.nextToken().charAt(0);
        }

        for (int i = 0; i < count; i++) {
            int ny = y;
            int nx = x;

            switch (plans[i]) {
                case 'L' : nx = nx - 1; break;
                case 'R' : nx = nx + 1; break;
                case 'U' : ny = ny - 1; break;
                case 'D' : ny = ny + 1; break;
            }

            if (ny < 1 || nx < 1 || ny > n || nx > n) continue;

            y = ny;
            x = nx;
        }
        System.out.println(y + " " + x);
    }
}

• 방향을 char[] 배열에 넣어 좀 더 가볍게 만들었다.
• Switch문 안을 1줄로 만들어 가독성을 약간 더 향상시켰다. 

 

[수정 코드 : plans를 미리 String 배열로 만들어 놓은 버전]

public class 상하좌우_3 {
    static int n;
    static int[] dy4 = {-1, 1, 0, 0};
    static int[] dx4 = {0, 0, -1, 1};
    static String[] plans = {"U", "D", "L", "R"};

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        int y = 1, x = 1;

        while(st.hasMoreTokens()) {
            String token = st.nextToken();

            int nx = x;
            int ny = y;
            for (int i = 0; i < plans.length; i++) {
                if(plans[i].equals(token)) {
                    ny += dy4[i];
                    nx += dx4[i];
                }
            }

            if (ny < 1 || nx < 1 || ny > n || nx > n) continue;

            x = nx;
            y = ny;
        }
        System.out.println(y + " " + x);
    }
}

• Switch문을 사용하지 않고, 가장 간단하고 유연하게 이동을 처리한다.
• 하지만 .equals()가 무거운 메서드라, 테스트 케이스가 커진다면 효율적이지 않다.