[1711] 직각삼각형

https://www.acmicpc.net/problem/1711

1711번: 직각삼각형

브루트포스로 접근한 문제다.

 

풀이

들어오는 좌표 중 3개를 선택하는 조합 반복문을 생성. 피타고라스의 정리를 사용해 직각 삼각형인지 판별하면 된다.

단 해당 문제에서 흥미로웠던 점은 세 점 A, B, C의 조합에서 나온 3가지의 선분(AB, BC, AC) 중 가장 긴 선분을 찾아내는 부분에서 시간초과가 났다.

 

처음에는 단순히 3개의 선분의 길이를 배열에 담아낸 뒤 내림차순 정렬하여 (0번 원소 == 1번 원소 + 2번 원소) 조건문으로 판별하였으나, 시간초과가 발생. 

func isRightTriangle(a:(Int,Int),b:(Int,Int),c:(Int,Int)) -> Bool{
    let AB = ((a.0-b.0)*(a.0-b.0)) + ((a.1-b.1)*(a.1-b.1))
    let AC = ((a.0-c.0)*(a.0-c.0)) + ((a.1-c.1)*(a.1-c.1))
    let BC = ((b.0-c.0)*(b.0-c.0)) + ((b.1-c.1)*(b.1-c.1))
    
    let tmp = [AB,AC,BC].sorted(by: >)
    return tmp[0]==tmp[1]+tmp[2] ? true:false
}

 

이때부터 조금 헤맸다. 시간복잡도를 계산해 보면 입력좌표는 최대 1500개가 입력. 1500C3 = 561,375,500 여기서 각 조합마다 정렬이 이루어지는데, Swift 배열의 정렬 함수 시간복잡도는 0(N)이므로 대략 16억 번의 수행이 이루어진다. 보통 알고리즘 문제를 풀 때 러프하게 1초당 1억 번의 연산으로 계산하게 되는데, 5초의 시간은 턱없이 부족한 시간인 것이다.

 

그러다 문득 배열을 생성하고 정렬하는 것보단 비트연산이 더욱 빠르겠다는 생각이 들어 아래와 같이 수정하였더니 통과하였다.

func isRightTriangle(a:(Int,Int),b:(Int,Int),c:(Int,Int)) -> Bool{
    let AB = ((a.0-b.0)*(a.0-b.0)) + ((a.1-b.1)*(a.1-b.1))
    let AC = ((a.0-c.0)*(a.0-c.0)) + ((a.1-c.1)*(a.1-c.1))
    let BC = ((b.0-c.0)*(b.0-c.0)) + ((b.1-c.1)*(b.1-c.1))

//  let tmp = [AB,AC,BC].sorted(by: >)
//  return tmp[0]==tmp[1]+tmp[2] ? true:false

    let res = (AB==AC+BC) || (AC == AB+BC) || (BC==AB+AC)
    return res ? true:false
}

 

정답 코드