문제 링크
문제 요약
Lesson 6의 Sorting 에 해당한다.주어진 숫자 배열들 중에서 삼각형을 만들 수 있으면 1을 return하고 그렇지 않으면 0을 return 한다.
삼각형을 만들 수 있는 조건은 P < Q < R 일때,
- P+Q > R
- Q+R > P
- P+R > Q
다음 조건이 성립하면 된다.
더 자세한 내용들은 위의 링크로 이동하여 확인해보길 바란다.
문제 풀이 - 시간 복잡도 O(n*logn)
def solution(A):
# Implement your solution here
#print(A)
A= sorted(A)
#print(A)
for i in range(2,len(A)):
if (A[i-2] + A[i-1]) > A[i]:
return 1
else:
return 0 📌 고려해야할 점
- 우선 오름차순으로 주어진 배열을 sorting 하자.
- P < Q < R 일 때,
P+Q > R이 조건만 고려하면 되는데, R의 경우 가장 큰 수 이기 때문에 나머지 조건들은 당연히 성리해야만 하는 조건이기 때문이다.
🙄 느낀 점
오름차순으로 배열을 정리해주고 삼각형을 만들 수 있는 조건에서 고려하지 않아도 될 조건을 제거해주면 정말 빠르게 풀 수 있다.
