문제:

숫자 야구 게임이란 2명이 서로가 생각한 숫자를 맞추는 게임입니다.

각자 서로 다른 1~9까지 3자리 임의의 숫자를 정한 뒤 서로에게 3자리의 숫자를 불러서 결과를 확인합니다. 그 결과를 토대로 상대가 정한 숫자를 예상한 뒤 맞힙니다.

* 숫자가 맞지만, 위치가 틀렸을 때는 볼
* 숫자와 위치가 모두 맞을 때는 스트라이크
* 숫자와 위치가 모두 틀렸을 때는 아웃

질문한 세 자리의 수, 스트라이크의 수, 볼의 수를 담은 2차원 배열 baseball이 매개변수로 주어질 때, 가능한 답의 개수를 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

완전 탐색 문제이므로 모든 경우의 수를 따져주면 된다. 우선 123~987까지 모든 경우를 만들어준다(중복은 허용하지 않는다)
이 후 123에 대해 1S, 1B인 경우들만 살려두고 나머지는 0으로 만들어 제거해버린다. 예를 들면 125이면 2S이므로 0으로 바뀌고 142와 같은 경우가 1S 1B이므로 살려둔다. 이와 같은 방법으로 baseball에 있는 모든 경우를 진행한 뒤 남은 경우의 길이를 반환하면 된다.

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
def solution(baseball):
    answer=[]
    for i in range(1,10):
        for j in range(1,10):
            for k in range(1,10):
                if (i==k or i==j or j==k):
                    pass
                else:
                    answer.append(str(i*100+j*10+k))
    for i in baseball:
        for j in range(len(answer)):
            st_cnt=0
            bl_cnt=0
            for k in range(3):
                for l in range(3):
                    if (answer[j][k]==str(i[0])[l] and k==l):
                        st_cnt+=1
                    elif (answer[j][k]==str(i[0])[l] and k!=l):
                        bl_cnt+=1
            if st_cnt==int(i[1]) and bl_cnt==int(i[2]):
                pass
            else:
                answer[j]=0
        answer=list(set(answer))
        if (0 in answer):
            answer.remove(0)
        else:
            pass
    return len(answer)
cs


저작자표시 비영리 동일조건

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

[Programmers]Lv 2. 구명 보트  (0) 2019.02.24
[Programmers]Lv 3.타일 장식물  (0) 2019.02.23
[Programmers]Lv 3. 2 X N 타일링  (0) 2019.02.21
[Programmers]Lv 2. 위장  (0) 2019.02.20
[Programmers]Lv 1.N으로 표현  (0) 2019.02.19

문제:

가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

타일을 가로로 배치 하는 경우
타일을 세로로 배치 하는 경우

직사각형 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

풀이 방법:

보통 이러한 문제는 패턴이 있기 때문에 패턴을 찾으려고 했다.
n이 1일때 1가지 방법,     2일 때 2가지 방법,     3일 때 3가지 방법,     4일 때 5가지 방법,     5일 때 8가지 방법...

1,2,3,5,8,13,.....

n이 증가함에 따라 방법의 갯수는 피보나치 수열을 따르면서 증가하고 있었다. 즉 피보나치를 활용해서 풀면 된다. 다음과 같이 간단하게 구할 수 있다.

1
2
3
4
5
def solution(n):
    a,b=1,1
    for i in range(n):
        a,b=b,a+b
    return a%1000000007
cs
 


저작자표시 비영리 동일조건

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

[Programmers]Lv 3.타일 장식물  (0) 2019.02.23
[Programmers]Lv 2. 숫자 야구  (0) 2019.02.22
[Programmers]Lv 2. 위장  (0) 2019.02.20
[Programmers]Lv 1.N으로 표현  (0) 2019.02.19
[Programmers]Lv 2. H-Index  (0) 2019.02.18

문제:

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

해시 태그를 가진 문제이므로 clothes를 해시로 바꾸었다. 의상의 이름은 문제에서 크게 필요하지 않으므로 의상의 종류가 몇 개있는지를 나타내는 딕셔너리 타입으로 바꾸었다. 해시 타입인 count에 있으면 그 의상의 종류에 +1을 하고 없다면 새로 추가하도록 하였다.
각 의상별로 갯수를 파악했으면 경우의 수 문제이므로 다음과 같이 구할 수 있다.
입출력의 예시 중 첫번째이다.

 eyewear       |    headgear 

 안입는다

yellow_hat 

green_turban 

 안입는다.

안입는다 

yellow_hat

green_turban

 blue_sunglasses

blue_sunglasses 

blue_sunglasses+yellow_hat 

blue_sunglasses+green_turban 


이 중 하나도 안 입는 경우는 없으므로 이 경우만 제외해야 한다.

즉 각 의상의 종류에 1씩 더한 값들을 모두 곱한 뒤에 하나도 안 입는 경우를 제거해야 하므로 -1을 빼서 반환하도록 한다.


