[프로그래머스] Lv.2 : 방문 길이 - 자바[Java]

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

프로그래머스

 

풀이

캐릭터가 지나간 길을 저장하는 Set 타입 변수를 사용하여 캐릭터가 처음 걸어본 길의 길이(Set의 크기)를 구한다.

 

길의 정보를 저장하기 위한 클래스 Line을 생성하고, Line은 시작점의 좌표와 도착점의 좌표 둘 다를 저장해야 하므로 int 형 변수 prevX, pervY, curX, curY를 필드 변수로 선언한다.

 

또한 Set<Line>형 변수 lineSet을 사용하므로 lineSet의 중복성 검사를 위해 클래스 Line에 equals() 메서드와 hashCode() 메서드를 오버라이딩해야 한다.

 

주의사항

• 좌표평면의 경계를 넘어가는 명령은 무시한다.
• 왼쪽에서 오른쪽으로 간 길과, 오른쪽에서 왼쪽으로 간 길은 같은 길이다. 이를 위해 prevX에는 x 좌표들 중 작은 x 좌표를 저장하고 curX에는 큰 x 좌표를 저장한다. prevY와 curY도 마찬가지로 저장한다.

 

로직

1. 클래스 Line을 생성한다. int 형 변수 prevX, pervY, curX, curY를 필드 변수로 선언한다. HashSet의 중복성 검사를 위해 equals() 메서드와 hashCode() 메서드를 오버라이딩한다.

2. 캐릭터가 걸어온 길을 저장할 Set<Line> lineSet을 선언한다.

3. 이전 길을 저장할 prevLine을 선언하고 (0, 0, 0, 0)으로 초기화한다.

4. dirs에 저장된 명령어 각각에 대해 다음을 수행한다.

• move() 메서드를 호출해 현재 이동한 경로(curLine)를 구한다.
• addLineSet() 메서드를 호출해 curLine을 lineSet에 저장한다.
• prevLine에 curLine을 저장한다.

5. lineSet의 크기를 반환한다.

 

Line move(Line prevLine, String dir) : 명령어(dir)을 통해 이동한 다음 현재 이동한 경로를 반환

    private static Line move(Line prevLine, String dir) {
        int prevX = prevLine.prevX, prevY = prevLine.prevY, curX = prevLine.curX, curY = prevLine.curY;
        
        prevX = curX;
        prevY = curY;
        
        switch(dir) {
                case "U": curY++; break;
                case "D": curY--; break;
                case "R": curX++; break;
                case "L": curX--; break;
        }
        
        if (checkIndex(curX, curY)) {
            return new Line(prevX, prevY, curX, curY);
        }
        else
            return prevLine;
    }

• prevX, prevY에 각각 curX, curY를 저장한다.
• dir에 따라 curX, curY를 변경한다.
• checkIndex() 메서드를 호출해 curX, curY가 좌표평면 경계를 넘어가는지 검사하고, 넘어가지 않는다면 이동한 경로를 반환한다. 넘어간다면 prevLine을 그대로 반환한다.

 

void addLineSet(Set<Line> lineSet, Line curLine) : curLine을 lineSet에 추가

    private static void addLineSet(Set<Line> lineSet, Line curLine) {
        int prevX = curLine.prevX, prevY = curLine.prevY, curX = curLine.curX, curY = curLine.curY;
        
        int tmp;
        
        if (prevX > curX) {
            tmp = prevX;
            prevX = curX;
            curX = tmp;
        }
        
        if (prevY > curY) {
            tmp = prevY;
            prevY = curY;
            curY = tmp;
        }
        
        lineSet.add(new Line(prevX, prevY, curX, curY));
    }

• prevX에는 x 좌표들 중 작은 x 좌표를 저장하고 curX에는 큰 x 좌표를 저장한다. prevY와 curY도 마찬가지로 저장한다.
• 새로운 Line 객체를 생성하여 lineSet에 추가한다.

 

코드

import java.util.*;

class Solution {
    static class Line {
        int prevX, prevY, curX, curY;
        
        public Line (int prevX, int prevY, int curX, int curY) {
            this.prevX = prevX;
            this.prevY = prevY;
            this.curX = curX;
            this.curY = curY;
        }
        
