Welcome to My IT World

Valid Triangle Number - LeetCode

문제요약

정수배열이 주어질 때, 삼각형을 만들 수 있는 경우의 수를 구하시오.

입력

1 <= nums.length <= 1000

0 <= nums[i] <= 1000

출력

return int

어떻게 풀까?

1. 삼각형을 만들 수 있는 조건?

삼각형의 세 변의 길이 A, B, C 중에서 한 변의 길이를 뽑았을 때, 나머지 두 변의 길이의 합 보다 작아야 한다.(세 변의 길이 모두 부합하여야 함)

⇒ 이 규칙을 좀 더 간단히 해보면?

⇒ “가장 큰 변의 길이 < 나머지 변의 길이의 합”이 부합한다면, 나머지 2조건은 자동적으로 성립할 것

2. 가장 간단하게 푸는 방법?

정수 배열로 가능한 모든 순열 조합을 뽑아 낸 후에 삼각형 만들 수 있는 조건 검토

⇒ O(3N^3)으로 불가능

3. 시간복잡도는 얼마나 수용 가능한가?

⇒ O(10N^2) 정도까지 수용 가능할 것

4. 좀 더 단순화 해본다면?

제약조건을 걸어서 선택지를 좁혀보자

⇒ 가장 큰 숫자를 고정시키고 해당 숫자를 바탕으로 가능한 나머지 숫자 2개의 조합을 찾기

⇒ for largest_idx in range(len(nums)) : O(N)

⇒ 나머지 숫자를 찾는 방식을 O(N)으로 끝내야 함

⇒ 한 배열을 1번만 돌면서 가능한 두 숫자의 조합을 찾아야 함

⇒ Two Pointers 알고리즘 활용

5. 풀이방식

1. 데이터 전처리 : 배열 오름차순 정렬
2. 배열 뒤에서부터 돌면서 가장 큰 값 고정시켜줌
3. 가장 큰 값이 고정된 상태에서 나머지 두 값 찾기
   1. right값을 기준으로 가능한 최소 left값을 찾아서 그 사이의 값들은 해당 right값과 무조건 조건에 부합한다는 방식으로 찾기

어려웠던 점

1. right값과 left값을 찾음에 있어서도 한 값을 기준으로 생각해야하는데, 처음에 두 개 모두 기준으로 생각해서 혼란이 왔다.
2. 중간에 더 시간복잡도를 줄이기 위해, 어느 하나의 largest_idx에서 가능한 조합이 0개가 나오면 더 이상 확인할 것도 없다는 생각에 곧바로 answer를 return해줬는데, [3, 19, 22, 24, 35, 82, 84] 와 같은 경우도 있을 수 있기 때문에 해당조건은 걸어두면 안 되었다.

느낀점

항상 느끼는 거지만, 코딩테스트 문제는 부지런히 풀어야 익숙해지는 것 같다.

내 코드

#largest_idx 주어질 때, 가능한 조합 찾는 함수
def find_possible_triangles(largest_idx, nums):
    #가장 큰 값의 idx가 2미만이면 return
    if largest_idx < 2: return 0
    #largest 바로 앞 숫자 2개 더해서 largest보다 작으면 바로 0 return
    if nums[largest_idx-1]+nums[largest_idx-2] < nums[largest_idx]:
        return 0
    #가장 큰 값 지정
    largest_num = nums[largest_idx]
    #right, left idx 지정
    right = largest_idx-1
    left = 0
    res = 0
    #left가 right보다 작은 한 반복
    while left < right:
        #left값과 right값이 largest보다 큰 최소 right위치 찾기
        #어느 정도까지 가능할지 확인하기 위해 right값 내리기
        if nums[left] + nums[right] > largest_num:
            #해당 right값과 가능한 left값 조합은 현재 left 사이의 값은 모두 가능(오름차순)
            res += (right - left)
            right -= 1
        #반대의 경우엔 left값을 올려보자
        else: left += 1
    return res

def solution(nums):
    answer =0
    #오름차순 정렬
    nums.sort()

    #뒤에서부터 largest num 고정 후 나머지 두 값 찾기
    for i in range(len(nums)-1, -1, -1):
        res = find_possible_triangles(i, nums)
        answer += res
    return answer

print(solution(nums))