[코딩테스트합격자되기-자바편] 문제07. 방문길이

💡 해당 풀이는 코딩 테스트 합격자되기 - 자바편 에서 발췌된 내용을 바탕으로 작성되었습니다.

 

문제

출처: 프로그래머스 - 방문길이

 

내용

 

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

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

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

명령어가 매개변수 dirs로 주어질 때, 게임 캐릭터가 처음 걸어본 길의 길이를 구하여 반환하는 solution() 함수를 완성해 주세요.

 

제약 조건

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

 

입출력의 예

 

dirs	answer
ULURRDLLU	7
LULLLLLLU	7

 

풀이

 

풀이 시간

 

시작 시각	종료 시각	총 소요 시간
15:56	16:42	48분

 

문제 분석

• U: 위쪽으로 한 칸 가기 -> (0, 1)
• D: 아래쪽으로 한 칸 가기 -> (0, -1)
• R: 오른쪽으로 한 칸 가기 -> (1, 0)
• L: 왼쪽으로 한 칸 가기 -> (-1, 0)

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

 

 

제약 사항 파악 & 테스트 케이스 작성

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

 

입력값 분석

💡 입력값을 분석하면 문제에서 요구하는 알고리즘의 시간 복잡도를 간접적으로 파악할 수 있습니다.

 

dirs	answer
ULURRDLLU	7
LULLLLLLU	7

 

 

의사 코드 작성

💡 의사 코드는 동작 중심으로 작성하는 것이 중요합니다.

💡 의사 코드는 문제 해결 순서로 작성합니다.

💡 의사 코드를 충분히 테스트해봅니다.

int solution(String dirs) {
    // direction
    // U = (0, 1)
    // D = (0, -1)
    // R = (1, 0)
    // L = (-1, 0)
    // edge (-5, 5), (-5, -5), (5, -5), (5, 5)
    // start = (0, 0)
    int answer = 0;
    // 1. char 쪼개기
    for (dir in dirs) {
        // 1. next = prev + direction
        // 2. 0보다 작을 경우 max(-5), 0보다 클 경우 min(5)
        // next != prev 일 경우 answer++
    }
    return answer;
}

 

 

구현

import java.util.HashMap;
import java.util.HashSet;

class Solution {
    public int solution(String dirs) {
        // direction
        HashMap<Character, int[]> directions = new HashMap<>();
        directions.put('U', new int[]{0, 1});
        directions.put('D', new int[]{0, -1});
        directions.put('R', new int[]{1, 0});
        directions.put('L', new int[]{-1, 0});

        int max = 10;
        int min = 0;

        int prevX = 5;
        int prevY = 5;

        HashSet<String> answer = new HashSet<>();

        // 1. for 문
        for (int i = 0; i < dirs.length(); i++) {
            // 1. next = prev + direction
            char dir = dirs.charAt(i);
            int[] direction = directions.get(dir);
            int nextX = prevX + direction[0];
            int nextY = prevY + direction[1];

            // 2. 0보다 작을 경우 혹은 10보다 클 경우 continue
            if (nextX > max || nextX < min || nextY > max || nextY < min) {
                continue;
            }

            // 3. 방문 업데이트
            // a -> b 인 경우 b -> a 와 동일하게 방문된 곳이므로 추가되어야 함
            answer.add(prevX + " " + prevY + " " + nextX + " " + nextY);
            answer.add(nextX + " " + nextY + " " + prevX + " " + prevY);

            // 4. 좌표 업데이트
            prevX = nextX;
            prevY = nextY;
        }
        return answer.size() / 2;
    }
}

 

 

복기하기

저자 권장 시간	권장 시간 복잡도
40분	O(N)

 

 

답안과 나의 풀이를 비교해보세요

• 원점 옮기는 것도 고려해 보기
• 쉽게 생각하기
• 중복되는 경우가 존재하고 답에서 중복된 값을 제거해야 한다면 HashSet 사용 생각해보기

 

 

요약하기

• 시간복잡도 O(N)