728x90
반응형

문제:

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조작을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

풀이 방법:

 문제의 태그가 완전탐색인만큼 시간이 충분히 주어졌을 것이라고 생각했다. 따라서 numbers로 생성될 수 있는 모든 숫자의 경우들을 다 담아두고 하나씩 소수인지 판별하면 될 것 같다고 생각했다.
따라서 모든 경우의 수를 만들기 위해서 python의 itertools의 permutations 기능을 사용하고자 하였다. 
itertools.permutations(iterable,i) 와 같이 사용을 하며 iterable한 객체 중 i 개를 사용해서 나올 수 있는 경우의 수를 모두 만들어준다.
따라서 이를 활용해 모든 경우의 수를 만들어내었고 중복을 set을 사용해서 제거한 후 소수인지 판별 하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def solution(numbers):
    import itertools
    number=list(numbers)
    a=[]   
    for i in range(1,len(number)+1):
        a+=list(map(''.join,itertools.permutations(number,i)))
    a=list(set(map(int,a))) 
    a.sort()
    count=0
    print(a)
    for i in a:
        if i < 2:
            pass
        elif i ==2:
            count+=1
        else:
            for j in range(2,i):
                if i % j ==0:
                    break;
                elif j==i-1:
                    count+=1
    return count
cs


728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 2.전화번호 목록  (0) 2019.02.16
[Programmers]Lv 1.모의고사  (0) 2019.02.15
[Programmers]Lv 1. 체육복  (0) 2019.02.13
[Programmers]Lv2. 큰 수 만들기  (0) 2019.02.12
[Programmers]Lv 1. K번째수  (0) 2019.02.11
728x90
반응형

문제:

오늘은 체육수업이 있는 날입니다. 그런데 점심시간에 도둑이 들어 몇몇 학생의 체육복이 도난을 당했습니다. 다행히 일부 학생들이 여벌의 체육복을 가져왔습니다. 학생들의 번호는 체격 순으로 매겨져 있기 때문에 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려주려고 합니다.

예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 당연히 체육복을 2벌 가져온 학생의 체육복이 도난을 당했다면, 여벌의 체육복을 빌려줄 수 없습니다.

체육복이 없으면 체육수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 듣고 싶습니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

 여분을 가지고 있는 학생들은 2의 값을 가지고 있고 도난당한 학생은 0의 값, 여분을 가지고 있었지만 도난당한 학생들은 1의 값을 가지도록 한다.
이후 이웃 학생들과의 값을 비교해보았을 때 둘의 차이가 2인 경우에만 여분을 가지고 있는 학생이 도난당한 학생에게 빌려줄수 있는 상황이다. 이를 크게 두 개의 반복문으로 해결하도록 하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def solution(n,lost,reserve):
    cloth=[1]*n
    for i in range(n):
        if i+1 in reserve:
            cloth[i]=2
            if i+1 in lost:
                cloth[i]-=1
                continue
        if i+1 in lost:
            cloth[i]=0
    if cloth[0]-cloth[1]>1:
        cloth[0]-=1
        cloth[1]+=1
    for i in range(1,n-1):
        if cloth[i]-cloth[i+1] > 1:
            cloth[i]-=1
            cloth[i+1]+=1
        elif cloth[i]-cloth[i-1]>1:
            cloth[i]-=1
            cloth[i-1]+=1
        else:
            pass
    if cloth[-1]-cloth[-2] > 1:
        cloth[-1]-=1
        cloth[-2]+=1
    count=0
    for i in cloth:
        if i > 0:
            count+=1
        else:
            pass
    return count
cs

수정:

2월 28일 이후로 테스트 케이스가 추가되었다.


728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 1.모의고사  (0) 2019.02.15
[Programmers]Lv 2. 소수 찾기  (0) 2019.02.14
[Programmers]Lv2. 큰 수 만들기  (0) 2019.02.12
[Programmers]Lv 1. K번째수  (0) 2019.02.11
[Programmers]Lv 2.더 맵게  (0) 2019.02.10
728x90
반응형

문제:

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19,12,14,92,94,24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수를 매개변수로 주어집니다. number에서 k 개의 수를 제거 했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