        @Override
        public boolean equals(Object obj) {
            if (obj instanceof Line) {
                Line line = (Line)obj;
                return (this.prevX == line.prevX) && (this.prevY == line.prevY) && (this.curX == line.curX) && (this.curY == line.curY);
            }
            return false;
        }
        
        @Override
        public int hashCode() {
            return Integer.toString(prevX+prevY+curX+curY).hashCode();
        }
    }
    
    public int solution(String dirs) {
        Set<Line> lineSet = new HashSet<>();
        Line prevLine = new Line(0, 0, 0, 0);
        
        for (String dir : dirs.split("")) {
            Line curLine = move(prevLine, dir);
            addLineSet(lineSet, curLine);
            prevLine = curLine;
        }
        
        return lineSet.size();
    }
    
    private static Line move(Line prevLine, String dir) {
        int prevX = prevLine.prevX, prevY = prevLine.prevY, curX = prevLine.curX, curY = prevLine.curY;
        
        prevX = curX;
        prevY = curY;
        
        switch(dir) {
                case "U": curY++; break;
                case "D": curY--; break;
                case "R": curX++; break;
                case "L": curX--; break;
        }
        
        if (checkIndex(curX, curY)) {
            return new Line(prevX, prevY, curX, curY);
        }
        else
            return prevLine;
    }
    
    private static boolean checkIndex(int curX, int curY) {
        if (curX >= -5 && curX <= 5 && curY >= -5 && curY <= 5)
            return true;
        return false;
    }
    
    private static void addLineSet(Set<Line> lineSet, Line curLine) {
        int prevX = curLine.prevX, prevY = curLine.prevY, curX = curLine.curX, curY = curLine.curY;
        
        int tmp;
        if (prevX > curX) {
            tmp = prevX;
            prevX = curX;
            curX = tmp;
        }
        if (prevY > curY) {
            tmp = prevY;
            prevY = curY;
            curY = tmp;
        }
        
        lineSet.add(new Line(prevX, prevY, curX, curY));
    }
}

 

 

Reference

HashSet 커스텀 클래스 중복 제거 방법 참고 글

• HashSet, HashMap에 Custom class 중복 제거하기
• 자바 HashSet이 중복값을 제거하지 못할 때
• [자바 소스] HashSet 사용시 중복 여부 판별 부여 방법

---

다른 풀이 2

• Map<String, int[]> dirMap을 선언하여 U, D, R, L에 따른 x, y 이동값을 저장한다.
• 이동 경로를 저장하기 위한 Line 클래스를 생성하지 않고, 대신 이동 경로를 문자열로 저장한다.
• Set<String> lineSet을 생성하고, 이후 lineSet을 저장할 때 "x+y+nx+ny" 문자열과 "nx+ny+x+y" 문자열을 같이 저장한다. 이후 결과를 반환할 때 lineSet.size() / 2를 리턴한다.

 

코드

import java.util.*;

class Solution {
    
    public int solution(String dirs) {
        Map<String, int[]> dirMap = new HashMap<>();
        dirMap.put("U", new int[]{0, 1});
        dirMap.put("D", new int[]{0, -1});
        dirMap.put("R", new int[]{1, 0});
        dirMap.put("L", new int[]{-1, 0});
        
        Set<String> lineSet = new HashSet<>();
        int x = 0, y = 0;
        
        for (String dir : dirs.split("")) {
            int dx = dirMap.get(dir)[0];
            int dy = dirMap.get(dir)[1];
            
            int nx = x + dx;
            int ny = y + dy;
            
            if (checkIndex(nx, ny)) {
                StringBuilder sb = new StringBuilder();
                sb.append(x).append(y).append(nx).append(ny);
                lineSet.add(sb.toString());
                
                sb = new StringBuilder();
                sb.append(nx).append(ny).append(x).append(y);
                lineSet.add(sb.toString());
                
                x = nx;
                y = ny;
            }
        }
        
        return lineSet.size() / 2;
    }
    
    private static boolean checkIndex(int x, int y) {
        if (x >= -5 && x <= 5 && y >= -5 && y <= 5)
            return true;
        return false;
    }
}

 

1번째 풀이

2번째 풀이

만약 2번째 풀이에서 StringBuilder를 사용하지 않고 String을 사용하면 실행 결과는 다음과 같다.