[알고리즘]프로그래머스 49994번 - 방문 길이

프로그래머스 49994번 - 방문 길이

프로그래머스 49994번 - https://programmers.co.kr/learn/courses/30/lessons/49994

프로그래머스 49994번 - https://programmers.co.kr/learn/courses/30/lessons/49994

 

요구사항

1. 좌표평면상 U는 위로 한 칸, D는 아래로 한 칸, L은 왼쪽으로 한 칸, R은 오른쪽으로 한 칸 이동하는 명령어입니다.

2. 캐릭터는 좌표평면의 (0, 0)에서 시작합니다.

3. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래 (5, -5)로 이루어져 있습니다.

4. 단, 좌표평면의 경계를 넘어가는 명령어는 무시합니다.

5. 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 반환하라.

 

요구사항 분석 및  풀이과정

캐릭터가 이미 거쳐 간 길을 제외한 처음 걸어본 길의 길이를 구하여야 합니다.

 

그런데, 하나의 길을 지나가는 방법은 다음과 같이 총 4가지 방법이 존재합니다.

 

왼쪽에서 오른쪽 방향

오른쪽에서 왼쪽 방향

아래쪽에서 위쪽 방향

위쪽에서 아래쪽 방향

 

그러나 이 모든 방법은 모두 동일한 길을 지나가는 방법이기 때문에 처음 걸어본 길의 길이를 구하기 위해서는 하나로 식별할 방법이 필요합니다. 여러 가지 방법이 있겠지만 저는 어떤 방향으로 길을 지나던, 하나로 식별하기 위하여 다음과 같이 기준을 세웠습니다.

 

가로 방향의 길의 경우 길의 왼쪽 끝과 오른쪽 끝 좌표 순

세로 방향의 길의 경우 길의 아래쪽 끝과 위쪽 끝 좌표 순

 

위의 식별 방법으로 유일하게 길을 나타내는 Road 클래스를 디자인할 것이고, 캐릭터가 이미 거쳐간 길에 대한 중복을 제거하기 위하여 HashSet 자료구조를 사용, Road 객체를 다룰 것입니다.

 

그러기 위해서는 Road 클래스에 HashSet 내부에서 사용할 Road 객체의 hash 값과 equals 메서드를 작성하여야 합니다. 위 식별방법을 이용하여 작성하였습니다. (Road 클래스의 hashCode 메서드와 equals 메서드를 참고)

 

또한 캐릭터가 이동 명령어를 실행했을 때 좌표평면의 경계를 넘어가는 명령어를 무시하기 위하여 예외처리(boundary 메서드)를 해주어야 합니다.

 

모든 이동 명령어를 수행하여 이동 명령어를 수행하기 전 위치와 이동 명령어를 수행한 위치를 두 점으로 한 Road 객체를 만들어 HashSet에 추가합니다.

 

그렇게 되면 이미 거쳐간 길은 한 번만 추가되며, 최종적으로 HashSet의 크기(size)가 캐릭터가 처음 걸어본 길의 길이가 될 것입니다.

 

여기서 주의하여할 점은 만약 캐릭터가 이동 명령어를 수행하여 좌표평면의 경계를 넘어가게 될 경우 캐릭터는 상대적인 위치 변화가 없으므로 어느 길도 건너지 않습니다. 그 경우는 Road 객체를 HashSet에 추가해서는 안됩니다.

 

그 이외 위치를 디자인한 Point 클래스, 캐릭터를 디자인한 GameCharacter 클래스 등은 소스코드를 참고해주세요.

 

소스코드 작성

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

class Solution {

	private static final int HALF_LENGTH = 5;

	private static class Position {

		private final int x;
		private final int y;

		public Position(int x, int y) {
			this.x = x;
			this.y = y;
		}

		public int getX() {
			return x;
		}

		public int getY() {
			return y;
		}

		@Override
		public boolean equals(Object o) {
			if (this == o)
				return true;

			if (!(o instanceof Position))
				return false;

			Position position = (Position)o;
			return x == position.x && y == position.y;
		}

		@Override
		public int hashCode() {
			return Objects.hash(x, y);
		}
	}

	private static class GameCharacter {

		private Position position;
		private final int width;
		private final int height;

		public GameCharacter(int width, int height, int x, int y) {
			this.width = width;
			this.height = height;
			this.position = new Position(x, y);
		}

		public Position getPosition() {
			return new Position(position.x, position.y);
		}

		private int boundary(int base, int delta, int lowerBound, int upperBound) {
			if (delta >= 0) {
				return Math.min(base + delta, upperBound);
			} else {
				return Math.max(base + delta, lowerBound);
			}
		}

		private Position move(int x, int y) {
			int nextX = boundary(position.x, x, -1 * width, width);
			int nextY = boundary(position.y, y, -1 * height, height);
			position = new Position(nextX, nextY);
			return position;
		}

		public Position move(char direction) {
			switch (direction) {
				case 'U':
					return move(0, 1);
				case 'D':
					return move(0, -1);
				case 'L':
					return move(-1, 0);
				case 'R':
					return move(1, 0);
				default:
					return move(0, 0);
			}
		}
	}

	public static class Road {

		private final Position first;
		private final Position second;

		public Road(Position first, Position second) {
			if (first.getX() == second.getX()) {
				this.first = first.getY() <= second.getY() ? first : second;
				this.second = first.getY() <= second.getY() ? second : first;
			} else {
				this.first = first.getX() < second.getX() ? first : second;
				this.second = first.getX() < second.getX() ? second : first;
			}
		}

		@Override
		public boolean equals(Object o) {
			if (this == o)
				return true;

			if (!(o instanceof Road))
				return false;

			Road road = (Road)o;
			return this.first.equals(road.first) && this.second.equals(road.second);
		}

		@Override
		public int hashCode() {
			return Objects.hash(first, second);
		}
	}

	public int solution(String dirs) {
		GameCharacter character = new GameCharacter(HALF_LENGTH, HALF_LENGTH, 0, 0);
		Set<Road> navigation = new HashSet<>();

		for (char dir : dirs.toCharArray()) {
			Position current = character.getPosition();
			Position next = character.move(dir);

			if (!(current.equals(next))) {
				navigation.add(new Road(current, next));
			}
		}

		return navigation.size();
	}
}

 

 

결과

 

소스코드 깃허브 주소

링크

 

마무리

단순히 빠른 시간내에 푸는 코딩 테스트 문제라고 할지라도 최대한 객체적인 사고를 하면서 짜려고 하고 있습니다. 문제를 푸는 것만에 초점을 맞출 경우 코드의 수를 대폭 줄일 수 있습니다. 속도 또한 ms 단위지만 2~10배까이 빠르게 할 수 있습니다.

 

이 말을 적는 이유는, 간혹 제 풀이에 쓸데 없이 클래스를 만들고 사용하는 방식의 문제풀이 방법이 의아해하실 분들 위하여 적습니다.