[프로그래머스] 방의 개수-JAVA

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/49190

코딩테스트 연습 - 방의 개수

 

첫 5단계 문제풀이..

특별한 알고리즘을 요하지 않지만, 방이 만들어지는 조건과 필요한 변수의 타입을 확실하게 지정해주지 않으면 시간초과나 메모리 초과 이슈가 생긴다.

 

 문제 풀이

 

먼저, 화살표가 움직인 범위를 사각형(행렬) 기준으로 구해보자.

arrows 배열을 쭉 돌며 움직인 방향을 변수에 담는다.

오른쪽 방향이 들어간 화살표(오른쪽 위, 오른쪽, 오른쪽 아래)는 width+1

왼쪽 방향이 들어간 화살표(왼쪽 위, 왼쪽, 왼쪽 아래)는 width-1

아래 방향이 들어간 화살표(오른쪽 아래, 아래, 왼쪽 아래)는 height-1

위 방향이 들어간 화살표(왼쪽 위, 위, 오른쪽 아래)는 height+1

또한, 배열을 돌며 가로, 세로의 최대값을 갱신한다.

위 사진의 로직을 통해 선을 그은 모습을 5x6 행렬로 구현하고, 시작 좌표를 구할 수 있다.

 

 

선이 움직인 자리를 그래프로 구현했으니, 이제 본격적인 로직을 수행할 차례다.

방이 생기는 조건을 알아보자.

방이 생기는 조건은 크게 A와 B로 나눌 수 있다.

단, 지나간 경로를 또 지나가는 중복된 상황은 count하면 안된다. 

좌표 (a, b)에 대하여, 해당 좌표가 어떤 점과 선이 연결되어 있는지의 여부를 파악하는 connect 변수를 선언했다.

HashMap<Integer, ArrayList<Integer>> connect = new HashMap<>();

connect의 키값은 좌표를 나타낸다. 점 (1, 3)의 경우 1(x좌표) * 6(width) + 3(y좌표) = 9이다.

키값 9에 value는 점(1, 3)과 연결되어있는 좌표 (0, 3) & (1, 4)이며 Integer로 환산하면 각각 3, 10이다.

 

따라서

A의 경우 : visited[1][3] == true 인 점을 또 방문했고, 이전 (1, 4)에서 처음 온 경로기 때문에 방 개수를 count + 1 한다.

B의 경우 : (3, 5)에서 (2, 4)로 대각선을 그었을 때, (2, 5)나 (3, 4)좌표에서 대각선 여부를 파악한다.

              (3, 4)에서 (2, 5)로 대각선을 교차했고 중복으로 지나간 적이 없으므로 방 개수를 +1 한다.

 

이 여부를 파악하는 방법은 connect<(3, 4)좌표> 키값에 (2, 5) 좌표값이 value로 들어가있으니, 두 점이 연결되어있다는 사실을 알 수 있다.

 

이제 전체적인 로직은 얼추 완성됐다. 단, connect변수를 초기화 할 때 조심해야 할 것이 있다.

예시의 5x6행렬과 같이 범위가 작을 때는 상관없지만, 행렬 범위가 커질 경우 전체 좌표 값을 키값에 모두 넣을 경우 메모리 초과가 발생할 수 있다. (필자가 리트라이 한 이유)

따라서, 선이 지나간 경로만 한정하여 connect 키값을 추가해줘야한다.

 

 

 코드 구현

 

import java.util.ArrayList;
import java.util.HashMap;
class Solution {
    public int solution(int[] arrows) {
        int answer = 0;
        int minW = 0, maxW = 0, minH = 0, maxH = 0;
        int width = 0, height = 0;
        
        for(int i = 0; i < arrows.length; i++) {
            if (arrows[i] == 0 || arrows[i] == 1 || arrows[i] == 7)
                height++;
            maxH = Math.max(maxH, height);
            if (arrows[i] == 3 || arrows[i] == 4 || arrows[i] == 5)
                height--;
            minH = Math.min(minH, height);
            if (arrows[i] == 1 || arrows[i] == 2 || arrows[i] == 3)
                width++;
            maxW = Math.max(maxW, width);
            if (arrows[i] == 5 || arrows[i] == 6 || arrows[i] == 7)
                width--;
            minW = Math.min(minW, width);
        }
        int x = maxH, y = -minW; //원점의 위치
        width = maxW - minW + 1;
        height = maxH - minH + 1;
        
        //좌표 (a,b)가 어떤 좌표와 연결되어있는지
        HashMap<Integer, ArrayList<Integer>> connect = new HashMap<>();
        connect.put(x*width+y, new ArrayList<>());
        
        boolean[][] visited = new boolean[height][width];
        visited[x][y] = true; //시작점은 이미 지나간거니까
        for(int i = 0; i < arrows.length; i++) {
            int prev_x = x, prev_y = y;
            
            if (arrows[i] == 0 || arrows[i] == 1 || arrows[i] == 7)
                x -= 1;
            if (arrows[i] == 3 || arrows[i] == 4 || arrows[i] == 5)
                x += 1;
            if (arrows[i] == 1 || arrows[i] == 2 || arrows[i] == 3)
                y += 1;
            if (arrows[i] == 5 || arrows[i] == 6 || arrows[i] == 7)
                y -= 1;
            // //방문하지 않은 점이면 Map에도 해당 점 원소 추가
            if (!connect.containsKey(x*width+y)) {
                connect.put(x*width+y, new ArrayList<>());
            }
            //해당 점을 한번 더 방문하고, 이전에 그어지지 않았던 선이면
            if (visited[x][y] == true) { 
                if (connect.get(x*width+y).contains(prev_x*width+prev_y) == false)
                    answer++;
            }
            //대각선 검사 : 교차할때 방 만들어짐, 단 이미 그었던 선은 안됨.
            if (connect.get(x*width+y).contains(prev_x*width+prev_y) == false) {
                if (arrows[i] == 7 && connect.containsKey((x+1)*width+y)) 
                    if (connect.get((x+1)*width+y).contains(x*width+(y+1)) == true) 
                            answer++;
                if (arrows[i] == 5 && connect.containsKey((x-1)*width+y)) 
                    if (connect.get((x-1)*width+y).contains(x*width+(y+1)) == true)
                            answer++;
                if (arrows[i] == 3 && connect.containsKey((x-1)*width+y)) 
                    if (connect.get((x-1)*width+y).contains(x*width+(y-1)) == true)
                            answer++;
                if (arrows[i] == 1 && connect.containsKey(x*width+(y-1)))
                    if (connect.get(x*width+(y-1)).contains((x+1)*width+y) == true)
                            answer++;
            }
            if (visited[x][y] == false) {
                visited[x][y] = true;
            }
            // 점 연결
            connect.get(x*width+y).add(prev_x*width+prev_y);
            connect.get(prev_x*width+prev_y).add(x*width+y);
        }
        return answer;
    }
}

도합 1박2일이 걸려서 푼 문제..