[프로그래머스 , JAVA, LV.0] 평행

목차

문제 설명

점 네 개의 좌표를 담은 이차원 배열  dots가 다음과 같이 매개변수로 주어집니다.

• [[x1, y1], [x2, y2], [x3, y3], [x4, y4]]

주어진 네 개의 점을 두 개씩 이었을 때, 두 직선이 평행이 되는 경우가 있으면 1을 없으면 0을 return 하도록 solution 함수를 완성해보세요.

---

 

제한사항

• dots의 길이 = 4
• dots의 원소는 [x, y] 형태이며 x, y는 정수입니다.
  • 0 ≤ x, y ≤ 100
• 서로 다른 두개 이상의 점이 겹치는 경우는 없습니다.
• 두 직선이 겹치는 경우(일치하는 경우)에도 1을 return 해주세요.
• 임의의 두 점을 이은 직선이 x축 또는 y축과 평행한 경우는 주어지지 않습니다.

 

 

dots	result
[[1, 4], [9, 2], [3, 8], [11, 6]]	1
[[3, 5], [4, 1], [2, 4], [5, 10]]	0

 

class Solution {
    public int solution(int[][] dots) {
        // 직선의 기울기를 비교하여 평행 여부 확인
        double slope1 = getSlope(dots[0], dots[1]); // 첫 번째 점과 두 번째 점 사이 기울기
        double slope2 = getSlope(dots[2], dots[3]); // 세 번째 점과 네 번째 점 사이 기울기

        double slope3 = getSlope(dots[0], dots[2]); // 첫 번째 점과 세 번째 점 사이 기울기
        double slope4 = getSlope(dots[1], dots[3]); // 두 번째 점과 네 번째 점 사이 기울기

        double slope5 = getSlope(dots[0], dots[3]); // 첫 번째 점과 네 번째 점 사이 기울기
        double slope6 = getSlope(dots[1], dots[2]); // 두 번째 점과 세 번째 점 사이 기울기

        // 평행한 경우가 있는지 검사
        if (slope1 == slope2 || slope3 == slope4 || slope5 == slope6) {
            return 1; // 평행
        }
        return 0; // 평행하지 않음
    }

    // 두 점 사이의 기울기를 계산하는 메서드
    private static double getSlope(int[] dot1, int[] dot2) {
        if (dot1[0] == dot2[0]) { // x 좌표가 같으면 기울기가 무한대
            return Double.MAX_VALUE;
        }
        return (double) (dot2[1] - dot1[1]) / (dot2[0] - dot1[0]);
    }

}

1. 문제 이해

주어진 4개의 점 중에서 두 개씩 점을 이었을 때, 두 직선의 기울기가 같은 경우를 찾아야 한다. 기울기가 같다면 그 직선들은 평행이다.

 

2. 알고리즘 접근 방식

1) 두 점을 이용해 기울기 계산

기울기 공식은 다음과 같다:

여기서,

• 두 점의 xxx 좌표가 같으면 기울기는 무한대이다. (수직선의 경우)

예외 처리: x2−x1=0x_2 - x_1 = 0x2​−x1​=0이면 Double.MAX_VALUE를 기울기로 설정한

 

2) 가능한 모든 직선의 기울기 계산

4개의 점이 주어졌을 때 가능한 직선은 6가지이다.
서로 다른 점을 두 개씩 선택했을 때:

• 점 1과 점 2: slope1
• 점 3과 점 4: slope2
• 점 1과 점 3: slope3
• 점 2와 점 4: slope4
• 점 1과 점 4: slope5
• 점 2와 점 3: slope6

---

3) 기울기 비교를 통해 평행 여부 확인

평행 조건은 다음과 같다:

• 두 직선의 기울기가 같으면 평행이다.
  즉,
  if (slope1 == slope2 || slope3 == slope4 || slope5 == slope6)
  이 조건 중 하나라도 만족하면 1을 반환한다.

---

3. 코드 동작 과정

1. 기울기 계산 함수 (getSlope)
   • 두 점 사이의 기울기를 계산하고 xxx 좌표가 같을 경우 Double.MAX_VALUE를 반환한다.
2. 모든 가능한 직선의 기울기 계산
   • 6가지 조합으로 두 점을 연결해 기울기를 구한다.
3. 기울기 비교
   • 6가지 직선 중에서 두 기울기가 같은 경우가 있는지 검사한다.
4. 결과 반환
   • 평행한 직선이 있다면 1을 반환하고, 없다면 0을 반환한다.

---

4. 시간 복잡도 분석

1. 가능한 직선의 조합은 6가지이다.
2. 각 기울기 계산은 **O(1)**이다.
3. 따라서 전체 시간 복잡도는 **O(1)**으로 매우 효율적이다.