[99클럽 코테 스터디] 16일차 TIL - 배열, Number of Good Pairs

[16일차] 배열

문제: https://leetcode.com/problems/number-of-good-pairs/description/

* 번역: 주어진 정수 배열 nums에 대해, 좋은 쌍(good pairs)를 반환하라. 좋은 쌍이란, i < j 에 대해 nums[i] == nums[j] 을 만족하는 쌍 (i, j)이다. 

Solution

제한 조건에 nums의 길이는 100이하라고 했으므로, 중첩 for문을 사용해도 시간 초과가 날 것 같지 않다고 판단했다.

for 문 자체에서 i < j 조건을 적용해주고, if문으로 값 조건을 확인했다.

class Solution(object):
    def numIdenticalPairs(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        answer = 0
        
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] == nums[j]:
                    answer += 1

        return answer

나다어

나는 다음에 어떻게 풀까

 

• for문, 배열의 인덱스는 문제 풀이에 요긴하게 쓰인다.
• 파이썬은 1초에 2천만번, 2*10^7 번의 연산이 가능하다.
  즉 시간제한이 1초, n = 10^5(10만)일 때 O(N^2)의 알고리즘은 10^10(100억)번 연산이 필요하므로, 시간초과가 나게 된다. 이 경우 O(NlogN)으로 짜야, 16*10^5 번의 연산으로 수행 가능하다. (log100,000 = 약 16)