[99클럽 코테스터디 2기][Python/비기너] 여덟번째 문제 : Count Pairs Whose Sum is Less than Target

오늘의 주제도 "정렬"
[Count Pairs Whose Sum is Less than Target]

문제

입력과 출력

코드

class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        cnt=0
        for i in range(len(nums)-1):
            for j in range(i+1,len(nums)):
                sum=nums[i]+nums[j]
                if sum<target:
                    cnt+=1
        return cnt

알고리즘
#먼저, target보다 작은 합의 갯수를 세어줄 cnt 변수를 선언
#0번째 원소부터 자신을 제외한 다른 원소들과 합해보기 위해
#for문은 0부터 배열 끝-1까지, i다음의 원소부터 배열끝까지
#두 개를 써준다.
#sum 변수에 두 원소들을 더한 값을 담고
#이 sum이 target보다 작으면 cnt를 1씩 증가시킨다
#cnt를 리턴해주면 완료

시행착오
문제가 비교적 쉬워 빨리 풀긴 했지만, 처음에 j의 범위를 1부터 배열끝까지로 설정했더니 2번째 example에서 통과되지 않았다.
다시 생각해보니 무조건 1부터 다시 돌면 안되고 i다음부터 반복문으로 비교해야한다는 생각이 들어 범위를 i+1~배열끝까지로 변경해주었다.
바로 통과되었고, run time은 49ms여서 개선이 필요하다고 생각했다.

지금까지 풀어본 문제 중 검색을 한번도 하지 않고 푼 최초의 문제였다!
일주일정도 매일 코딩 문제를 풀고 그날의 회고도 작성하다 보니, 코딩을 하는 것이 좀 더 자연스러워 지고있다.
지금은 시험기간이라 더 많은 문제를 풀지는 못하지만, 시험이 끝나면 스터디 문제외에 다른 문제도 풀어보려 한다.

Something new I learned

• 시간복잡도를 고려해야 할 것 같다! 시간복잡도가 뭔지,, 어떻게 줄이면 될지

FeedBack
셀프세션 발표하신 분이 처음에 짜셨던 코드를 보여주셨는데, 내가 짠 코드와 같았다.
그러나 발표자분은 시간 복잡도가 높고 다른 풀이가 더 좋을것 같다는 생각을 해서 sort를 쓰는 방법을 시도하셨다고 한다.

띄워주신 코드

nums.sort()
cnt=0
i=0
j=len(nums)-1
while i<j:
	if nums[i]+nums[j]<target:
		cnt+=j-i
		i+=1
	else:
		j-=1
return cnt

코드를 다양하게 참고하셔서 다방면으로 시도하시는 모습을 보고, 나도 내 코드만 하지말고 더 참고해서 시간복잡도도 낮추고 효율성이 더 높은 코드를 완성해내는 연습을 해야겠다고 생각했다.

-> 개발자님 피드백
첫번째 코드도 배열이 크지않아 코딩테스트에서는 이렇게 답해도 문제없지만, 시간복잡도를 고려하여 풀다보면 훨씬 더 좋은 알고리즘을 짤 수 있을 것이라는 의견

To do List

• 시간 복잡도란?
• 내 코드외와 타 코드가 어떤 차이가 있는지 비교해보기