ONE MAN GAME DEV

내 인생에서 믿을 건 오직 나 자신뿐!

The only one you can truly trust is yourself.

게임 프로그래밍/Python 프로그래밍

프로그래머스 숫자 블록

🎮inspirer9 2023. 2. 18. 00:44

728x90

문제 설명

그렙시에는 숫자 0이 적힌 블록들이 설치된 도로에 다른 숫자가 적힌 블록들을 설치하기로 하였습니다. 숫자 블록을 설치하는 규칙은 다음과 같습니다.

블록에 적힌 번호가 n 일 때, 가장 첫 블록은 n * 2번째 위치에 설치합니다. 그 다음은 n * 3, 그 다음은 n * 4, ...위치에 설치합니다. 기존에 설치된 블록은 빼고 새로운 블록을 집어넣습니다.

블록은 1이 적힌 블록부터 숫자를 1씩 증가시키며 순서대로 설치합니다. 예를 들어 1이 적힌 블록은 2, 3, 4, 5, ... 인 위치에 우선 설치합니다. 그 다음 2가 적힌 블록은 4, 6, 8, 10, ... 인 위치에 설치하고, 3이 적힌 블록은 6, 9, 12... 인 위치에 설치합니다.

이렇게 3이 적힌 블록까지 설치하고 나면 첫 10개의 블록에 적힌 번호는 [0, 1, 1, 2, 1, 3, 1, 2, 3, 2]가 됩니다.

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

그렙시의 시장님은 특정 구간에 어떤 블록이 깔려 있는지 알고 싶습니다.

구간을 나타내는 두 정수 begin, end 가 매개변수로 주어 질 때, 그 구간에 깔려 있는 블록의 숫자 배열을 return하는 solution 함수를 완성해 주세요.

제한 사항

1 ≤ begin ≤ end ≤ 1,000,000,000
end - begin ≤ 5,000

입출력 예

begin	end	result
1	10	[0, 1, 1, 2, 1, 3, 1, 4, 3, 5]

입출력 예 설명

입출력 예 #1
다음과 같이 블럭이 깔리게 됩니다.

※ 공지 - 2019년 4월 07일 테스트케이스가 변경되었습니다.
※ 공지 - 2023년 2월 09일 지문과 테스트 케이스가 수정되었습니다. 기존에 통과되었던 코드가 통과되지 않을 수 있습니다.

풀이

처음 보고 소수 문제인가? 생각했다.
그리고 정확성 테스트 15개와 효율성 테스트 6개가 있으니까 위에 설명대로 1번 벽돌 부터 순서대로 까는 걸로 구현해버리면 당근 시간초과가 날 것이다.
그럼 어떻게 해야될까? 한방에 풀어야 하는 문제 아닐까?
근데 이거 딱 보니까 자신을 제외한 가장 큰 약수를 찾는 문제다.

1	2	3	4	5	6	7	8	9	10
0	1	1	2	1	3	1	4	3	5

~~파이썬 math.gcd로 되나?~~ 멍청아! 그건 공배수잖아... ㅋㅋㅋ
다시 봐봐 일단 짝수면 n/2다.
홀수가 문제.
- 홀수는 1부터 sqrt(n)까지 구해야되나?
- 홀수의 자신을 제외한 가장 큰 약수
1트
- 정확성 13번 실패.
- 효율성 올 실패(시간 초과 아님)

import math

def solution(begin, end):
    answer =[]
    
    def odd_check(n):
        if n == 1:
            return 0
        else:
            for i in range(3, int(math.sqrt(n)+1)):
                if n % i == 0:
                    return n // i
                    break
        return 1
    
    for i in range(begin, end+1):
        if i % 2 == 0:
            answer.append(i//2)
        else:
            answer.append(odd_check(i))
            
    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.08ms, 10.3MB)
테스트 2 〉	통과 (0.11ms, 10MB)
테스트 3 〉	통과 (0.11ms, 10.3MB)
테스트 4 〉	통과 (0.06ms, 10.2MB)
테스트 5 〉	통과 (0.03ms, 10.2MB)
테스트 6 〉	통과 (0.15ms, 10.1MB)
테스트 7 〉	통과 (0.03ms, 10MB)
테스트 8 〉	통과 (0.09ms, 10.2MB)
테스트 9 〉	통과 (0.15ms, 10.3MB)
테스트 10 〉	통과 (0.11ms, 10.2MB)
테스트 11 〉	통과 (0.04ms, 10.1MB)
테스트 12 〉	통과 (0.06ms, 10.1MB)
테스트 13 〉	실패 (0.00ms, 10.3MB)
테스트 14 〉	통과 (0.21ms, 10.2MB)
테스트 15 〉	통과 (0.01ms, 10.3MB)
효율성  테스트
테스트 1 〉	실패 (178.73ms, 10.6MB)
테스트 2 〉	실패 (244.52ms, 10.6MB)
테스트 3 〉	실패 (298.63ms, 10.5MB)
테스트 4 〉	실패 (351.76ms, 10.5MB)
테스트 5 〉	실패 (364.34ms, 10.5MB)
테스트 6 〉	실패 (316.73ms, 10.5MB)

