우선, 입력 조건에 x<y가 있으므로 min(a,b), max(a,b)는 할 필요가 없습니다.
그리고 위 코드의 시간복잡도도 O(n^2)으로 문제를 풀 수 없습니다.
input
3 1 3 8 10 2 9
output : 10
answer : 9
2170번 - 선 긋기
우선, 입력 조건에 x<y가 있으므로 min(a,b), max(a,b)는 할 필요가 없습니다.
그리고 위 코드의 시간복잡도도 O(n^2)으로 문제를 풀 수 없습니다.
input
3 1 3 8 10 2 9
output : 10
answer : 9
댓글을 작성하려면 로그인해야 합니다.
chickenchickenlove 3년 전
코드의 내용은 다음과 같습니다.
1. 입력 받은 좌표를 넣을 때, 다음과 같은 의사 결정을 합니다.
(a) answer_list라는 좌표 모음집에 있는 모든 좌표와 a,b라는 곳에 저장된 좌표가 만나지 않으면 a,b는 answer_list에 넣습니다.
좌표가 만나지 않는 것을 비교하는 방법은 다음과 같습니다.
(한 좌표가 a,b 다른 좌표가 c,d라고 했을 때, min(a,b) < max(a,b) < min(c,d) < max(c,d) 거나 min(a,b) < max(a,b) < min(c,d) < max(c,d) 이면 각 좌표가 그리는 선분이 만나지 않기 때문에, 이들은 연결되지 않습니다)
(b) answer_list라는 좌표 모음집에 있는 좌표 중 하나라도 만나는 것이 있다면, 그 인덱스를 뒤로 넘겨주어 값을 수정합니다.
수정하는 방법은 다음과 같습니다.
두 좌표의 4개의 점 중 가장 최소값과 최대값을 뽑아 각각 채워넣습니다.
예를 들어 (1,5) , (3,-1)이 있었다면, 4개 점 중 가장 작은 -1, 그리고 가장 큰 5만 answer_list에 남게 됩니다.
위와 같은 로직으로 연결되는 것들을 짜보았는데... 자꾸 틀렸다고 나오네요..
여러 반례들을 쳐봤으나... 안되네요 ㅠ.ㅠ... 도움 주시면 너무 감사하겠습니다.