[코딩 테스트] 방문 길이

https://school.programmers.co.kr/learn/courses/30/lessons/49994

프로그래머스

 

단순 구현문제이다.

 

처음 생각해낸 생각

1. 아 중복을 없애야 되니 HashSet을 이용해 볼까?

2. Point 객체를 만들어서 현재 x좌표랑 Y좌표를 Set의 객체로 넣어주어야 할까?

3. 그러면 너무 복잡해 지고, 만약 점 A-> B로 가는거랑 B->A로 가는 것을 중복되는 것으로 표현하려면 어떤 식으로 할 지 잘 모르겠어..

 

 

이렇게 생각하게 되어서 결국 2차원 배열을 가져가는 방식을 하였다.

 

최종 구현하기 위한 생각

나는 2차원 배열을 2개 만들어서 0으로 초기화 해둔 후에, 방문하였으면 1로 관리하려고 하였다.

그래서 만약 방문했던 곳을 또 방문하면 count를 세지 않는 것이 나의 생각이었다.

 

그림으로 어떤식으로 배열을 나타냈지 표현해보도록 하겠다.

 

위 처럼 빨간색은 가로 방문 edge를 나타내고, 파란색은 세로 방문 edge를 저장하게 된다.

 

처음 시작점은 좌표 x=5,y=5일 것이다.

 

- 좌표를 움직이고, 지나간 곳은 2차원 배열의 값을 1로 업데이트 해준다.

- 만약 x,y좌표가 0보다 작거나, 10보다 크게 되면 움직이지 않는다

- 만약 지금 지나간 곳의 2차원 배열을 확인하였을 경우에 값이 0이 아니라 1(지나갔던 경우)면 answer변수의 숫자를 증가시키지 않는다.

 

이런식으로 코드를 짜보았다.

class Solution {
    public int solution(String dirs) {
    int[][] x = new int[10][11];
    int[][] y = new int[11][10];
        
    int xp=5;
    int yp=5;
    
    int answer = 0;
        
    char[] commands=dirs.toCharArray();
    int tmp=0;
        
    for(int i = 0; i<commands.length ; i++){
        char command = commands[i];
        if(command=='U'){
            if(yp==10) continue;
            tmp = y[xp][yp];
            y[xp][yp]=1;
            yp++;
        }
        if(command=='D'){
            if(yp==0) continue;
            tmp = y[xp][yp-1];
            y[xp][yp-1]=1;
            yp--;
        }
        if(command=='R'){
            if(xp==10) continue;
            tmp = x[xp][yp];
            x[xp][yp]=1;
            xp++;
        }
        if(command=='L'){
            if(xp==0) continue;
            tmp = x[xp-1][yp];
            x[xp-1][yp]=1;
            xp--;
        }
        
        if(tmp!=1){
            answer++;
        }
        
    }
    
    return answer;
    }
}

 

이게 내가 생각해낸 코드다.

 

이 코드를 구현하면서 직접 손으로 그려보면서 해보았는데, 2차원 배열의 인덱스를 찾는 것이 거의 하드코딩으로 한 것 같은 느낌이 있어서 뭔가 시원하게 해결한 문제는 아닌 것 같다.

 

그래서 교재의 답을 확인해보았다.

 

교재 방식

내가 처음에 생각했더 것 처럼 중복되는 요소가 없어야 하기에 HashSet을 사용하는 방식을 구현하였다.

내가 HashSet을 사용하면 구현이 복잡해지고, A->B랑 B->A가 같은 것이라는 것을 어떻게 구별할까에 대해서 간단하게 해결한 모습을 볼 수 있다.

 

코드를 보면서 설명해보도록 하겠다.

import java.util.*;

class Solution {
    private static final HashMap<Character,int[]> location=new HashMap<>();
    
    public boolean isValid(int x,int y){
        return x>=0&&x<=10&&y>=0&&y<=10;
    }
    
    public void init(){
        location.put('U',new int[]{0,1});
        location.put('D',new int[]{0,-1});
        location.put('R',new int[]{1,0});
        location.put('L',new int[]{-1,0});
    }
    public int solution(String dirs) {
        int x=5;
        int y=5;
        init();
        
        HashSet<String> answer = new HashSet<>();
        
        for(int i=0;i<dirs.length();i++){
            int[] offset = location.get(dirs.charAt(i));
            int nx=x+offset[0];
            int ny=y+offset[1];
            if(!isValid(nx,ny)) continue;
            answer.add(x+" "+y+" "+nx+" "+ny);
            answer.add(nx+" "+ny+" "+x+" "+y);
            
            x= nx;
            y= ny;
        }
        
        
        return answer.size()/2;
    }
    
    
}

 

먼저 구현문제를 풀 때는 함수를 조금 나눠서 로직을 구분하면 좋다고 말한다.

그래서 isValid()함수는 좌표가 범위내에 있는 좌표인지 확인하는 함수이고

init()함수는 U,D,R,L를 나타내는 좌표를 저장하고 있는 함수를 HashMap에 저장하는 함수이다

 

간단하게 잘 구현한 것 같다.

 

보면 내가 처음에 고민했던

1. HashSet을 저장할때, 역방향은 어떻게 중복되는지 확인할지

2. 좌표가 총 4개 인데 이것을 어떤 식으로 데이터를 나타낼 지에 대해서 해결한 방법을 보자

 

1. 먼저 HashSet을 저장할때 역방향을 확인하기 위해서 add를 역방향에 대해서도 해준다. 그렇게 되면 나중에 역방향이 들어올 때도 이미 방문했던 것으로 알 수 있게 된다.

물론 그렇게 되면 총2배의 방문길이가 생기기에 마지막에 return을 할때에 나누기 2를 해주는 과정이 필요하다.

 

2. 그 다음 좌표가 총 4개인데 어떤식으로 나타냈는지 확인해보면

그냥 단순이 HashSet<String> 타입을 이용해여 (x y nx ny) 이런식으로 띄어쓰기로 구분하여서 4개의 좌표를 나타내었다.