공지사항에 뭐가 바뀌었다고 했었지?
아... 벽돌이 더 적어...
"그렙시는 길이가 1,000,000,000인 도로에 1부터 10,000,000까지의 숫자가 적힌 블록들을 이용해"
쉬울 줄 알았는데 갑자기 어려워졌다. ㅋㅋㅋ
짝수도 홀수가 되고, 엄청 큰 소수가 나오면 못 푸는 문제가 되어버렸네...

import sys
import math
sys.setrecursionlimit(10**5)

def solution(begin, end):
    answer =[]
    
    def even_check(n):
        n //= 2
        if n > 10000000:
            if n % 2 == 0:
                n = even_check(i)
            else:
                n = odd_check(i)
        return n
    
    def odd_check(n):
        if n == 1:
            return 0
        for i in range(2, n):
            if n % i == 0:
                if n // i <= 10000000:
                    return n // i
                    break
        return 1
        
    for i in range(begin, end+1):
        if i % 2 == 0:
            answer.append(even_check(i))
        else:
            answer.append(odd_check(i))
            
    return answer

재귀를 줄여야 하는데 짝수 밖에 못 줄임...

import sys
import math
sys.setrecursionlimit(10**5)

def solution(begin, end):
    answer =[]
    
    def even_check(n):
        n //= 2
        while n > 10000000:
            if n % 2 != 0:
                n = odd_check(i)
            else:
                n //= 2
        return n
    
    def odd_check(n):
        if n == 1:
            return 0
        for i in range(3, n, 2):
            if n % i == 0:
                if n // i <= 10000000:
                    return n // i
                    break
        return 1
        
    for i in range(begin, end+1):
        if i % 2 == 0:
            answer.append(even_check(i))
        else:
            answer.append(odd_check(i))
            
    return answer

채점가즈아!
하지만 효율성 통과 못 할 듯... 역시나...

정확성  테스트
테스트 1 〉	통과 (12.02ms, 9.94MB)
테스트 2 〉	통과 (50.41ms, 10.1MB)
테스트 3 〉	통과 (28.46ms, 10.2MB)
테스트 4 〉	통과 (18.05ms, 10.1MB)
테스트 5 〉	통과 (3.38ms, 10.1MB)
테스트 6 〉	통과 (37.07ms, 10.1MB)
테스트 7 〉	통과 (5.02ms, 10.1MB)
테스트 8 〉	통과 (12.03ms, 10.2MB)
테스트 9 〉	통과 (53.30ms, 10.1MB)
테스트 10 〉	통과 (14.35ms, 10.2MB)
테스트 11 〉	통과 (0.06ms, 10.1MB)
테스트 12 〉	통과 (11.87ms, 10.2MB)
테스트 13 〉	통과 (695.50ms, 10.3MB)
테스트 14 〉	통과 (16.21ms, 10.2MB)
테스트 15 〉	통과 (0.02ms, 10.2MB)
효율성  테스트
테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	
테스트 6 〉

소수가 포함되어 있는지 찾아야 됨.
에라토스테네스의 체로 천만까지 숫자중에 소수를 저장해두려고 했으나

import math

def solution(begin, end):
    answer =[]
    
    MAX = 10000001
    eratosthenes_sieve = [True] * MAX # 소수가 들어있는 리스트
    eratosthenes_sieve[0] = eratosthenes_sieve[1] = False
    for i in range(2,MAX):
        if eratosthenes_sieve[i]:
            for j in range(2, int(MAX ** 0.5) + 1):
                if i % j == 0: # i가 소수인 경우, i의 배수를 모두 제거한다
                    for k in range(i, MAX, i):
                        eratosthenes_sieve[k] = False
    print(eratosthenes_sieve[6])

실행시간이 10초를 초과하여 실행이 중단됨.

이런 케이스가 몇개 없을 것이다...라는건가?
... 자포자기다... 무지성 코딩 가즈아!!!
새벽 1시... 진짜 포기다. 완전 무지성으로 간다....
헐?

그냥 문제에서 말하는 대로 코딩함.
이게 설마 구현 문제였다니... ㄷㄷㄷ
자신을 제외한 가장 큰 약수 구하는 것만 덜 무지성으로 했으면 빨랐을텐데 아쉽다.

