[프로그래머스] LV.0 순서쌍의 개수 / 파이썬(Python)

문제 설명

순서쌍이란 두 개의 숫자를 순서를 정하여 짝지어 나타낸 쌍으로 (a, b)로 표기합니다. 자연수 n이 매개변수로 주어질 때 두 숫자의 곱이 n인 자연수 순서쌍의 개수를 return하도록 solution 함수를 완성해주세요.

제한사항

1 ≤ n ≤ 1,000,000

풀이 1

def solution(n):
    answer = 0
    for i in range(1, n+1):
        j = n % i
        if j == 0:
            answer += 1
        else:
            continue
    return answer

• 답은 맞았는데, 몇몇 케이스에서 시간이 꽤 걸림
  테스트 1 〉 통과 (0.00ms, 10.1MB)
  테스트 2 〉 통과 (0.00ms, 10.1MB)
  테스트 3 〉 통과 (7.78ms, 10.1MB)
  테스트 4 〉 통과 (0.00ms, 10.3MB)
  테스트 5 〉 통과 (5.75ms, 10.2MB)
  테스트 6 〉 통과 (59.47ms, 10.1MB)
  테스트 7 〉 통과 (0.00ms, 10.2MB)
  테스트 8 〉 통과 (0.01ms, 10.1MB)
  테스트 9 〉 통과 (62.75ms, 10.2MB)
  테스트 10 〉 통과 (83.92ms, 10.2MB)

• idea
  제곱수를 제외하면 같은 원소를 가진 순서쌍이 2개씩이니까, 연산량을 거의 절반으로 줄여볼 수 있지 않을까?

풀이 2

• idea
  제곱근으로 이루어진 순서쌍은 1개, 그 외의 순서쌍은 2개씩 있다는 점을 이용했다

def solution(n):
    answer = 0
    for i in range(1, int(n**(1/2))+1):
        if i*i == n:
            answer += 1
        elif n % i == 0:
            answer += 2
        else:
            continue
    return answer

• 풀이 1에 비하면 시간이 확연히 줄었다
  테스트 1 〉 통과 (0.00ms, 10.1MB)
  테스트 2 〉 통과 (0.01ms, 10.2MB)
  테스트 3 〉 통과 (0.04ms, 10.2MB)
  테스트 4 〉 통과 (0.02ms, 10.3MB)
  테스트 5 〉 통과 (0.04ms, 10.1MB)
  테스트 6 〉 통과 (0.10ms, 10.1MB)
  테스트 7 〉 통과 (0.01ms, 10.3MB)
  테스트 8 〉 통과 (0.02ms, 10.2MB)
  테스트 9 〉 통과 (0.10ms, 10.1MB)
  테스트 10 〉 통과 (0.10ms, 10.1MB)

• 하나 더 깨달은 점은, 동일한 변수를 게속 쓰는 게 아니면서, 코드 가독성에 무리가 없다면 변수를 따로 만들지 않고 바로 사용하는 편이 더 빠르다.
  근데 코테볼 때는 속도가 중요하니까 그렇게 짜겠는데, 실제로는 0.1ms 더걸려도 변수 따로 선언해주는 게 좋지 않을까?

• (수정) 다시 보니까, n%i 조건을 먼저 쓰고, elif i*i ==n 을 쓰는 게 더 빠를 것 같다.
  제곱근은 어차피 하나 밖에 없는 데 굳이 먼저 훑고 지나가게 만들 필요가 없다고 생각된다.

다른 사람 풀이 1

def solution(n):
    answer = 0
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            answer += 2

            if i * i == n:
                answer -= 1

    return answer

• 내 풀이2와 유사한데, 전체적으로 2씩 더하고 제곱근이면 1을 빼도록 만드셨다.
  대체적으로 이러한 idea 를 사용한 풀이가 많았다.

다른 사람 풀이 2

def solution(n):
    return len(list(filter(lambda v: n % (v+1) == 0, range(n))))