28일차(2020-12-15)

programmers.co.kr/learn/challenges?selected_part_id=12079

코딩테스트 연습

 

<문제 1> 프로그래머스) 소수 찾기(Level 1)

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
 
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
 
제한 조건
n은 2이상 1000000이하의 자연수입니다.

 

<답안 1>

def solution(n):
    sosu = 0
    nsosu = 0
 
    for i in range(2, n+1):
        for j in range(2, i): #본인보다 작은 수 넣기
            if i % j == 0: #본인과 본인보다 작은 수를 나눠서 0이면
                nsosu += 1 #나눠지는 수가 있다는 거니까 소수가 아닌 곳에 +1
        if nsosu == 0: #nsosu가 0이라는건 1과 본인 말고는 약수가 없다는 이야기
            sosu += 1
        nsosu = 0 #for문 돌려야 하니까 초기화
 
    return sosu
 
print(solution(10))

-> 답은 나오지만 실행 시간 초과로 나온다.

 

<답안 1 : 다른 ver>

ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

소수를 구하는 공식인 에라토스테네스의 체로 풀어보자!

 

여기서 우리가 알아야 할 점은:

(1) 2를 선택하여 2의 배수들을 모두 제거한다.
(2) 그 다음 제거되지 않은 숫자를 기준으로 그 숫자의 배수들을 모두 제거한다.
=> (1), (2)에서 제거되지 않고 남아있는 숫자가 소수다.

 

def solution(n):
    answer = 0
    number = []
    # 1단계: 리스트 number에  0부터 n까지 인덱스와 값이 일치하도록 만들어준다.
    for i in range(n + 1):
        number.append(i)
    # 2단계: 2의 배수와 숫자의 배수를 -1로 만든다. 
    for i in range(2, n + 1, 1):
        if i == -1: #이미 -1이라면 continue
            continue
        j = 0
        for j in range(i + i, n + 1, i): 
            number[j] = -1 #i + i를 하면 2의 배수가, by값을 i로 하면 배수가 -1이 된다.
    # 3단계 -1이 아닌 값이 소수이다.
    for i in range(2, n + 1):
        if number[i] != -1:
            answer += 1
    return answer
 
print(solution(5))

 

참고한 사이트: m.blog.naver.com/PostView.nhn?blogId=h0609zxc&logNo=221362746026&proxyReferer=https:%2F%2Fwww.google.co.kr%2F

소수 찾기(프로그래머스 level1, 에라토스테네스의 체, 파이썬)

 

 

<문제 2> 프로그래머스) 수박수박수박수박수박수?

길이가 n이고, 수박수박수박수....와 같은 패턴을 유지하는 문자열을 리턴하는 함수, solution을 완성하세요. 
예를들어 n이 4이면 수박수박을 리턴하고 3이라면 수박수를 리턴하면 됩니다.
 
<제한 조건>
n은 길이 10,000이하인 자연수입니다.

 

<답안 2>

text = "수박수박수박수"
 
def solution(text, n):
    answer = []
    a = list(text) #리스트형으로 바꿈
 
    for i in range(n):
       answer.append(a[i]) #갯수만큼 answer리스트에 추가
    
    return ("").join(answer) #문자열 형식으로 나오게 함
 
print(solution(text, 3))

=> 답은 나오는데 프로그래머스에서 정답으로 처리되진 않는다.

 

<답안 2 : 다른 ver>

def solution(n):
    return "수박"*(n//2) + "수"*(n%2)
 
print(solution(4))

1. n이 짝수인 경우 "수박" 전체가 반복되므로 n을 2로 나눴을 때 몫 개수만큼 "수박"을 반복해준다.

2. n이 홀수인 경우 "수"가 뒤에 붙으므로 n을 2로 나눴을 때 나머지값 만큼 "수"를 반복해준다.

 

=> 프로그래머스에서 정답으로 인정되지만 이 경우 확장성이 부족해서 아쉽다.