1
2
3
4
5
6
7
8
9
10
11
12
def solution(clothes):
    count={}
    for i in clothes:
        if i[1] in count:
            count[i[1]]+=1
        else:
            count[i[1]]=1
    count_list=count.values()
    answer=1
    for i in count_list:
        answer*=i+1
    return answer-1
cs


저작자표시 비영리 동일조건

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

[Programmers]Lv 2. 숫자 야구  (0) 2019.02.22
[Programmers]Lv 3. 2 X N 타일링  (0) 2019.02.21
[Programmers]Lv 1.N으로 표현  (0) 2019.02.19
[Programmers]Lv 2. H-Index  (0) 2019.02.18
[Programmers]Lv 2.전화번호 목록  (0) 2019.02.16

문제:

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 +(5/5) +(5/5)
12 = 55/5 + 5/5
12 = (55 + 5)/5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

풀이 방법:

이 문제는 절대로 1단계에 있을 문제라고 생각이 들지 않는다.

숫자를 표현하는 방법에는 총 5가지가 있다.

1. 더하기 2. 곱하기 3. 빼기 4.나누기 5. 숫자 붙이기

따라서 위 방법에 따라 숫자를 생성하는 generator(N,n) 이라는 함수를 만들었다. 이 함수는 숫자 N과 그 숫자를 사용할 횟수 n이 주어지면 N을 n개 사용해서 생기는 모든 경우를 반환해준다.
DP(동적계획법)을 사용하는 문제임을 인지하고 풀었다. 최솟값이 8보다 크면 -1을 반환하기에 경우의 수가 엄청 많지는 않다.
예를 들어 N을 4번 사용해서 number를 만들 수 있다고 하자. generator(N,4) 는 generator(N,3)에다가 N을 하나씩 더 연산해준 것이다. 즉 3+1=4 연산을 했다. 하지만 2+2=4 인 경우도 있다. 하지만 내가 고안한 generator로는 2+2를 바로 얻을 수 없기 때문에 generator(N,2) 2개를 활용해 얻도록 하였다.
또한 작은 경우에서부터 시작하므로 answer의 min 값보다 큰 경우를 시행하는 경우에는 break로 바로 빠져 나오도록 하였다.

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
def generator(N,n):
    answer = [N]
    if n==1:
        return answer
    for i in range(2,n+1):
        temporary=[]
        for j in answer:
            temporary.append(j+N)
            if abs(j-N)!=0:
                temporary.append(abs(j-N))
            a,b=max(j,N),min(j,N)
            temporary.append(a//b)
            temporary.append(j*N)
        answer+=temporary
        answer.append(int(str(N)*i))
    return answer
 
def solution(N, number):
    answer= [9]
    if N==number:
        return 1
    for i in range(1,8):
        if number in generator(N,i):
            answer.append(i)
    for i in range(2,5):
        answer1=generator(N,i)
        for j in range(i,9-i):
            answer2=generator(N,j)
            if min(answer)<i+j:
                pass
            else:
                temporary=[]
                for l in answer2:
                    for k in answer1:
                        temporary.append(k+l)
                        temporary.append(abs(k-l))
                        c,d=max(l,k),min(l,k)
                        if d!=0:
                            temporary.append(c//d)
                        temporary.append(l*k)
                if number in temporary:
                    answer.append(i+j)
    if answer==[9]:
        return -1
    else:
        return min(answer)
        return min(answer)
cs


저작자표시 비영리 동일조건

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

[Programmers]Lv 3. 2 X N 타일링  (0) 2019.02.21
[Programmers]Lv 2. 위장  (0) 2019.02.20
[Programmers]Lv 2. H-Index  (0) 2019.02.18
[Programmers]Lv 2.전화번호 목록  (0) 2019.02.16
[Programmers]Lv 1.모의고사  (0) 2019.02.15

문제:

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과에 따르면 H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n 편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h가 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

 어려운 알고리즘을 필요를 하지는 않는다. 반복문을 활용해서 풀면 된다. 첫 반복문을 설정할 때 정렬을 한 뒤 citations의 길이부터 거꾸로 진행을 하도록 하였다. 또한 문제에서 딱히 말은 없었지만 H-Index가 여러개라면 최댓값을 리턴해야하므로 배열에 담아서 최대값을 반환하도록 하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(citations):
    answer=[]
citations.sort(reverse=True)
    for i in range(len(citations),0,-1):
        count=0
        for j in citations:
            if j >= i:
                count+=1
        if count <= i:
            answer.append(count)
        else:
            count=0
            answer.append(count)
    return max(answer)
cs


저작자표시 비영리 동일조건

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

[Programmers]Lv 2. 위장  (0) 2019.02.20
[Programmers]Lv 1.N으로 표현  (0) 2019.02.19
[Programmers]Lv 2.전화번호 목록  (0) 2019.02.16
[Programmers]Lv 1.모의고사  (0) 2019.02.15
[Programmers]Lv 2. 소수 찾기  (0) 2019.02.14

문제:

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

해시를 사용해서 푸는 문제이므로 Python의 set의 특징을 이용한다면 쉽게 풀 수 있었다. Python에서의 set은 중복을 제거해주고, 차집합과 같은 연산도 지원을 해주었다. set을 통해서 중복을 제거할 수 있다는 특징을 이용해서 동명이인이 완주를 못 한 사람인지 아닌지를 판단 할 수 있다. 두 개의 배열에 set을 취한 뒤 차집합을 해주었을 때, 1이라면 동명이인이 범인이 아닌경우이며, 0이라면 동명이인이 범인인 경우이다.
따라서 이를 판별하기 전에 각각의 배열을 정렬해준 뒤에 차집합의 길이가 1이라면 두 개의 차 집합에서 남은 사람이 완주를 하지 못한 사람이며, 0일 경우에는 하나씩 탐색했을 때 서로 다른 부분에서 완주를 하지 못한 사람을 찾을 수 있다.

1
2
3
4
5
6
7
8
9
10
def solution(participant,completion):
    participant.sort()
    completion.sort()
    if not bool(set(participant)-set(completion)):
        for i in range(len(completion)):
            if participant[i]!=completion[i]:
                return participant[i]
    else:
        answer=list(set(participant)-set(completion))[0]
    return answer
cs


저작자표시 비영리 동일조건

'Algorithm' 카테고리의 다른 글

[BOJ]11559. Puyo Puyo  (0) 2021.09.07
[BOJ]3190. 뱀  (0) 2021.08.19
[BOJ]1520. 내리막길  (0) 2021.08.17
[BOJ]1987. 알파벳  (0) 2021.08.10
[BOJ]14425. 문자열 집합  (0) 2021.06.24

문제:

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대: 119
박준영: 97 674 223
지영석: 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true return 하도록 solution 함수를 작성해주세요.

풀이 방법:

해시를 사용해서 푸는 문제이지만 해시를 사용할 필요가 전혀 없는 문제이다.
단순히 이중 반복문을 통해서 검사를 진행해도 정확성, 효율성을 문제없이 통과 할 수 있다.

1
2
3
4
5
6
7
8
9
10
def solution(phone_book):
    answer = True
    phone_book.sort()
    for i in range(len(phone_book)-1):
        for j in range(i+1,len(phone_book)):
            if phone_book[i] in phone_book[j]:
                answer=False
        if answer==False:
            break
    return answer
cs


저작자표시 비영리 동일조건

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

[Programmers]Lv 1.N으로 표현  (0) 2019.02.19
[Programmers]Lv 2. H-Index  (0) 2019.02.18
[Programmers]Lv 1.모의고사  (0) 2019.02.15
[Programmers]Lv 2. 소수 찾기  (0) 2019.02.14
[Programmers]Lv 1. 체육복  (0) 2019.02.13

문제:

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다.
수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1,2,3,4,5,1,2,3,,4,5....
2번 수포자가 찍는 방식: 2,1,2,3,2,4,2,5,2,1,2,3,2,4,2,5....
3번 수포자가 찍는 방식: 3,3,1,1,2,2,4,4,5,5,3,3,1,1,2,2,4,4,5,5....

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answer가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

문제가 완전탐색을 활용하여 푸는 것이므로, 모든 경우의 수를 다 따져주면 된다.
수포자의 패턴 리스트를 만든 후에 answers 보다 충분히 크게만 만들어주면 된다. 이후 반복문을 활용해서 맞은 사람의 값만 1씩 올려준 뒤 가장 큰 값의 인덱스를 answer_list에 넣으면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution(answers):
    answer = [0,0,0]
    answer_list=[]
    supoja_1=list(range(1,6))*2*((len(answers)//10)+1)
    supoja_2=[2,1,2,3,2,4,2,5]*((len(answers)//8)+1)
    supoja_3=[3,3,1,1,2,2,4,4,5,5]*((len(answers)//10)+1)
    for i in range(len(answers)):
        if answers[i]==supoja_1[i]:
            answer[0]+=1
        if answers[i]==supoja_2[i]:
            answer[1]+=1
        if answers[i]==supoja_3[i]:
            answer[2]+=1
    for i in range(len(answer)):
        if answer[i] == max(answer):
            answer_list.append(i+1)
        else:
            pass
    return answer_list
cs


저작자표시 비영리 동일조건

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

[Programmers]Lv 2. H-Index  (0) 2019.02.18
[Programmers]Lv 2.전화번호 목록  (0) 2019.02.16
[Programmers]Lv 2. 소수 찾기  (0) 2019.02.14
[Programmers]Lv 1. 체육복  (0) 2019.02.13
[Programmers]Lv2. 큰 수 만들기  (0) 2019.02.12

문제:

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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


저작자표시 비영리 동일조건

'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

문제:

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

예를 들어, 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일 이후로 테스트 케이스가 추가되었다.


저작자표시 비영리 동일조건

'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

+ Recent posts

티스토리툴바