[프로그래머스][PYTHON] Lv. 0 합성수 찾기

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/120846

프로그래머스

 

내 풀이

def solution(n):
    # 1과 2는 합성수X, 2를 제외한 모든 짝수는 합성수
    answer = 0
    for i in range(n):
        if (i+1) != 2 and (i+1) % 2 == 0:
            # i+1이 2가 아닌 모든 짝수일 경우 answer을 +1 한다. 
            answer += 1
            
        elif (i+1) != 1 and (i+1) % 2 != 0:
            # i+1이 1이 아닌 모든 홀수를 체크한다. 
            measure = 0 # 각 숫자의 약수를 담을 measure
            for j in range(i):  # 각 숫자보다 작은 수들을 순회하며..
                if (i+1)/(j+1) == int((i+1)/(j+1)):
                # 값을 나눈 것이 소숫점없이 떨어지는 수(약수)이면 measure을 증가시킨다. 
                    measure += 1
                    # 약수의 개수가 2개가 이상이면(자기자신도 약수이므로 이는 제외한다) 
                    # 합성수로 판단하여 answer을 하나 증가시키고, for문을 멈춘다. 
                    if measure >= 2:
                        answer += 1
                        break
    return answer

 

다른 사람 풀이

[코드 1]

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

 

위는 나랑 비슷한 코드이다. 그러나 나는 짝수와 홀수를 나눠 홀수인 숫자들만 약수의 개수를 판단했고, 

위의 풀이는 모든 숫자들의 약수의 개수를 세었다는 차이점이 있다. 훨씬 보기 간편하고 좋은 것 같긴 하다! 

 

 

[코드 2]

def solution(n):
    output = 0
    for i in range(4, n + 1):
        for j in range(2, int(i ** 0.5) + 1):
            if i % j == 0:
                output += 1
                break
    return output

 

이는 4부터 for문을 도는 방법이다. 왜냐하면 어차피 1, 2, 3은 합성수가 아니기 때문이다. 

따라서 4부터 n까지 순회하고,,,

각 값의 약수를 체크한다. 이때, 2부터 i의 제곱근까지의 범위까지 순회를 한다. 

왜냐하면 어떤 수의 약수는 그 수의 제곱근을 넘어가지 않기 때문이다. 

즉, i가 소수가 아니라면 i의 약수 중 하나는 반드시 i의 제곱근보다 작거나 같아야 한다. 

 

예를 들어, 

i가 4라면 4의 약수는 1, 2, 4로 소수가 아니다. 

4의 제곱근은 2인데, 위의 예시처럼 4의 약수 중 하나인 1은 4의 제곱근인 2보다 작다.

 

 

느낀점

for문을 도는 횟수를 줄이기 위해 생각하다보니 푸는데 꽤 걸렸던 것 같다. 

가끔은 간단하게, 그리고 직관적으로 푸는 것도 중요한듯하다.