문제 출처:https://school.programmers.co.kr/learn/courses/30/lessons/138475
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이:
다 틀린 풀이:
from collections import deque, Counter
from itertools import islice
def solution(e, starts):
lst = deque(sorted([(i, e) for i in starts]))
dic = {x:0 for x in range(1,e+1)}
res = []
while lst:
left, right = lst.popleft()
for x in range(left, right+1):
count = 0 # 숫자가 나와야함
if dic[x] != 0:
continue
for i in range(1, int(x**0.5)+1):
if x % i == 0:
count += 1
if i ** 2 != x:
count += 1
dic[x] = count
start, ex = 0, len(starts)
while ex != 0:
arr = dict(islice(dic.items(),starts[start],e))
ex -= 1
start += 1
res += Counter.most_common(arr,1)
return [x for x,y in res]
1개 맞음
시간초과 코드
from collections import deque, Counter
from itertools import islice
def solution(e, starts):
lst = deque([(i, e) for i in starts])
dic = {x:0 for x in range(1,e+1)}
res = []
while lst:
left, right = lst.popleft()
for x in range(left, right+1):
count = 0
for i in range(1, int(x**0.5)+1):
if x % i == 0:
count += 1
if i ** 2 != x:
count += 1
dic[x] = count
arr = dict(islice(dic.items(),left-1,right))
max = Counter.most_common(arr,1)
res.append(max)
return [x for x,y in sum(res,[])]
60점 맞음
시간초과 다 틀림 정답은 맞는다
# 약수구하는거 while 으로 바꿔봄
from collections import deque, Counter
from itertools import islice
def solution(e, starts):
lst = deque([(i, e) for i in starts])
dic = {x:1 for x in range(1,e+1)}
res = []
for i in range(2, e+1):
x = 1
while i * x <= e:
dic[i*x] += 1
x += 1
for i in starts:
arr = dict(islice(dic.items(),i-1,e))
max = Counter.most_common(arr,1)
res.append(max)
return [x for x,y in sum(res,[])]
print(solution(8,[1,3,7]))
# 70점 맞는 코드정답 풀이:
#
def solution(e, starts):
lst = [1 for _ in range(e+1)]
for a in range(2, e+1) :
for b in range(a, e+1, a) :
lst[b] += 1
result = []
idx = len(lst)-1
max_value = lst[-1]
for i in range(idx ,0 ,-1):
if lst[i] >= max_value:
idx = i
max_value = lst[i]
lst[i] = idx
for i in starts:
result.append(lst[i])
return result
우선 딕셔너리를 사용하여 숫자별로 약수에 갯수를 세서 저장하려고 했다.
dic = {x:1 for x in range(1,e+1)}
res = []
for i in range(2, e+1):
x = 1
while i * x <= e:
dic[i*x] += 1
x += 1
이렇게 말이다.하지만 시간을 너무 많이써서 이 부분을 아래와 같이 바꿔주었다.
lst = [1 for _ in range(e+1)]
for a in range(2, e+1) :
for b in range(a, e+1, a) :
lst[b] += 1
print(solution(10,[3,1,7]))
>> [1, 1, 2, 2, 3, 2, 4, 2, 4, 3, 4]
# 인덱스는 0 부터 저장
일단 모든 수는 자기 자신을 약수로 가지고 있으니깐 1을 기본적으로 넣어주고
2부터 e까지 포문을 돌면서 >> 2의배수, 3의배수 ..m의 배수,, e 전까지 +1을 더해주면
최종적으로 약수가 저장된다.
예시를 아래로 들겠다.
print(solution(10,[3,1,7]))때 E 는 10 이다 시작점은 3,1,7
내가 푼 방식은 인덱스와,최댓값을 저장해놓고 starts에서 거꾸로 오는것이다
idx = len(data) - 1
for i in range(len(data) - 1, 0, -1):그럼 거꾸로 오면서 계산하는데 어차피 맨 마지막 10은 10~10 이니깐 10의 약수를 넣어주면 된다.
그러므로 일단 max_val 에 lst[-1] (약수갯수) 값을 저장한다 그러면 시작이 10일때 >> 10부터 10 까지 중 약수 가장많은
최댓값은 10 밖에 없으므로 10의 약수갯수(4) 저장
인덱스 거꾸로 내려가야하니까 len(lst) - 1 선언 // -1 안하면 e 보다 1크다.
지금 상태 idx = 10 max_value = 4
for i in range(idx ,0 ,-1):
if lst[i] >= max_value:
idx = i
max_value = lst[i]
lst[i] = idxmax_value 는 약수의 갯수라고 생각하면 된다.
그러면 이제 for 문을 돌려서 맨 끝부터 -1씩 내려가면서 원래 가지고 있던 max_value와
지금 i 인덱스에 max_value을 비교하여 저장하는식으로 나가면 된다 >> 저장된거보다 크면 index를 넣어주는식
예를들면 첫 포문 돌리면
[1, 1, 2, 2, 3, 2, 4, 2, 4, 3, 10] 이 나온다.
그이유는 위에서 말한것처럼 맨 마지막 값이므로 10에서 10 까지 중 최댓값이므로 10 max_val 에는 10에 약수의 갯수(4)가 저장
그다음 포문을 돌리면 i = 9 이고, max_value = 4이며, lst 에는 [1, 1, 2, 2, 3, 2, 4, 2, 4, 10, 10] 이렇게 들어가 있다.
인덱스는 9가 된다. 근데 리스트 안에서의 [9] 의 값 lst[9] 의 약수갯수 는 3개이다
그러면 9는 약수갯수가 3인데 10은 약수갯수가 4니깐 10이 들어가면 되는것이다.
9에서 10 은 [3,4] 10에서 10은 [4] 즉 약수 최대갯수 가진 10이 들어간다
그럼 그 다음 포문으로 오면 i = 8 max_value = 4 lst = [1, 1, 2, 2, 3, 2, 4, 2, 8, 10, 10] 이런식인데
if 문에 조건이 맞게된다 8도 약수4개 그리고 원래 10의 max_value 도 4이므로 lst[i] 와 max_value가 같다.
그러면 작은수를 저장해야하니깐 idx를 i(8)로 바꿔주고 max_value 도 바꿔주고
리스트 값을 idx(8) 값으로 저장해준다..
이렇게 쭉쭉 내려가면
[1, 1, 6, 6, 6, 6, 6, 8, 8, 10, 10] 이 나온다.
for i in starts:
result.append(lst[i])
return result그럼 인덱스 찾아서 출력
댓글