약수 구하기 (2501) / 완전 제곱수 (1977)

브루트 포스 기초문제

• 하단 영상에서 추천해주신 문제를 풀어보았다.

• 코딩테스트 문제 추천! (2023년 2월 3주차)
• 기초 브루트 포스 문제들은 첫 번째 시도에서 한 번에 맞추도록 해야한다.

약수 구하기 (2501) [브론즈 III]

• 2501번: 약수 구하기
• Github

# 0. 입력 받기
n, k = map(int, input().split())

# 1. 약수 리스트 작성
divider = []
# 1-1. 제곱근 이하까지만 탐색하면 시간 효율을 높일 수 있음.
for i in range(1, int(n ** 0.5) + 1):
    if n % i == 0:
        divider.append(i)
        # 1-2. 제곱근의 경우 한 번 더 추가되므로
        if i != int(n / i):
            divider.append(int(n / i))
# 1-3. 오름차순 정렬 진행
divider = sorted(divider)

# 2. k개보다 약수 수가 적으면 0을 출력
if len(divider) >= k:
    print(divider[k - 1])
else:
    print(0)

• 최대한 단순하게 구현했다. 약수 리스트를 만들고 정렬했다.
• 정렬하는 과정에서 시간복잡도가 증가할 가능성을 막아보고자 deque를 활용해보았다.
  
  

# 0. 입력 준비 + deque 준비
from collections import deque
n, k = map(int, input().split())

# 1. 중간 지점(제곱근 부근)까지의 약수 리스트와
# 그 이상의 약수 리스트 두 가지를 구성한다.
divider_left = deque([])
divider_right = deque([])
for i in range(1, int(n ** 0.5) + 1):
    if n % i == 0:
        divider_left.append(i)
        if i != int(n / i):
        	# 1-1. 큰 약수 리스트는 더 작은 값이 들어올 것이므로.
            # appendleft로 앞에 추가해준다.
            divider_right.appendleft(int(n / i))
# 1-2. sorted 메소드 없이 그대로 붙여주면 된다.
divider = divider_left + divider_right

# 2. k개보다 약수 수가 적으면 0을 출력
if len(divider) >= k:
    print(divider[k - 1])
else:
    print(0)

• 예상과 달리 시간이 더 걸렸다. (40ms -> 68ms)
• 두 개의 리스트를 합하는 것에서 시간이 더 소요된 것으로 보였다.
• sorted는 O(n log n)의 시간복잡도가 소요되지만 extend(리스트 끼리의 + 연산과 같음)는 O(확장하는 길이)만큼 소요된다.
• 즉 케이스의 수가 커짐에 따른 소요 시간 증가폭은 deque를 이용한 솔루션이 좀 더 걸릴 수 있는 것이다.

완전 제곱수 (1977) [브론즈 II]

• 1977번: 완전 제곱수
• Github

# 0. 입력 준비.
import math
m = int(input())
n = int(input())

# 1. math.ceil을 이용해 올림한다.
# 만일 60이 입력되면 7.xx가 될 것이고 최소 제곱수는 8이 되어야 한다.
s = math.ceil(m ** 0.5)
powed = []
# 1-1. 1씩 올리며 n 이하의 제곱수인지 체크
while (s * s) <= n:
    powed.append(s * s)
    s += 1

if len(powed) > 0:
    print(sum(powed))    
    print(powed[0])
else:
    print(-1)

• 문제의 이상, 이하 조건이 있어 확인해야했다.
• 처음에 int로 버림을 진행하고 1을 더해줬는데, 위의 조건에서처럼 다른 수가 입력되면 문제 없었으나, 64와 같은 제곱수가 들어오면 오답이 발생했다.