[코드트리/NOVICE MID] 되돌아오기 (JAVA)

🔺 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int max = 2000;
 
    static int[] dx = {0,0,1,-1};   // 동서남북 (행과 열로 생각)
    static int[] dy = {1,-1,0,0,};
 
    static int N, dir;
    static int[][] map = new int[max + 1][max + 1];
    static int x = 500, y = 500; // 시작점을 500,500으로 설정 (마이너스 고려해서)
    static int time = 0;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
 
        while(N --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            dir = getDir(st.nextToken().charAt(0));
            int dist = Integer.parseInt(st.nextToken());
 
            while(dist --> 0) {
                x += dx[dir];
                y += dy[dir];
 
                map[x][y] = time++; // 이동 시간 갱신
 
                // 시작점으로 돌아오면, 답 갱신
                if(x == 500 && y == 500) {
                    System.out.println(time);
                    return;
                }
            }
        }
 
        System.out.println(-1);
    }
 
    // 방향 구하는 메소드
    private static int getDir(char c) {
        if(c == 'E')       return 0;
        else if(c == 'W')   return 1;
        else if(c == 'S')   return 2;
        else                return 3;
    }
}

 

 

 

🧩  해결 아이디어

• dx/dy technique

입력받은 시간과 이동 거리만큼 이동하며 시간을 +1해 갱신한다.

이동했을 때의 위치가 시작점과 같다면 현재까지 소요된 시간을 출력한다.

 

시작점에 도달하지 않는다면, -1을 출력한다.

 

 

 

---

🔺 다른 풀이들

- 사실 이동한 시간을 2차원 배열에 저장하면서 다닐 필요는 없고,

소요 시간만 갱신해 주면 되더라,,~~

import java.util.Scanner;

public class Main {
    public static final int DIR_NUM = 4;
    
    public static int n, x, y;
    public static int[] dx = new int[]{1, -1,  0, 0};	// 동서남북 순
    public static int[] dy = new int[]{0,  0, -1, 1};
    
    public static int ans = -1;
    public static int elapsedTime;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        
        while(n-- > 0) {
            char cDir = sc.next().charAt(0);
            int dist = sc.nextInt();
            
            int dir;
            if(cDir == 'E')
                dir = 0;
            else if(cDir == 'W')
                dir = 1;
            else if(cDir == 'S')
                dir = 2;
            else
                dir = 3;
            
            // 주어진 방향대로 dist만큼 위치 이동
            boolean done = move(dir, dist);
            
            // 시작 위치에 도달했다면, 종료
            if(done) break;
        }
        
        System.out.print(ans);
    }
    
    // dir 방향으로 dist 만큼 이동하는 함수
    public static boolean move(int dir, int dist) {
        while(dist-- > 0) {
            x += dx[dir];
            y += dy[dir];
            
            elapsedTime++;	// 이동한 시간 기록
    
            // 시작지로 다시 돌아오면, 답 갱신
            if(x == 0 && y == 0) {
                ans = elapsedTime;
                return true;
            }
        }
        
        return false;
    }
}

 

---

💬 느낀 점

하 어렵지 않은 문제인데 나는 왜 시간이 오래 걸리는 것인가...!

더 집중해서 푸는 시간을 줄이자ㅠ

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 코드트리 dx/dy technique