풀이 과정:

 단순히 number 중 작은 순으로 빼는 것이 아니라는 것을 마지막 예시 케이스 4177252841을 보면 알 수 있다. 따라서 이 문제는 탐욕법을 사용해서 풀어야 하는 문제이므로 문제 풀이를 생각하였다. 따라서 각 자리별로 한번씩 다 빼보아서(ex 1924의 경우 924, 124, 194, 192) 이 중 가장 큰 경우를 선택하도록 하였다. 대부분의 경우에 대해서 통과를 하지만 역시나 자릿수가 큰 경우에 시간초과가 발생하였다.
 그래서 탐욕법이 아닌 다른 방법도 생각해보았는데 스택을 활용해서 푸는 것이 효율적으로 할 수 있었다.

 숫자를 다음과 같은 규칙에 따라 스택을 쌓아가면 큰 수를 만들어 갈 수 있다.
  1. 하나의 값을 넣는다
  2. 맨 위에 쌓인 값과 그 바로 밑(맨 위에서 두번째 값)을 비교한다.
  3. 맨 위의 값이 더 클 경우 두 개의 값의 자리를 바꾸고 pop 해내서 빼낸다. 맨 위의 값이 작으면 다음 단계로 넘어간다
  4. 1~3을 k번 빼내거나, number를 다 쌓으면 끝낸다.

 다음은 예시 케이스 4177252841을 쌓는 과정을 나타냈다.


 

 

 

 

 

 

 

 

 

 

 1


 4

 비교 대상이 없어 통과한다.

 4

위 값이 작으므로  그냥 패스한다. 

 



 

 

 

 

 

 

 7

 

 

 

 

 

 1

 7을 쌓았을 때 자리를 

 7

 자리를 바꾼 후 1을 빼

 

 이 역시 7이 더 크므로

 4

바꾼다.

 4

 고 다시 4와 비교를 함

 7

 자리를 바꾸고 4를 뺌


이 작업을 반복해서 하면 큰 수를 만들 수 있다.


하지만 54321, k=1 와 같은 경우에는 하나도 빠지는 것 없이 54321 순으로 쌓이게 된다. 이 규칙으로 쌓았을 때 마지막으로 갈 수록 수가 작아지므로 뒤에서 부터 잘라서 사용하도록 한다.


우선 number가 string이므로 이를 list로 쪼개 하나씩 넣을 수 있도록 만들었다. 그리고 첫 수는 항상 넣고 시작하였다. 하나씩 넣으면서 Tos(Top of stack) 즉 지금 맨 위에 쌓인 부분의 인덱스를 하나씩 늘렸다. while 문이 규칙의 2,3번을 반복하는 과정이다. correct라는 변수는 4177252841와 같은 경우에 7을 넣을 때 두 번 연속 빼야하는데 이와 같은 행위를 하기 위해서 넣은 변수이다.

그리고 맨마지막에 54321 과 같은 경우를 해결하기 위해 뒤에서 부터 자르도록 하였다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def solution(number,k):
    number=list(number)
    answer=[number[0]]
    Tos=0
    for i in range(1,len(number)):
        answer.append(number[i])
        Tos+=1
        correct=1
        while (correct and k !=0):
            correct-=1
            for j in range(Tos,len(answer)):
                if answer[j-1]>=answer[j]:
                    pass
                else:
                    answer[j-1],answer[j]=answer[j],answer[j-1]
                    answer.pop()
                    correct+=1
                    Tos-=1
                    k-=1
                    break
    answer="".join(answer)
    return answer[:len(answer)-k]
cs



728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 2. 소수 찾기  (0) 2019.02.14
[Programmers]Lv 1. 체육복  (0) 2019.02.13
[Programmers]Lv 1. K번째수  (0) 2019.02.11
[Programmers]Lv 2.더 맵게  (0) 2019.02.10
[Programmers]Lv 1.같은 숫자는 싫어  (0) 2019.02.09
728x90
반응형

문제:

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, K번째에 있는 수를 구하려 합니다.

