[프로그래머스] 방문 길이 (java)

코딩테스트 연습 - 방문 길이 | 프로그래머스 (programmers.co.kr)

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

어떻게 생각하고 문제를 풀었는가?

좌표에 대한 기억이 아닌 이동한 길을 기억해야 하는 문제이므로 지나온 길을 저장하고, 중복 확인을 하여 처음 걸어본 길의 길이를 반환할 수 있다고 생각하였습니다.

코드

import java.util.*;
class Solution {
    public int solution(String dirs) {
        int x=0,y=0;
        HashSet<Path> set = new HashSet<>();
        for(char c : dirs.toCharArray()){
            if(c=='U' && y<5)  {
                set.add(new Path(x,y,x,y+1));
                y=y+1;
            }
            if(c=='D' && y>-5){
               set.add(new Path(x,y,x,y-1)); 
                y=y-1;
            }  
            if(c=='L' && x>-5){
                set.add(new Path(x,y,x-1,y));
                x=x-1;
            }  
            if(c=='R' && x<5){
               set.add(new Path(x,y,x+1,y)); 
                x=x+1;
            }
        }
        return set.size();
    }
    class Path{
        int prevX, prevY, curX, curY;
        Path(int prevX, int prevY, int curX, int curY){
            this.prevX = prevX;
            this.prevY = prevY;
            this.curX = curX;
            this.curY = curY;
        }
        public boolean equals(Object obj){
            if(obj instanceof Path){
                Path B = (Path) obj;
                if(this.prevX==B.prevX && this.prevY==B.prevY && this.curX==B.curX && this.curY==B.curY){
                    return true;
                }
                if(this.prevX==B.curX && this.prevY==B.curY && this.curX==B.prevX && this.curY==B.prevY){
                    return true;
                }
            }
            return false;
        }
        public int hashCode(){
            return prevX+prevY+curX+curY;
        }
    }
} 

HashSet은 중복을 허용하지 않는 컬렉션입니다. add함수로 원소 삽입시 equals와 hashCode를 호출하여 인스턴스를 비교하고 중복이라고 판단된 경우 삽입을 중지합니다.

클래스 Path에 이전 좌표와 이동한 후 좌표를 저장하여 지나온 길을 표현하였고 이를 HashSet의 원소로 추가함으로서 테스트를 통과할 수 있습니다.

클래스에서 equals함수가 재정의되지 않은 경우 인스턴스 값을 비교하기 때문에 멤버변수가 같더라도 다른 인스턴스로서 false가 반환되어집니다.

진행방향이 같을 경우와 반대일 경우에도 지나온 길은 중복되므로 이를 고려하여 equals함수를 작성하였습니다.

또한, hashCode함수로 hash값을 반환하는데 있어 equals값이 true일 경우 hashCode값도 true로 반환되어야 같은 인스턴스로 취급되어지므로 해당 함수도 재정의가 필요합니다.

HashSet에서 equals 결과가 false일 경우 hashCode 함수는 실행되지 않으므로 같은 멤버변수들을 가졌을 때 같은 hash값이 반환될 수 있도록 멤버변수들을 모두 더한 값으로 hash값을 생성하였습니다.