[Summer/Winter Coding(~2018)] 방문 길이 (java)

문제풀이

 

set 을 이용 하는 데 많은 공부가 되었던 문제이다.

원래 4차원 배열을 이용하여 저장해도 됐지만 set을 사용하고 싶어 사용하다가 자연스레 하나 배워간 문제이다.

 

먼저, set을 사용할때 key가 객체일경우 객체안의 값이아니라 객체자체를 비교하게 된다 그래서 같은객체가 아니라면 값이 같아도 다르게 판단한다.

 

그래서 hashcode를 오버라이딩하여 수정 할 필요가있다. 객체안의 값이 같은경우 같은 해시코드를 반환하게 해주면 객체 값을 가지고 비교할 수 있다.

 

그리고 문제풀 때 주의할점이 방향성이 없는 선이라서 나같은 경우에는 양방향으로 set에 다추가해준 뒤 /2 를 통해 길의 개수를 판단해 주었다.

 

소스코드

import java.util.HashSet;
import java.util.Set;
 
public class Programmers49994 {
    static Set<Path> pathSet = new HashSet<>();
 
    static int dirRow[] = {-1,0,0,1};
    static int dirCol[] = {0,-1,1,0};
    public static int solution(String dirs) {
        int answer = 0;
        int x = 0;
        int y = 0;
        Path path1 = null;
        Path path2 = null;
        for(int i=0;i<dirs.length();i++){
            int dir = getDir(dirs.charAt(i));
            int nextX = x + dirRow[dir];
            int nextY = y + dirCol[dir];
 
            if(!isRange(nextX, nextY))
                continue;
            path1 = new Path(x,y,nextX,nextY);
            path2 = new Path(nextX,nextY,x,y);
            x = nextX;
            y = nextY;
 
            if(!pathSet.contains(path1)){
                pathSet.add(path1);
                pathSet.add(path2);
            }
        }
        answer = pathSet.size()/2;
        return answer;
    }
 
    public static boolean isRange(int nextX, int nextY) {
        return nextX>=-5&&nextY>=-5 && nextX<=5 &&nextY<=5;
    }
 
    private static int getDir(char c) {
        switch (c){
            case 'U':
                return 0;
            case 'L':
                return 1;
            case 'R':
               return 2;
            case 'D':
                return 3;
            default:
                return -1;
        }
    }
 
    static class Path {
        int curX,curY,nextX,nextY;
 
        public Path(int curX, int curY, int nextX, int nextY) {
            this.curX = curX;
            this.curY = curY;
            this.nextX = nextX;
            this.nextY = nextY;
        }
 
        public void setReverse(){
            int tempX = curX;
            int tempY = curY;
            curX = nextX;
            curY = nextY;
            nextX = tempX;
            nextY = tempY;
        }
 
        public int getCurX() {
            return curX;
        }
 
        public int getCurY() {
            return curY;
        }
 
        public int getNextX() {
            return nextX;
        }
 
        public int getNextY() {
            return nextY;
        }
 
        @Override
        public int hashCode() {
            return Integer.toString(curX).hashCode()+ Integer.toString(curY).hashCode() + Integer.toString(nextX).hashCode()+ Integer.toString(nextY).hashCode();
        }
 
        @Override
        public boolean equals(Object obj) {
            if(obj instanceof Path){
                Path path = (Path) obj;
                return path.getCurX()==curX && path.getCurY() ==curY && path.getNextX() ==nextX && path.getNextY()==nextY;
            }
            return false;
        }
 
 
    }
 
    public static void main(String[] args) {
        String dirs = "ULURRDLLU";
        int result = solution(dirs);
        System.out.println(result);
    }
}
 

 

 

문제 링크 : programmers.co.kr/learn/courses/30/lessons/49994

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