문제:

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

스파이가 가진 의상들이 담긴 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[1in 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

문제:

어떤 숫자에서 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



'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

문제:

배열 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


'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

+ Recent posts