[ 프로그래머스 ] 평행

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

프로그래머스

 

 

👨‍💻 접근 방식

4개의 좌표 중 2개의 좌표를 선택하여 기울기 lean1 을 계산하고 선택되지 않은 좌표들로 기울기 lean2 를 계산하려고 하였다. 이 때 백트래킹을 이용한 조합을 구현하여 2개의 좌표를 선택하는 경우의 수를 구하려고 하였다.

 

📄 4개의 좌표 중 2개를 선택하는 경우의 수를 구하는 코드

static void comb( int[][] dots, boolean[] visited, int depth , int n , int r ){        
    if( r == 0 ){
        chkParallel( dots, visited );	// 두 선분의 기울기를 비교하는 함수
    }
    for( int i = depth ; i < n ; i++ ){
        visited[i] = true;
        comb( dots, visited, i + 1 , n , r - 1 );
        visited[i] = false;
    }
}

 

📄 두 선분의 기울기를 구하여 비교하는 코드

static void chkParallel( int[][] dots, boolean[] visited ){
        int x1 = Integer.MAX_VALUE;
        int x2 = Integer.MAX_VALUE;
        int y1 = Integer.MAX_VALUE;
        int y2 = Integer.MAX_VALUE;
        for( int i = 0 ; i < 4 ; i++ ){
            if( visited[i] ){
                if( x1 == Integer.MAX_VALUE ) {
                    x1 = dots[i][0];
                    y1 = dots[i][1];
                }
                else{
                    x1 -= dots[i][0];	// 두 좌표의 x 사이 거리
                    y1 -= dots[i][1];	// 두 좌표의 y 사이 거리
                }
            } else {
                if( x2 == Integer.MAX_VALUE ) {
                    x2 = dots[i][0];
                    y2 = dots[i][1];
                }
                else{
                    x2 -= dots[i][0];	// 두 좌표의 x 사이 거리
                    y2 -= dots[i][1];	// 두 좌표의 y 사이 거리
                }
            }
        }
        double lean1 = y1 / (double)x1;
        double lean2 = y2 / (double)x2;
        if( lean1 == lean2 ) answer = 1;  // 두 선분의 기울기가 같으면 answer = 1
        else if( x1 == 0 && x2 == 0) answer = 1;	// 예외: 기울기가 무한대일 경우
    }

 

 

❗ 테스트 케이스 3번 실패 처리 코드

위 코드에서 마지막 줄의 코드를 보면 다음과 같다.

else if( x1 == 0 && x2 == 0) answer = 1;

이 한 줄 코드를 작성하기 전에 테스트 케이스 3번만 실패가 떠서 어떤 예외가 있을까 생각했는데

바로 두 선분이 모두 기울기가 무한대일 경우, 즉 두 좌표의 x 사이 거리가 0 인 두 선분의 경우( y축에 평행한 경우 )이다. lean1 과 lean2 가 모두 무한대가 되면 서로 값을 비교할 수 없기 때문에 위의 조건문을 추가로 생성해서 따져야 했다.

 

📄 전체 코드

class Solution {
    static int answer = 0;
    public int solution(int[][] dots) {        
        boolean[] visited = new boolean[ 4 ];
        comb( dots, visited , 0 , 4 , 2 );
        return answer;
    }    
    static void comb( int[][] dots, boolean[] visited, int depth , int n , int r ){        
        if( r == 0 ){
            chkParallel( dots, visited );
        }
        for( int i = depth ; i < n ; i++ ){
            visited[i] = true;
            comb( dots, visited, i + 1 , n , r - 1 );
            visited[i] = false;
        }
        
    }
    
    static void chkParallel( int[][] dots, boolean[] visited ){
        int x1 = Integer.MAX_VALUE;
        int x2 = Integer.MAX_VALUE;
        int y1 = Integer.MAX_VALUE;
        int y2 = Integer.MAX_VALUE;
        for( int i = 0 ; i < 4 ; i++ ){
            if( visited[i] ){
                if( x1 == Integer.MAX_VALUE ) {
                    x1 = dots[i][0];
                    y1 = dots[i][1];
                }
                else{
                    x1 -= dots[i][0];
                    y1 -= dots[i][1];
                }
            } else {
                if( x2 == Integer.MAX_VALUE ) {
                    x2 = dots[i][0];
                    y2 = dots[i][1];
                }
                else{
                    x2 -= dots[i][0];
                    y2 -= dots[i][1];
                }
            }
        }
        double lean1 = y1 / (double)x1;
        double lean2 = y2 / (double)x2;
        if( lean1 == lean2 ) answer = 1;  
        else if( x1 == 0 && x2 == 0) answer = 1;
    }
}

 

💭 Review

코딩테스트 연습을 좀 오래 쉬었다가 오랜만에 알고리즘 문제를 풀게 되었고, 예전의 감을 다 잃었을 것 같아서 쉬운 문제로 감 좀 찾으려고 프로그래머스에서 Lv0 난이도의 이 문제를 골랐는데, 내가 생각한 Lv0의 문제가 아닌 느낌... 내가 못해진 건지 모르겠지만 처음에는 이렇게까지 코드가 길 필요가 없는 문제일 줄 알았다.. 좀 더 깔끔한 풀이가 있을 것이라 생각된다.