[프로그래머스 Summer/Winter Coding(~2018)] 방문길이 -Java

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

코딩테스트 연습 - 방문 길이

import java.util.HashSet;
import java.util.Set;

class Solution {
	    public int solution(String dirs) {
	        int answer = 0;
	        int dx[]= {-1,1,0,0}; //위 아래 왼 오 
	        int dy[]= {0,0,-1,1};	    
	        Set<String> set = new HashSet<>();
	        int x=5,y=5;
	        
	        dirs=dirs.replace('U', '0').replace('D', '1').replace('L', '2').replace('R', '3');
	        
	        for(int i=0; i<dirs.length(); i++) {
	        	int nx=x+dx[dirs.charAt(i)-'0'];
	        	int ny=y+dy[dirs.charAt(i)-'0'];
	        	
	        	if(nx<0 || ny<0 || nx>10 || ny>10) continue;
	        	
	        	if(!set.contains(x+","+y+","+nx+","+ny)) {
	        		answer++;
	        		set.add(x+","+y+","+nx+","+ny);
	        		set.add(nx+","+ny+","+x+","+y);
	        	}
	        	x=nx;
	        	y=ny;
	        }
	        return answer;
	    }
	}

소요시간 : 30분

 

 

로직을 살펴보면

우선 U, D, L, R를 편하게 사용하기 위해 replace로 숫자로 바꾸어주었습니다!

 

이렇게 입력이 들어온다면 x, y의 좌표는 초기 0,0에서

1. 0,0  ->  1,0

2. 1,0  ->  1,-1

3. 1,-1 ->  2,-1

4. 2,-1 ->  2,0

5. 2,0  ->  2,1

6. 2,1  ->  1,1

7. 1,1  ->  1,0

8. 1,0  ->  1,-1

9. 1,-1 -> 2,-1

 

처럼 바뀌게 됩니다. 여기서 8번 9번은 이미 지나왔던 길입니다.

 

근데 잘 보면 가로( ㅡ )는 왼쪽에서 오른쪽으로 오거나 오른쪽에서 왼쪽으로 밖에 못 옵니다.

마찬가지고 세로( | )는 위에서 아래, 또는 아래에서 위로 밖에 못 옵니다.

 

그래서 1번. 0,0 -> 1,0의 값을 set에

(0,0,1,0)->0,0에서 1,0으로 간다는 뜻,

(1,0,0,0)->1,0에서 0,0으로 간다는 뜻,

처럼 한 번에 두 개를 넣어줍니다!

 

그리고 x, y를 이동시킬 때마다 set에 들어가 있는지 확인하고 안 들어가 있다면 answer을 하나 늘려주고 set에 삽입해줍니다!