def get_larger_but_smaller_than_10M(n):
    divisors = [1]
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n//i:
                divisors.append(n//i)
    for i in range(len(divisors)):
        if divisors[i] > 10000000:
            divisors[i] = 1
    return max(divisors)

def solution(begin, end):
    length = end - begin + 1
    array = [0] * length

    for i in range(begin, end+1):
        if array[i-begin] == 0:
            array[i-begin] = get_larger_but_smaller_than_10M(i)
        for j in range(i*2, end+1, i):
            array[j-begin] = i

    if begin == 1:
        array[0] = 0
        
    return array

정확성  테스트
테스트 1 〉	통과 (1.28ms, 10.3MB)
테스트 2 〉	통과 (0.83ms, 10.4MB)
테스트 3 〉	통과 (1.01ms, 10.3MB)
테스트 4 〉	통과 (0.39ms, 10.3MB)
테스트 5 〉	통과 (0.23ms, 10.3MB)
테스트 6 〉	통과 (1.72ms, 10.3MB)
테스트 7 〉	통과 (0.25ms, 10.4MB)
테스트 8 〉	통과 (0.62ms, 10.4MB)
테스트 9 〉	통과 (1.58ms, 10.4MB)
테스트 10 〉	통과 (0.67ms, 10.4MB)
테스트 11 〉	통과 (0.56ms, 10.3MB)
테스트 12 〉	통과 (0.46ms, 10.4MB)
테스트 13 〉	통과 (0.26ms, 10.4MB)
테스트 14 〉	통과 (1.60ms, 10.3MB)
테스트 15 〉	통과 (0.01ms, 10.3MB)
효율성  테스트
테스트 1 〉	통과 (2432.80ms, 10.7MB)
테스트 2 〉	통과 (3823.08ms, 10.8MB)
테스트 3 〉	통과 (4690.62ms, 10.6MB)
테스트 4 〉	통과 (6079.13ms, 10.6MB)
테스트 5 〉	통과 (6633.37ms, 10.7MB)
테스트 6 〉	통과 (4767.64ms, 10.6MB)

지성이 있는 고수들의 풀이...
네, 저도 처음에는 이 정도 길이의 알고리즘을 생각했씁미다.
근데 그땐 안됐었다구요.

def solution(begin, end):
    answer = []
    #약수 중 가장 큰 수 찾기
    for i in range(begin,end+1):
        if i>1:
            a=1
            for j in range(2,int(i**(1/2))+1):
                if i%j==0:
                    a=j
                    if i//j<=10000000:
                        a=i//j
                        break
            answer.append(a)
        elif i==1:
            answer.append(0)
    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.11ms, 10.2MB)
테스트 2 〉	통과 (0.14ms, 10.3MB)
테스트 3 〉	통과 (0.25ms, 10.3MB)
테스트 4 〉	통과 (0.08ms, 10.2MB)
테스트 5 〉	통과 (0.05ms, 10.2MB)
테스트 6 〉	통과 (0.18ms, 10.2MB)
테스트 7 〉	통과 (0.05ms, 10.3MB)
테스트 8 〉	통과 (0.07ms, 10.3MB)
테스트 9 〉	통과 (0.35ms, 10.2MB)
테스트 10 〉	통과 (0.13ms, 10.2MB)
테스트 11 〉	통과 (0.06ms, 10.3MB)
테스트 12 〉	통과 (0.06ms, 10.4MB)
테스트 13 〉	통과 (0.26ms, 10.3MB)
테스트 14 〉	통과 (0.44ms, 10.1MB)
테스트 15 〉	통과 (0.02ms, 10.2MB)
효율성  테스트
테스트 1 〉	통과 (509.04ms, 10.7MB)
테스트 2 〉	통과 (834.14ms, 10.8MB)
테스트 3 〉	통과 (1134.45ms, 10.5MB)
테스트 4 〉	통과 (1602.54ms, 10.6MB)
테스트 5 〉	통과 (1862.51ms, 10.6MB)
테스트 6 〉	통과 (1333.27ms, 10.7MB)

from math import sqrt

def get_div(n):
    if n == 1:
        return 0
    elif n <= 3:
        return 1

    tmp = []
    for i in range(2, int(sqrt(n)) + 1):
        if n%i == 0:
            d = int(n/i)
            if d <= 10000000:
                return d
            else:
                tmp.append(i)
    if tmp:
        return tmp[-1]
    return 1

def solution(begin, end):
    answer = [get_div(i) for i in range(begin, end+1)]
    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.10ms, 10.1MB)
