[프로그래머스] 방문 길이

오늘의 문제는 레벨 2에 해당하는 <방문 길이>인데요.
(문제 출처 : 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/49994)

프로그래머스는 블로그 게재 시 문제 여지가 있어
자세한 내용 없이 문제 제목과 링크로 대체합니다. 

게임 캐릭터가 제한된 맵(좌표) 내에서
상하좌우로 움직이는 경로의 길이를 계산하는 문제였다.

내 첫 접근법은
1) 좌표니까 계산하기 쉽게 배열을 쓰고
2) 그 다음에 좌표값에 따라 배열마다 횟수를 저장하면 되겠지 였다.

// 이 코드는 정답이 아닙니다 //
class Solution {
    public int solution(String dirs) {
        int answer = 0;
        
        // 좌표평면 배열
        // 배열[5][5]가 좌표평면 (0.0) = 배열 -5하면 좌표 평면 위치가 나옴
        int[][] path = new int[11][11];
        int x = 5, y = 5; 
        
        for (int i=0; i<dirs.length(); i++){
            char c = dirs.charAt(i);
            
            switch (c){
                case 'U': // 위로 한 칸
                    if (y<10) {y++;} break; 
                case 'D': // 아래로 한 칸
                    if (0<y) {y--;} break;
                case 'R': // 오른쪽으로 한칸
                    if (x<10) {x++;} break;
                case 'L': // 왼쪽으로 한 칸
                    if (0<x) {x--;} break;
            }
            
            // 처음 걸어본 길일 때만
            if (path[x][y] == 0) {
                path[x][y] += 1;
                answer++;
            }
        }
        return answer;
    }
}

 

근데 코드를 돌려 보니 실패!
다시 살펴보니 너무 단순하게 생각해
방향성을 고려하지 않았다.

내 코드대로 라면 (0.0) 에서 U 해서 1이 되면
(2.1) 에서 L로 다시 돌아오는 것도 카운트가 안됨...

그래서 바꾼 게 3차원 배열로 방향성을 추가해 주는 거였다.
하지만 가내수공업으로 U/D 또는 L/R을 다 고려해줘야 했고요...
그래서 이렇게 지저분한 코드가 탄생했지요

import java.util.*;

class Solution {
    public int solution(String dirs) {
        int answer = 0;
        
        // 좌표평면 배열
        // 배열[5][5]가 좌표평면 (0.0) = 배열 -5하면 좌표 평면 위치가 나옴
        // [][][방향] 0 U, 1 D, 2 L, 3 R
        int[][][] path = new int[11][11][4];
        int x = 5, y = 5;

        for (int i=0; i<dirs.length(); i++){
            char c = dirs.charAt(i);
            
            switch (c){
                case 'U': // 위로 한 칸
                    if (y<10) {
                        path[x][y][0] = 1;
                        y++;
                        path[x][y][1] = 1;
                    } break; // 경로마다 방향은 양쪽 + 처음 걸은 1번만 카운트
                case 'D': // 아래로 한 칸
                    if (0<y) {
                        path[x][y][1] = 1;
                        y--;
                        path[x][y][0] = 1;} break;
                case 'R': // 오른쪽으로 한칸
                    if (x<10) {
                        path[x][y][3] = 1;
                        x++;
                        path[x][y][2] = 1;} break;
                case 'L': // 왼쪽으로 한 칸
                    if (0<x) {
                        path[x][y][2] = 1;
                        x--;
                        path[x][y][3] = 1;} break;
            }
        }
        
        for (int i=0; i<path.length; i++){
            for(int j=0; j<path[0].length; j++){
                for(int k=0; k<path[0][0].length; k++){
                    if (path[i][j][k] == 1) {
                        answer++;
                    }
                }
            }
        }
        answer = answer/2; // 양방향이라 /2
        return answer;
    }
}

답안을 보니 이렇게 중복 미포함과 같은 문구가 나올 때는 해시셋을 떠올리라고 하더라
자바의 HashSet은 Set 인터페이스를 구현한 클래스다.
1) 중복된 값을 허용하지 않음
2) 입력한 순서가 보장되지 않음
3) null을 값으로 허용함

대충 로직은 이래서 나랑 비슷하기는 한데...
코드는 훨씬 더 간결하다 심지어 이건 시간복잡도도 N이라서
나중에 다른 문제 풀면서 해시맵/셋을 활용하기 위해 노력해 봐야겠다.

import java.util.*;


private static boolean isValidMove(int nx, int ny){
    return 좌표평면 내인지 체크하는 함수 구현
}

// 다음 좌표 결정을 위한 해시맵 생성
private static final HashMap<Character, int[]> location = new HashMap<>();

private static void initLocation(){
	// put 함수 사용, 상하좌우에 따른 배열을 생성함
}

class Solution {
    public int solution(String dirs) {

        initLocation();
        int x = 5, y = 5;

        // 겹치는 좌표는 1개로 처리
        HashSet<String> answer = new HashSet<>();

        for (int i=0; i<dirs.length(); i++){

            // UDLR을 가지고 매번 새로운 배열 offset을 만든다
            int[] offset = locations.get(dirs.charAt(i));
			// 그리고 좌표값 nx, ny를 계산함
            
            if (!isValideMove(nx,ny)) continue;
            // 범위 벗어나면 패스함

            // A에서 B로 간 경우, B에서 A로 간 경우를 해시셋에 추가
            // 해시셋에 추가하는 메소드는 .add
            // 0 0 >> 0 1
            // 0 1 >> 0 0

            // 좌표 이동 후 x, y를 업데이트
        }

        return answer ;
    }
}

이렇게 해서 "코딩 테스트 합격자 되기:자바 편"의 첫 번째 파트인 "배열"이 끝났다.
마지막에 풀어 보면 좋을 추천 문제도 알려주더라
- 배열의 평균값
- 배열 뒤집기
- 배열 자르기
- 나누어 떨어지는 숫자 배열
앞에 2개는 풀어봤던 거라, 뒤에 2개만 풀어보고 스택으로 넘어갈 예정이다.

반복해서 포스팅하고 있는데,
내가 보면서 공부하고 있는 책은 "코딩 테스트 합격자 되기:자바 편"이다.
가격은 정가 42,000원이다. (밀리의 서재에도 있음)