프로그래머스 algorithm study python 공약수

파이썬 알고리즘 : 바탕화면 정리

좌표

2023년 12월 19일 알고리즘 문제풀이

문제

숫자 블록

난이도

Lv.2

코드

첫 생각

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def solution(begin, end):
    answer = []
    for n in range(begin,end+1):
        if n == 1:
            answer.append(0)
        elif not n%2:
            answer.append(n//2)
        else:
            for i in range(3,n//2):
                if not n%i:
                    answer.append(n//i)
                    print(n,n//i)
                    break
            else:
                answer.append(1)
    return answer

최대공약수와 관련된 문제라고 생각했다. 최초 0으로 설정되있는 각 숫자는 1부터 하나씩 업데이트되겠지만, 마지막으로 업데이트될 때는 최대공약수로 될 것이다. 따라서 짝수는 절반값으로 된다. 2는 1, 4는 2, 6은 3, 8은 4 가 그 예시이다. 문제는 홀수였는데.. 홀수는 2로 나눠질 수 없는 것은 확실하니 3부터 1씩 커지면서 나누어주었다. 나누어 떨이질때, 그 몫이 최대 공약수이다. 하지만 이 경우가 자기 자신 뿐이라면 그때는 소수이므로 1로 설정해줬다.

이 풀이는 1가지 예외의 경우가 존재한다는 것, 효율성에 문제가 있었다. 우선 짝수와 홀수를 굳이 구분해야하나? 라는 생각이 들었다. 이를 하나로 합쳐보면 생각하는데 좀더 간편해지지 않을까.. 그리고 자세히 보니 도로의 길이(배열의 길이)와 도로에 적힌 수의 크기가 달랐다. 뭔가 심상치 않아 조건을 추가해주었다.

1
2
3
4
5
6
7
8
9
10

def solution(begin, end):
    answer = []
    for n in range(begin,end+1):
        if n == 1:
            answer.append(0)
            continue
        for i in range(2,int(n**(0.5))+1):
            if not n%i and n//i <= 10000000:
                answer.append(n//i)
    return answer

이렇게 바꿔보았는데.. 예시로 주어진 케이스로 begin이 1이고 end가 10일때를 실행해보면 배열에 6개밖에 나타나지 않았다. 아무래도 저 두번쨰 반복문에서도 걸리지 않은 것들이 존재하기 떄문이라고 생각했고 그게 소수일 것이라고 추측했다. 출력을 통해 확인해보니 n이 1,4,6,8,9,10 일때만 answer 배열에 원소가 추가됐다. 내 코드의 문제는 소수를 처리하지 못하고 있던것. 근데 그 부분을 추가해봤자 위 코드와 달라지는 게 없는데…

결국 열심히 구글링 끝에 해결해서 답을 도출했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def solution(begin, end):
    answer = []
    for n in range(begin,end+1):
        num = 1
        if n == 1:
            num = 0
        for i in range(2,int(n**(0.5))+1):
            if not n%i:
                if n//i <= 10000000:
                    num = n//i
                    break
                else:
                    num = i
        answer.append(num)
    return answer

어떤 수는 두 공약수의 곱이라는 짝으로 이루어진다. 하나가 작으면, 하나는 크다. 애초에 이 성질을 이용해서 코드를 짰는데 부족했다. 문제 조건상 블록에 적힐 수는 10000000을 넘을 수 없다. 따라서, 현재 들어갈 수를 나누는 수가 아니라 몫으로 설정헀기 떄문에, 몫이 조건을 넘는다면 반대로 나누는 수는 조건을 넘지 않는다. 따라서 그 수를 배열에 넣어주면 된다. 기존에는 넣지 않았기 떄문에 n = axb 에서 몫인 b의 값이 조건에 부합하지 않는다면 숫자를 1씩 증가시켜 n = bxa가 나올떄까지 반복문이 진행되기 떄문에 효율성에도 문제가 발생했었던 것. 또 한가지는, 몫이 아닌 나누는 수를 체크할 때는 반복문을 종료해선 안된다. 몫은 점점 작아지기 떄문에 최댓값을 구해야 하는 상황에서 더 볼 여지가 없지만, 나누는 수는 점점 증가하기 떄문에 이후 더 적합한 최댓값이 나타날 수 있기 떄문이다.

CATALOG
    algorithm