방문 길이

문제 설명

게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.

• U: 위쪽으로 한 칸 가기
• D: 아래쪽으로 한 칸 가기
• R: 오른쪽으로 한 칸 가기
• L: 왼쪽으로 한 칸 가기

캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.

 

예를 들어, "ULURRDLLU"로 명령했다면

• 다음과 같이 움직입니다.

• 8번 명령어부터 9번 명령어까지 다음과 같이 움직입니다.

이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다.

 

제한사항

• dirs는 string형으로 주어지며, 'U', 'D', 'R', 'L' 이외에 문자는 주어지지 않습니다.
• dirs의 길이는 500 이하의 자연수입니다.

 

---

나의 풀이

class Solution {
    public int solution(String dirs) {
		int lenOfDirs = dirs.length();
		int x=0, y=0, bx=0, by=0;
		int dot = 0;
		HashSet<String> set = new HashSet<String>();
		for(int i=0;i<lenOfDirs;i++) {
			char dir = dirs.charAt(i);
			if 	(dir == 'U') 	y++;
			else if (dir == 'D') 	y--;
			else if (dir == 'R') 	x++;
			else 			x--;	//dir == 'L'
			
			if (x>5) 	x = 5;
			if (x<-5) 	x = -5;
			if (y>5) 	y = 5;
			if (y<-5) 	y = -5;
			
			String str1 = x+""+y+" "+bx+""+by;
			String str2 = bx+""+by+" "+x+""+y;
			bx = x;
			by = y;
			
			if(str1.equals(str2) && !set.contains(str1)) dot++;
			set.add(str1);
			set.add(str2);
		}
        return (set.size()-dot)/2;
    }
}

캐릭터의 위치를 (x,y) 좌표로 계산하고, HashSet을 이용해 선을 저장했다.

String 부분을 StringBuilder로 더하려고 했는데 수정을 깜빡했다..(ㅠㅠ)

 

처음에는 HashSet에 거쳐간 점을 저장했었는데 예외처리하기가 번거롭다.

같은 점을 또 지났으나 지나온 길은 다를때 같은...

 

선은 두 점의 좌표를 String 형태로 묶어서 표시한다.

bx, by: 이전 위치의 점 좌표

x, y: 현재 위치의 점 좌표

로 취급해서 "점좌표 점좌표"를 저장한다.

점1-점2를 잇는 선과 점2-점1를 잇는 선이 같으므로 xy bxby, bxby xy 둘 다 HashSet에 저장한다.

만약 xy와 bxby가 동일하다는건 x나 y가 이동할 수 있는 위치를 벗어나려고 했던 시도이므로 dot에 카운트를 해준다.

 

이후에 Hashset의 크기를 구하면 구해야하는 선의 2배 크기이다.

(점1-점2 선분과 점2-점1 선분이 다르므로)

점1과 점2가 같은 경우 점1-점1 같은 형식의 선이 저장되어있으므로 크기에서 빼준다 (dot)

 

코드가 깔끔하다는 생각은 안든다ㅠㅠ

 

다른 사람 코드를 보며 몇 가지 개선 사항이 추가적으로 생각났다.

• String말고 StringBuilder 사용
• x, y가 범위를 벗어나면 set에 추가하지 않기
• x, y와 bx, by가 같으면 set에 추가하지 않기

 

HashSet에 무조건 추가하고 나서 계산식을 생각했는데 애초에 추가할 필요가 없었다.

 

---

개선 후 코드

class Solution {
    public int solution(String dirs) {
		int lenOfDirs = dirs.length();
		int x=0, y=0, bx=0, by=0;

		HashSet<String> set = new HashSet<String>();
		for(int i=0;i<lenOfDirs;i++) {
			char dir = dirs.charAt(i);
			if 	(dir == 'U') 	y++;
			else if (dir == 'D') 	y--;
			else if (dir == 'R') 	x++;
			else 			x--;	//dir == 'L'
			
			if (x>5) 	{ x = 5; continue; }
			if (x<-5) 	{ x = -5; continue; }
			if (y>5) 	{ y = 5; continue; }
			if (y<-5) 	{ y = -5; continue; }
			
			String str1 = makeLine(x,y,bx,by);
			String str2 = makeLine(bx,by,x,y);

			bx = x;
			by = y;
			
			set.add(str1);
			set.add(str2);
		}
        return set.size()/2;
    }
	
	public String makeLine (int x, int y, int bx, int by) {
		StringBuilder sb = new StringBuilder();
		sb.append(x).append(y).append(" ").append(bx).append(by);
		return sb.toString();
	}
}

< 개선 전, > 개선 후

개선하니까 훨씬 빨리지는걸 볼 수 있다!!

 

---

다른 사람 코드

class Solution {
    public int solution(String dirs) {
        Map<String, int[]> map = new HashMap<>();
        map.put("U", new int[] {0, 1});
        map.put("D", new int[] {0, -1});
        map.put("R", new int[] {1, 0});
        map.put("L", new int[] {-1, 0});

        String[] arr = dirs.split("");

        Set<String> set = new HashSet<>();        
        int cx = 0;
        int cy = 0;

        for(int i=0; i<arr.length; i++) {
            String s = arr[i];

            int x = map.get(s)[0];
            int y = map.get(s)[1];

            cx += x;
            cy += y;

            if(cx < -5 || cx > 5) {
                cx -= x;
                continue;
            }
            if(cy < -5 || cy > 5) {
                cy -= y;
                continue;
            }
            set.add(""+(cx-x)+ ""+ (cy-y)+ ""+cx + ""+cy);
            set.add(""+cx + ""+cy+""+(cx-x)+ ""+ (cy-y));
        } 
        return set.size()/2;
    }
}

출처: https://programmers.co.kr/learn/courses/30/lessons/49994/solution_groups?language=java