배열 array, [i,j,k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

배열의 슬라이싱이 가장 중요한 문제이다. command를 반복문으로 돌리면서 0번째 값 1번째 값으로 슬라이싱을 해서 따로 배열을 복사한 뒤에 sort로 정렬하고 2번째 값으로 값을 얻어 answer 배열에 넣었다.

1
2
3
4
5
6
7
def solution(array, commands):
    answer = []
    for i in commands:
        a=array[(i[0]-1):i[1]]
        a.sort()
        answer.append(a[i[2]-1])
    return answer
cs


728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 1. 체육복  (0) 2019.02.13
[Programmers]Lv2. 큰 수 만들기  (0) 2019.02.12
[Programmers]Lv 2.더 맵게  (0) 2019.02.10
[Programmers]Lv 1.같은 숫자는 싫어  (0) 2019.02.09
[Programmers]Lv 2.조이스틱  (2) 2019.02.08
728x90
반응형

문제:

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 *2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

단순하게 scoville 배열을 정렬한 뒤에 첫 번째 인덱스값이 K보다 커지는 순간까지 섞는 과정을 반복하면 된다고 생각했다.
따라서 다음과 같이 코드를 작성할 수 있었다. 중간에 elif 조건으로 scoville 배열이 1인지 확인을 하였는데 이 경우에 더 이상 섞지 못하는 경우이기 때문에 -1을 반환하는 경우인 것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def solution(scoville,K):
    count=0
    while(True):
        scoville.sort()
        if scoville[0]>K:
            break
        elif len(scoville)==1:
            return -1
        else:
            count+=1
            a=scoville.pop(0)
            b=scoville.pop(0)
            scoville.append(a+2*b)
    return count
cs

 하지만 이 방법은 효율성 테스트에서 시간초과로 통과하지 못한다. 이 문제의 태그가 힙(heap)이므로 힙을 사용하도록 코드를 수정하였다.

힙이란 최댓값과 최솟값을 빠르게 찾아내기 위해 고안된 자료 구조로 완전이진트리로 구성되어 있다. 힙에는 최대 힙과 최소 힙 두 가지가 있다. 힙은 부모노드와 자식 노드와만 대소 관계가 존재하는데 부모 노드가 큰 경우가 최대 힙, 자식 노드가 큰 경우가 최소 힙이다.


 파이썬에서는 힙 구조를 구현할 수 있도록 모듈을 제공한다. import heapq 로 불러와서 사용을 한다. heapq는 부모 노드가 자식 노드보다 항상 작거나 같은 최소 힙을 제공한다. 따라서 가장 작은 요소가 0 인덱스를 가지며 pop을 했을 경우에 가장 작은 값이 나온다.


이번 문제를 해결하기 위해 heapq.heappush(heap,item)과 heapq.heappop(heap)을 사용했다.

heapq.heappush(heap,item)은 힙의 구조를 유지하면서 heap에 item을 넣는 것이고 heapq.heappop(heap)은 가장 작은 값을 반환하며 이 역시 힙의 구조를 유지한다. 따라서 위의 코드를 heap 구조를 유지하면서 해결하도록 수정하였다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import heapq
def solution(scoville,K):
    count=0
    h=[]
    for i in scoville:
        heapq.heappush(h,i)
    while(True):
        if h[0]>=K:
            return count
        elif len(h)==1:
            return -1
        else:
            a=heapq.heappop(h)
            b=heapq.heappop(h)
            heapq.heappush(h,a+b*2)
            count+=1
cs


728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv2. 큰 수 만들기  (0) 2019.02.12
[Programmers]Lv 1. K번째수  (0) 2019.02.11
[Programmers]Lv 1.같은 숫자는 싫어  (0) 2019.02.09
[Programmers]Lv 2.조이스틱  (2) 2019.02.08
[Programmers]Lv 1.문자열 내 마음대로 정렬하기  (0) 2019.02.07
728x90
반응형

문제:

배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 배열 arr에서 제거 되고 남은 수들을 return 하는 solution 함수를 완성해 주세요.단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다.

배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

풀이 방법:

반복문을 사용해서 연속되는 두 개 원소를 비교해 보아서 서로 달라지는 부분에서 원소를 answer에 담았다. 즉 예시에서 1,1 의 경우에는 pass로 지나가지만 1,3 구간에서는 1을 answer에 추가하게 되는 것이다.

1
2
3
4
5
6
7
8
9
def solution(arr):
    answer=[]
    for i in range(len(arr)-1):
        if arr[i]==arr[i+1]:
            pass
        else:
            answer.append(arr[i])
    answer.append(arr[-1])
    return answer
cs


728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 1. K번째수  (0) 2019.02.11
[Programmers]Lv 2.더 맵게  (0) 2019.02.10
[Programmers]Lv 2.조이스틱  (2) 2019.02.08
[Programmers]Lv 1.문자열 내 마음대로 정렬하기  (0) 2019.02.07
[Programmers]Lv 2.주식 가격  (0) 2019.02.06
728x90
반응형

문제:

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.
▲ - 다음 알파벳
▼ - 이전 알파벳(A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동

예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

-첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
-조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
-마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이 때가 최소 이동입니다.

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

풀이방법:

이 조이스틱은 크게 두가지를 최적의 방법으로 정해야 한다.

첫번째는 문자의 이동이다. 위 방향키를 사용해서 원하는 문자로 이동을 할지 아래 방향키를 사용할지를 정해야 한다. 이것은 비교적 간단하다. 알파벳은 총 26자이므로 A에서 14번째에 존재하는 알파벳은 위 방향키보다 아래 방향키로 이동하는 것이 더 효율적이기 때문이다. 이는 아스키코드 함수인 ord를 사용해서 이동하고 그 차이만큼 answer에 더하도록 한다.

두번째는 위치의 이동이다. 문자 중 A가 존재한다면 문자를 이동시킬 필요가 없으므로 왼쪽으로 이동할지 오른쪽으로 이동할지 결정을 해야한다.
이는 하나의 반복을 이용해서 결정하도록 하였다. 방금 문자를 이동시킨 인덱스에서 오른쪽 문자와 왼쪽 문자 중 A가 아닌 것을 더 빨리 만나는 쪽으로 이동하도록 하였다. 파이썬의 인덱스는 음수로 가면 오른쪽 맨 끝으로 이동하기 때문에 1씩 빼는 과정에서 음수로 가도 문제가 없다.

이 두가지의 방법을 원하는 알파벳을 만들때까지 반복하도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def solution(name):
    answer = 0
    name=list(name)
    base=["A"]*len(name)
    idx=0
    while(True):
        rightidx=1
        leftidx=1
        if name[idx]!="A":
            if ord(name[idx])-ord("A")>13:
                answer+=26-(ord(name[idx])-ord("A"))
            else:
                answer+=ord(name[idx])-ord("A")
            name[idx]="A"
        if name ==base:
            break
        else:
            for i in range(1,len(name)):
                if name[idx+i]=="A":
                    rightidx+=1
                else:
                    break
                if name[idx-i]=="A":
                    leftidx+=1
                else:
                    break
            if rightidx>leftidx:
                answer+=leftidx
                idx-=leftidx
            else:
                answer+=rightidx
                idx+=rightidx
    return answer
cs



728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 2.더 맵게  (0) 2019.02.10
[Programmers]Lv 1.같은 숫자는 싫어  (0) 2019.02.09
[Programmers]Lv 1.문자열 내 마음대로 정렬하기  (0) 2019.02.07
[Programmers]Lv 2.주식 가격  (0) 2019.02.06
[Programmers]Lv 1.소수 찾기  (0) 2019.02.05
728x90
반응형

문제:

문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 [ "sun" , "bed" , "car" ]이고 n이 1이면 각 단어의 인덱스 1의 문자 "u", "e", "a"로 strings를 정렬합니다.

풀이 방법:

 sorted에 있는 key 조건을 사용해서 풀어야 하는 문제이다. sorted 함수는 sorted( iterable , key=None , reverse=False)로 구성되어 있는데, key에 조건을 설정해주면 그 조건에 따라서 iterable을 정렬 해 준다. 이 문제에서는 인덱스 n번째로 정렬을 하므로 lambda 함수를 사용하도록 한다. 같은 인덱스 1의 문자가 여럿일 수 있으므로 미리 한번 조건 없이 정렬한 뒤 키 값을 주어서 정렬을 하도록 한다.

1
2
3
def solution(strings, n):
    strings=sorted(strings)
    return sorted(strings, key = lambda x : x[n])
cs


728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 1.같은 숫자는 싫어  (0) 2019.02.09
[Programmers]Lv 2.조이스틱  (2) 2019.02.08
[Programmers]Lv 2.주식 가격  (0) 2019.02.06
[Programmers]Lv 1.소수 찾기  (0) 2019.02.05
[Programmers]Lv 2.쇠막대기  (0) 2019.02.04
728x90
반응형

문제:

 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 유지된 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

풀이방법:

스택/큐를 사용해서 풀어야 하는 문제인 것 같지만 딱히 스택/큐를 활용하지 않아도 쉽게 풀 수 있다. 이중반복문을 이용해서 떨어지기 전까지 계속 count를 증가시키고 떨어지는 순간 break를 걸어서 그 때까지의 count를 answer 배열에 넣어주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
def solution(prices):
    answer=[]
    for i in range(len(prices)):
        count=0
        for j in range(i+1,len(prices)):
            count+=1
            if prices[i] <= prices[j]:
                pass
            else:
                break
        answer.append(count)
    return answer
cs


728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 2.조이스틱  (2) 2019.02.08
[Programmers]Lv 1.문자열 내 마음대로 정렬하기  (0) 2019.02.07
[Programmers]Lv 1.소수 찾기  (0) 2019.02.05
[Programmers]Lv 2.쇠막대기  (0) 2019.02.04
[Programmers]Lv 1. 시저 암호  (0) 2019.02.03
728x90
반응형

문제:

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

풀이 방법:

소수는 1과 자기 자신으로만 나누어지는 수이기 때문에 반복문을 사용해서 임의의 수 x가 소수인지 판별하는 방법은 2부터 x-1까지 나누어 보았을 때, 나머지가 생기지 않으면 된다. 따라서 다음과 같이 코드를 작성할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(n):
    answer=[]
    cnt=1
    while(cnt!=n):
        cnt+=1
        prime=True
        for i in range(2,cnt):
            if cnt%i==0:
                prime=False
                break
        if prime:
            answer.append(cnt)
    return len(answer)
cs

하지만 이 방법은 효율적이지 못한 방법이라 큰 수의 경우에는 통과를 하지 못한다.



 그 이유는 2부터 x-1까지 검사하기 때문에 엄청 큰 소수 인 경우 x-1까지 반복해야하기 때문이다.

하지만 수학적으로 생각해보면 만약 어떤 수의 약수가 존재한다면 x-1까지 검사할 필요 없이 sqrt(x)까지만 검사를 해보아도 충분하다는 것을 알 수 있다.

따라서 위 코드를 다음과 같이 수정을 하였다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
def solution(n):
    import math
    answer=[2]
    cnt=1
    while(cnt!=n):
        cnt+=1
        prime=True
        for i in range(2,math.ceil(math.sqrt(cnt))+1):
            if cnt%i==0:
                prime=False
                break
        if prime:
            answer.append(cnt)
    return len(answer)
cs


math에 있는 루트 함수인 sqrt와 올림 함수인 ceil을 사용해서 범위를 잡아 주었다. 그러면 다음과 같이 큰 수의 경우에도 통과를 하는 것을 알 수 있다.



 하지만 이 방법이 소수를 판별하는 문제에서 최적의 효율을 나타내지는 않는다. 소수를 판별하는 문제에서 가장 효율이 좋은 코드는 '에라토스테네스의 체' 원리를 사용하는 것이다. 소수가 1과 자기 자신으로 나누어 지는 수라고 가정하면 소수가 아닌 수는 임의의 소수 하나로 나눌 수 있다는 말이 된다. 따라서 2부터 x-1까지 나누어보는 것이 아닌 소수 배열을 만들어서 임의의 소수로 나누어 지지 않는다면 소수가 된다는 것이다. 다음은 에라토스테네스의 체 원리를 이용해 작성한 코드다.


1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(n):
    answer=[]
    for i in range(2,n+1):
        prime=True
        for j in answer:
            if i%j == 0:
                prime=False
                break
            elif j > i**(1/2):
                break
        if prime:
            answer.append(i)
    return len(answer)
cs

다음

다음과 같이 더 빨리 통과함을 알 수 있다. 효율성 테스트에서는 더 빨리 통과한다는 것을 체감할 수 있다.

 


728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 1.문자열 내 마음대로 정렬하기  (0) 2019.02.07
[Programmers]Lv 2.주식 가격  (0) 2019.02.06
[Programmers]Lv 2.쇠막대기  (0) 2019.02.04
[Programmers]Lv 1. 시저 암호  (0) 2019.02.03
[Programmers]Lv 2.프린터  (0) 2019.02.02

+ Recent posts

티스토리툴바