문제

2475. Number of Unequal Triplets in Array

User Accepted:9355
User Tried:10114
Total Accepted:9627
Total Submissions:14508
Difficulty:Easy

You are given a 0-indexed array of positive integers nums. Find the number of triplets (i, j, k) that meet the following conditions:

0 <= i < j < k < nums.length
nums[i], nums[j], and nums[k] are pairwise distinct.
In other words, nums[i] != nums[j], nums[i] != nums[k], and nums[j] != nums[k].
Return the number of triplets that meet the conditions.

Example 1:
  Input: nums = [4,4,2,4,3]
  Output: 3
  Explanation: The following triplets meet the conditions:
  - (0, 2, 4) because 4 != 2 != 3
  - (1, 2, 4) because 4 != 2 != 3
  - (2, 3, 4) because 2 != 4 != 3
  Since there are 3 triplets, we return 3.
  Note that (2, 0, 4) is not a valid triplet because 2 > 0.

Example 2:
  Input: nums = [1,1,1,1,1]
  Output: 0
  Explanation: No triplets meet the conditions so we return 0.

Constraints:
  3 <= nums.length <= 100
  1 <= nums[i] <= 1000

풀이

class Solution:
    def unequalTriplets(self, nums: List[int]) -> int:
        answer = 0
        for i in range(len(nums) - 2):
            for j in range(i + 1, len(nums) - 1):
                for k in range(j + 1, len(nums)):
                    if nums[i] != nums[j] and nums[j] != nums[k] and nums[i] != nums[k]:
                        answer += 1
                
        return answer

사실 이 문제는 조건이 매우 여유롭기 때문에 3중 반복문을 돌려도 시간 안에 통과할 수 있다. 하지만 나는 반복문을 3중으로 돌리면 시간 초과가 날 것이라 지레짐작을 한 나머지 반복문을 2중까지로만 돌려보려고 온갖 애를 쓰다가 결국 이 쉬운 문제를 시간내에 못 풀고 말았다...
그리고 O(N)으로 해결하는 방법도 있다.

여기서 얻은 교훈이랄것 까진 없지만 느낀 점은
1. 우선 조건을 잘 보고
2. 더 좋은 풀이법이 있을 것 같아도 일단 풀 수 있는 문제를 빨리 풀고 시간을 번 다음에 다른 방법을 생각하는 것이 더 낫다는 것이다.