gilbutitbook / 080337 Goto Github PK

숫자가 모두 채워진 triangle 을 기반으로 1차원 배열에 옮길 때
triangle[i][j] 의 값이 0이 아닌지 체크 하지 않아 초기 선언한 result 배열의 사이즈보다 큰 index 값을 할당하려고 하여
out of bounds 오류가 발생합니다.
코드 위치 : https://github.com/gilbutITbook/080337/blob/main/3%EC%9E%A5/%EC%82%BC%EA%B0%81_%EB%8B%AC%ED%8C%BD%EC%9D%B4.java#L43

따라서 아래와 같이 if 문을 추가해야 할 것 같습니다.
if (triangle[i][j] != 0) { result[index++] = triangle[i][j]; }

기존 소스코드

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public double getSlope(int x1, int y1, int x2, int y2) {
        return (double) (y2 - y1) / (x2 - x1);
    }

    public int solution(int[][] dots) {
        Set<Double> slopes = new HashSet<>();
        for (int i = 0; i < dots.length; i++) {
            for (int j = i + 1; j < dots.length; j++) {
                double slope = getSlope(dots[i][0], dots[i][1],
                        dots[j][0], dots[j][1]);
                if (slopes.contains(slope)) {
                    return 1;
                }
                slopes.add(slope);
            }
        }
        return 0;
    }
}

상황

책 출판 이후 테스트케이스가 수정되어 해당 코드로 제출시 일부 테스트 케이스에 대해 틀리게 되었습니다.

원인

각 좌표를 [a, b, c, d]로 대응했을 때
해당 코드는 아래의 6가지 경우에 대해 하나라도 기울기가 같다면 1를 반환하고 종료됩니다.
그러나 해당 경우에 한 점이 두 번 사용되는 등 논리적 오류가 있을 수 있습니다.
ex) [a, b]의 기울기와 [a, c]의 기울기가 같다면? 종료되는데, 점 d는 혼자 쓸쓸하게... 😢

[a, b]
[a, c]
[a, d]
[b, c]
[b, d]
[c, d] 

해당 문제에서 요구하는 가지 수는 실제로는 3가지 입니다.

[a, b] 를 고르면 [c, d]와 만 기울기 비교 <-> [c, d]를 고르면 [a, b]와 기울기 비교;
[a, c] 를 고르면 [b, d]와 만 기울기 비교 <->[b, d]를 고르면 [a, c]와 기울기 비교 
[a, d] 를 고르면 [b, c]와 만 기울기 비교 <->  [b, c]를 고르면 [a, d]와 기울기 비교

예를 들어 [[1, 2], [3, 4], [5, 6], [99, 50]] 이 있다고 할 때

[[1, 2], [3,4]] 기울기 : 1 <-> [[5, 6], [99,50]] 기울기 22/47   -> F
[[1, 2], [5, 6]] 기울기 : 1 <-> [[3, 4], [99, 50]] 기울기 23/48 -> F
[[1, 2], [99, 50]] 기울기 : 24/49 <-> [[3, 4], [5, 6]] 기울기 1 -> F

로 0을 반환해야하지만

현재 코드의 로직에서는

[1, 2], [3, 4] 기울기 1
[1, 2], [5, 6] 기울기 1  

바로 종료되게 됩니다.
그러나 주어진 문제 상황에서 두 점 [1, 2], [3, 4]를 잇고 [5, 6]에도 이으면 모두 한 평행선에 있긴 하지만
점[1, 2]를 두번이나 사용해서 존재할 수 없는 경우입니다. [1, 2], [3, 4] <-> [1, 2], [5, 6] X