테스트 2 〉	통과 (0.13ms, 10.2MB)
테스트 3 〉	통과 (0.13ms, 10.2MB)
테스트 4 〉	통과 (0.07ms, 10.2MB)
테스트 5 〉	통과 (0.06ms, 10.1MB)
테스트 6 〉	통과 (0.17ms, 10.1MB)
테스트 7 〉	통과 (0.10ms, 10.2MB)
테스트 8 〉	통과 (0.12ms, 10.3MB)
테스트 9 〉	통과 (0.18ms, 10.2MB)
테스트 10 〉	통과 (0.23ms, 10.1MB)
테스트 11 〉	통과 (0.05ms, 10.2MB)
테스트 12 〉	통과 (0.05ms, 10.2MB)
테스트 13 〉	통과 (0.51ms, 9.96MB)
테스트 14 〉	통과 (0.25ms, 10MB)
테스트 15 〉	통과 (0.03ms, 10.1MB)
효율성  테스트
테스트 1 〉	통과 (511.13ms, 10.6MB)
테스트 2 〉	통과 (792.36ms, 10.5MB)
테스트 3 〉	통과 (1159.49ms, 10.6MB)
테스트 4 〉	통과 (1684.38ms, 10.6MB)
테스트 5 〉	통과 (1706.12ms, 10.5MB)
테스트 6 〉	통과 (1336.56ms, 10.6MB)

내가 짠 코드에서 약수 구하는 부분만 위에거 참고해서 고쳤다.

def get_larger_but_smaller_than_10M(n):
    divisors = []
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            d = int(n/i)
            if d <= 10000000:
                return d
            else:
                divisors.append(i)
    if divisors:
        return divisors[-1]
    return 1

def solution(begin, end):
    length = end - begin + 1
    array = [0] * length

    for i in range(begin, end+1):
        if array[i-begin] == 0:
            array[i-begin] = get_larger_but_smaller_than_10M(i)
        for j in range(i*2, end+1, i):
            array[j-begin] = i

    if begin == 1:
        array[0] = 0
        
    return array

정확성  테스트
테스트 1 〉	통과 (0.14ms, 10.2MB)
테스트 2 〉	통과 (0.16ms, 10.2MB)
테스트 3 〉	통과 (0.16ms, 10.4MB)
테스트 4 〉	통과 (0.09ms, 10MB)
테스트 5 〉	통과 (0.06ms, 10.1MB)
테스트 6 〉	통과 (0.22ms, 10.2MB)
테스트 7 〉	통과 (0.10ms, 10.4MB)
테스트 8 〉	통과 (0.08ms, 10.2MB)
테스트 9 〉	통과 (0.40ms, 10.3MB)
테스트 10 〉	통과 (0.29ms, 10.2MB)
테스트 11 〉	통과 (0.07ms, 10.2MB)
테스트 12 〉	통과 (0.12ms, 10.3MB)
테스트 13 〉	통과 (0.26ms, 9.98MB)
테스트 14 〉	통과 (0.33ms, 10.3MB)
테스트 15 〉	통과 (0.01ms, 10.2MB)
효율성  테스트
테스트 1 〉	통과 (513.00ms, 10.7MB)
테스트 2 〉	통과 (872.49ms, 10.8MB)
테스트 3 〉	통과 (1235.25ms, 10.6MB)
테스트 4 〉	통과 (1627.39ms, 10.6MB)
테스트 5 〉	통과 (1867.44ms, 10.6MB)
테스트 6 〉	통과 (1402.81ms, 10.7MB)

728x90

저작자표시 동일조건

'게임 프로그래밍 > Python 프로그래밍' 카테고리의 다른 글

프로그래머스 모음사전 (0)	2023.02.18
프로그래머스 배달 (0)	2023.02.18
프로그래머스 땅따먹기 (0)	2023.02.17
피보나치 수열의 일반항 (0)	2023.02.17
프로그래머스 3 x n 타일링 역대급 어렵넼ㅋㅋ (0)	2023.02.17

현재글프로그래머스 숫자 블록

ONE MAN GAME DEV

프로그래머스 숫자 블록

문제 설명

제한 사항

입출력 예

입출력 예 설명

풀이

'게임 프로그래밍 > Python 프로그래밍' 카테고리의 다른 글

'게임 프로그래밍/Python 프로그래밍'의 다른글

티스토리툴바

프로그래머스 숫자 블록

문제 설명

제한 사항

입출력 예

입출력 예 설명

풀이

'게임 프로그래밍 > Python 프로그래밍' 카테고리의 다른 글

'게임 프로그래밍/Python 프로그래밍'의 다른글

관련글

티스토리툴바