숫자 블록

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

프로그래머스

문제요약:

n 이 1부터 증가하며 배열의 2*n,3*n... 에 그 n을 집어넣을때, (가령 배열8같은 경우는 n 이 2 일때 2*4이므로 2를 쓰게 되지만 n이증가하며 4가될때 4*2가 되므로 최종적으론 4가된다.)  배열에서 입력한 부분의 값만 표현하라

 

소요시간:

40분

난이도 2

 

1차시도: (실패)

def solution(begin, end):
	L = end - begin +1
	#배열에서 필요한 부분만 생성
	arr = [1] * L
	for i in range(L):
		#짝수라면 무조건 2로 나눈것이 최대값임
		if (i+begin)%2 == 0:
			arr[i] = (i+begin)//2
		#홀수라면 3부터 제곱근 까지 구해보고 최대값이 나온다면 반복문탈
		else:
			for j in range(3,math.floor(math.sqrt(i+begin))+1,2):
				if (i+begin)%j==0:
					arr[i] = (i+begin)//j
					break
	if begin ==1:
		arr[0] =0
	return arr

결국 문제를 요약하면 자신을 제외한 공약수 중 가장 큰 값을 넣어라 이기 때문에, 짝수라면 2로나눈 나머지가 가장 클것이고, 홀수 라면 3부터 제곱근까지 계속 나누어 그중 나누어 떨어지는 나머지가 가장 클 것이기 때문에, 다음과 같이 코딩을 했습니다. 다만 이때 아무것도 나누어 떨어지지 않는다면 (소수) 자신을 제외한 공약수는 1밖에 없기 때문에 초기값을 1로 세팅해 주었는데, 항상 시작할때, 2*n부터 시작 하기 때문에 만약 begin이 1 이어서 배열1의 값을 확인해야한다면 그값은 0으로 예외처리 해주었습니다. 

 

대부분의 테스트 케이스를 통과했지만, 한개의 테스트케이스가 통과하지 않았고, 효율성 테스트 케이스가 전부 통과하지 않았습니다. 이때 효율성테스트의 실패가 시간초과가 아닌 그냥실패(답이 다름) 이어서 놓친 조건이 있는지 확인했고, 다음과 같은 조건이 있었습니다.

 

'길이가 1,000,000,000인 도로에 1부터 10,000,000까지의 숫자가 적힌 블록들을 이용해 위의 규칙대로 모두 설치 했습니다.' 

즉 배열의 길이는 1e9이지만 안에 들어갈 수 있는 숫자는 1e7이하여야 했습니다. 그래서 숫자가 작은 (배열의 숫자가 1e7이내인) 테스트 케이스는 통과했지만, 숫자가큰 효율성 테스트들은 실패한것이었습니다. 

(ex 40,000,000 에선 원래짠 코드에선 짝수이기 때문에 반을 나눈, 20,000,000 이 정답이지만 표연할 수 있는 숫자 초과이기 때문에, 4를 나눈 10,000,000 이 정답입니다)

 

2차시도:

import math

def check(k):
	#만약 1e7로 나누어떨어지는 숫자라면 1e7이 가장큼
	if k%10000000 == 0 :
		return 10000000
	temp = []
	
	for l in range(2,math.floor(math.sqrt(k))+1):
		#만약 나누어 떨어졌는데 
		if k%l == 0 :
			# 값이 1e7보다 작다면 제곱근 이전까지만 찾았으므로 그것이 무조건 최대
			if k//l <10000000:
				return k//l
			else:
			# 만약 1e7보다 크다면 제곱근 이전까지만 찾을것이기 때문에 나머지값저장
			# ex) 2 * (1e7보다큰 소수 ) 일 경우 가장 큰값은 2이다.
				temp.append(l)
	#제곱근 이전에 나눌수 있던 수 중 가장큰수
	else:	
		return max(temp)
		
def solution(begin, end):
	L = end - begin +1
	#배열에서 필요한 부분만 생성
	arr = [1] * L
	for i in range(L):
		#짝수라면 무조건 2로 나눈것이 최대값임
		if (i+begin)%2 == 0:
			arr[i] = (i+begin)//2
		#홀수라면 3부터 제곱근 까지 구해보고 최대값이 나온다면 반복문탈
		else:
			for j in range(3,math.floor(math.sqrt(i+begin))+1,2):
				if (i+begin)%j==0:
					arr[i] = (i+begin)//j
					break
		if arr[i]>10000000:
			arr[i] = check(i+begin)
	if begin ==1:
		arr[0] =0
	return arr

기본 로직은 똑같고 만약 1e7를 넘어갈경우만 새로운 함수에 넣어 주었는데 위에 주석에 달았듯이, 쉽게 말하면 나누어 지는 수중 1e7보다 작은 가장큰 값을 찾는 함수입니다. 만약 바로바로 정답인경우(ex 1e7로 나누어지는 경우)등은 예외처리를 해주어 속도향상을 기대하였습니다.(크게 차이나진 않음)