https://www.acmicpc.net/problem/1711
1711번: 직각삼각형
첫째 줄에 점의 개수 N(3 ≤ N ≤ 1,500)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 좌표값은 절댓값이 1,000,000,000을 넘지 않는 정수이며, 주
www.acmicpc.net
브루트포스로 접근한 문제다.
풀이
들어오는 좌표 중 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
}
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [14719] 빗물 (0) | 2023.06.02 |
|---|---|
| [5719] 거의 최단 경로 (0) | 2023.04.30 |
| [16169] 수행시간 (0) | 2023.04.11 |
| [24526] 전화 돌리기 (0) | 2023.04.05 |
| [14907] 프로젝트 스케줄링 (0) | 2023.04.03 |
