greentea31's Note

https://programmers.co.kr/learn/courses/30/lessons/43165

풀이 과정

양수들의 집합 numbers에 들어있는 모든 수를 사용하여 target을 만드는 방법이 몇 가지 있는지를 구하는 문제이다.

1. 조합

numbers 내부의 모든 수를 다 더한 뒤 (numbers의 모든 수를 양수로 선택했다고 가정한 뒤) 조합으로 경우의 수를 만들어 보면서 선택한 양수를 음수로 바꿔볼 수 있다.

예를 들어 [3, 4, 5, 7]이면 3, 4, 5, 7 전부를 양수로 선택했을 경우의 값은 19이고, 여기서 4를 음수로 선택했다고 가정하면 19 - (4 * 2) = 11이 됨을 고려하며 (3), (4), (5), (7), (3, 4), (3, 5), ... , (3, 4, 5, 7)의 모든 순서쌍을 만들어보며 각 순서쌍 안의 숫자들을 음수로 선택했을 경우의 합을 생각해보고 target과 같은지 판단해 볼 수 있다.

2. DFS

[4, 1, 2, 1]이 있으면 DFS로

1. 4 혹은 -4를 선택

2. 1 혹은 -1을 선택

3. 2 혹은 -2를 선택

4. 1 혹은 -1을 선택

를 점검하면서 4개 모두 골랐을 경우의 합이 target과 같은지 판단하고 같으면 정답의 개수를 증가시키는 방법으로 문제를 해결할 수 있다.

소스 코드

1번 방법

from itertools import combinations


def solution(numbers, target):
    sum_value = sum(numbers)
    answer = 0
    target = (sum_value - target) // 2
    for length in range(1, len(numbers) + 1):
        for j in combinations(numbers, length):
            if sum(j) == target:
                answer += 1
    return answer

2번 방법

answer = 0


def dfs(numbers, target, discovered=[], depth=0):
    global answer
    if len(numbers) == depth:
        if sum(discovered) == target:
            answer += 1
        return
    dfs(numbers, target, discovered + [numbers[depth]], depth+1)
    dfs(numbers, target, discovered + [numbers[depth] * -1], depth+1)

def solution(numbers, target):
    dfs(numbers, target)
    return answer

https://www.acmicpc.net/problem/1260

풀이 과정

정점 수, 간선 수, 시작 점을 입력 받고 DFS, BFS를 사용했을 때의 순회 순서를 반환해주면 된다.

그래프의 간선을 파이썬의 딕셔너리를 활용하여 인접 리스트로 표현하고, DFS와 BFS를 통해 순회하였다. 방문할 수 있는 정점이 여러가지 인 경우 정점 번호가 작은 것을 먼저 방문하게 하려면 입력받은 인접 리스트를 정렬해주어야 한다.

소스 코드

from collections import deque
import sys

N, M, V = map(int, sys.stdin.readline().split())
g = {}
for i in range(N+1):
    g[i] = []
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    g[a].append(b)
    g[b].append(a)

for i in g.keys():
    g[i].sort()
    

def b_dfs(x, discovered=[]):
    discovered.append(x)
    for vertex in g[x]:
        if vertex not in discovered:
            discovered = b_dfs(vertex, discovered)
    return discovered


def b_bfs(start_x):
    discovered = [start_x]
    queue = deque([start_x])
    while queue:
        vertex = queue.popleft()
        for w in g[vertex]:
            if w not in discovered:
                discovered.append(w)
                queue.append(w)
    return discovered


a = b_dfs(V)
b = b_bfs(V)

for i in range(len(a)):
    if i == len(a) - 1:
        print(a[i])
        break
    print(f'{a[i]}', end=' ')
for i in range(len(b)):
    if i == len(b) - 1:
        print(b[i])
        break
    print(f'{b[i]}', end=' ')

https://programmers.co.kr/learn/courses/30/lessons/12930

풀이 과정

문자열에 포함된 각 단어의 짝수번째 index는 대문자로, 홀수번째 index는 소문자로 바꾼 문자열을 출력해주면 되는 문제다.

split(' ')으로 공백을 기준으로 문자열의 단어들을 나눠주고, upper(), lower()로 index에 따라 다르게 answer list에 삽입해준 뒤, answer list를 문자열로 전환해 출력하여 문제를 해결하였다.

소스 코드

def weird_letter(s):
    answer = []
    temp = s.split(' ')
    
    for word in temp:
        for index in range(len(word)):
            if index % 2 == 0:
                answer.append(word[index].upper())
            else:
                answer.append(word[index].lower())
        answer.append(' ')
    
    answer.pop()  # 문자열의 마지막에 붙는 공백 제거
    
    return ''.join(answer)

https://programmers.co.kr/learn/courses/30/lessons/42839

풀이 과정

numbers 문자열의 각 문자로 몇 개의 소수를 만들 수 있는지 반환해줘야 한다.

나올 수 있는 최대 수까지 에라토스테네스의 체를 사용해 소수를 미리 구해준 후, numbers의 각 문자로 만들 수 있는 모든 숫자의 쌍을 permutations 모듈을 이용하여 구해주었다. 그 후, 숫자가 소수면 정답 후보 리스트에 넣고, 정답 후보 리스트를 set으로 바꿔줬다가 list로 바꿔줘서 중복을 제거한 후, 리스트의 원소의 개수를 리턴하여 답을 구하였다.

소스 코드

from itertools import permutations


def solution(numbers):
    max_number = 10000001
    check = [False for _ in range(max_number)]
    check[0], check[1] = True, True
    
    for i in range(2, max_number):
        if not check[i]:
            for j in range(2*i, max_number, i):
                check[j] = True
                
    numbers = list(str(numbers))
    number_list = []
    
    for i in range(1, len(numbers) + 1):
        for j in permutations(numbers, i):
            temp = int(''.join(j))
            if not check[temp]:
                number_list.append(temp)
    
    return len(list(set(number_list)))

https://programmers.co.kr/learn/courses/30/lessons/42746

풀이 과정

숫자의 앞자리 수가 큰 순서대로 정답 문자열에 추가하면 될 것 같지만 숫자의 앞자리 수가 같은 숫자를 어떻게 처리할지가 애매하다. 입출력 예 2의 [3, 30, 34, 5, 9]에서 9, 5가 먼저 추가되야 하는것은 명확하지만 3, 30, 34를 34, 3, 30 순서대로 오게 해야할 것 같은데 처리를 어떻게 해줘야 할까?

0 <= numbers 원소 <= 1000임을 이용해서 숫자를 str으로 바꿔주고 *3으로 뒤에 같은 숫자를 붙여준 것을 통해 정렬하면 문제를 해결할 수 있다. 왜 *3인가? *2는 안되는가? 일단 *3의 예시를 생각해보면

[3, 30, 34, 5, 9] -> ['333', '303030', '343434', '555', '999']이고 이를 통해 왼쪽의 리스트를 정렬하면 [9, 5, 34, 3, 30]이 나오므로 이를 문자열로 합쳐주면 우리가 원하는 답을 얻을 수 있다.

[332, 3]을 생각해보자 3332가 이 리스트로 만들 수 있는 가장 큰 문자열이므로 3이 332보다 먼저 와야 한다. *3을 통해 정렬하면

[332, 3] -> ['332332332', '333'] 이므로 [3, 332]로 정렬이 된다. 하지만 *2를 통해 정렬하면

[332, 3] -> ['332332', '33'] 이 되므로 [332, 3]으로 정렬이 되게 된다. 이를 통해 답을 내면 3323이라는 잘못된 답이 나온다.

numbers의 원소가 10000까지 들어온다면 *4를 통해 정렬을 해주어야 할 것이다. 왜인지는 위의 설명과 유사한 반례를 들어 설명할 수 있을 것이다.

[0, 0, 0, 0]등의 input값에서 '0000'이라는 결과를 내는 것을 방지하기 위해 답은 int 타입으로 바꿔주었다가 다시 str로 바꿔주어야 한다.

소스 코드

def solution(numbers):
    str_numbers = [str(number) for number in numbers]
    str_numbers.sort(key=lambda x: x*3, reverse=True)
    return str(int(''.join(str_numbers)))

https://programmers.co.kr/learn/courses/30/lessons/42626

풀이 과정

음식을 섞어가면서 모든 음식이 스코빌 지수 K 이상이 되도록 하는 최소 섞음 횟수를 구해주면 된다.

리스트를 정렬하고, 리스트의 맨 앞이 K 이하이면 리스트의 0번째, 1번째 원소를 섞고 리스트에 넣은 다음에 다시 정렬해주고... 이런 방법이 떠오르지만 이렇게 문제를 풀면 음식을 섞을 때 마다 O(NlogN)인 정렬 과정을 거쳐야 하고 문제의 해결 알고리즘의 시간복잡도가 O(N^2logN)이 되어서 효율성 테스트를 통과할 수가 없다.

파이썬 내장 모듈인 heapq를 불러와 스코빌 리스트를 최소 힙으로 만든 후, 힙의 맨 위에 있는 음식의 스코빌 지수가 K 미만이면 heappop() 2번 해서 섞어주고 heappush() 해주고 다시 힙의 맨 위를 살펴보는 과정을 반복하는 방법으로 문제를 해결해 줄 수 있다.

리스트를 heap으로 만드는 heapify()가 O(NlogN), heappush()가 O(logN), heappop()도 O(logN)이므로 힙을 활용하여 문제를 해결하면 O(NlogN) 알고리즘으로 문제를 해결할 수 있고, 효율성 테스트도 통과할수가 있게 된다.

소스 코드

import heapq


def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while scoville[0] < K:
        if len(scoville) < 2:
            return -1
        bowl = []
        bowl.append(heapq.heappop(scoville))
        bowl.append(heapq.heappop(scoville))
        heapq.heappush(scoville, bowl[0] + 2*bowl[1])
        answer += 1

    return answer

https://programmers.co.kr/learn/courses/30/lessons/42586

풀이 과정

progresses를 deque에 담고 deque의 맨 앞이 100 이상이면 deque의 맨 앞이 100 이하가 될 때 까지 오늘 완료된 작업의 개수를 1 늘리고 정답 리스트에 넣었다.

deque의 맨 앞이 100 미만이라면, deque에 있는 모든 요소들을 해당하는 speeds만큼 증가 시켰다.

위의 두 작업을 progresses deque가 빌 때까지 반복하였다. 그냥 리스트를 사용하면 list의 맨 앞이 100 이상인 경우에 pop(0)을 사용해야 하는데 이는 시간복잡도가 O(N)인 코드이므로 O(1)인 popleft()를 사용하기 위해서 deque를 사용하였디.

소스 코드

from collections import deque


def solution(progresses, speeds):
    answer = []
    end_progresses = []
    deque1 = deque(progresses)
    while(deque1):
        answer_value = 0
        
        while deque1[0] < 100:
            deque2 = deque()
            for i in range(len(end_progresses), len(progresses)):
                deque2.append(deque1.popleft() + speeds[i])
            deque1 = deque2

        while deque1 and deque1[0] >= 100:
            answer_value += 1
            end_progresses.append(deque1.popleft())


        answer.append(answer_value)

    return answer

https://programmers.co.kr/learn/courses/30/lessons/42578

풀이 과정

딕셔너리를 하나 만들고, clothes를 확인하면서 옷의 종류를 키, 옷의 이름의 모음의 리스트를 밸류로 갖게끔 딕셔너리에 추가해준다.

{모자: [빨간 모자, 파란 모자, 노란 모자]

옷: [빨간 옷, 파란 옷]

바지: [빨간 바지, 파란 바지, 노란 바지]}

이렇게 딕셔너리가 만들어졌다고 생각해보자. 의상을 입는 조합의 수는 어떻게 구할 수 있을까? 처음 생각한 방법은 1번 방법이었지만 1번 방법으로는 이 문제를 해결할 수가 없다.

1. 조합

(모자), (옷), (바지), (모자, 옷), (모자, 바지), (옷, 바지), (모자, 옷, 바지)의 조합을 만들어 하나씩 골라 입는 경우의 수를 구하는 방법이 떠올랐다. 이를 위해 itertools에서 combintations 모듈을 가져와 1개 이상의 옷의 종류가 포함되어있는 모든 조합을 구한 뒤, 리스트의 길이를 통해 총 옷을 입는 조합의 가지수를 구했지만 테스트 케이스 1에서 시간 초과가 발생했다. 의상의 수가 30개까지 있을 수 있으므로 모두 다른 종류의 옷을 한 벌씩 가지고 있는 경우라면 30C1 + 30C2 + ... 30C15 + ... + 30C30 을 다 연산을 해야 하는데 이런 경우에 연산의 횟수가 너무 많아서 시간 초과가 발생한다. 테스트 케이스에서 1번 케이스를 제외하고는 옷의 종류가 많지 않아서 1번을 빼고는 다 통과가 가능하다.

2. 곱셈

가능한 조합의 경우는?

모자는 3가지 중에 1개를 고를 수 있고 하나도 안고를 수도 있다. (3+1)

옷은 2가지 중에 1개를 고를 수 있고 하나도 안고를 수도 있다. (2+1)

바지는 3가지 중에 1개를 고를 수 있고 하나도 안고를 수도 있다. (3+1)

그러면 답은 (3+1) * (2+1) * (3+1) - 1 = 47이 된다.

-1은 모자, 옷, 바지 전부 다 고르지 않은 경우를 제외해준 것이다. 문제에서 옷을 하나 이상은 입어야 된다는 조건을 주었기 때문이다.

이렇게 풀면 연산 횟수가 확 줄어서 모든 테스트 케이스를 통과할 수 있다.

소스 코드

1번

from itertools import combinations

def solution(clothes):
    answer = 0
    dictionary = {}
    dict_list = []
    
    for cloth in clothes:
        if cloth[1] in dictionary:
            dictionary[cloth[1]].append(cloth[0])
        else:
            dictionary[cloth[1]] = [cloth[0]]
    
    for value in dictionary.values():
        dict_list.append(value)
        
    for i in range(1, len(dict_list) + 1):
        for j in combinations(dict_list, i):
            temp1 = 1
            for k in j:
                temp1 *= len(k)
            answer += temp1
    
    return answer

2번

def solution(clothes):
    answer = 1
    dictionary = {}
    
    for cloth in clothes:
        if cloth[1] in dictionary:
            dictionary[cloth[1]].append(cloth[0])
        else:
            dictionary[cloth[1]] = [cloth[0]]
        
    for i in dictionary.values():
        temp = len(i) + 1
        answer *= temp
    
    answer -= 1
    
    return answer

https://programmers.co.kr/learn/courses/30/lessons/12926

풀이 과정

ord()로 문자의 아스키 코드를 감지할 수 있고, chr()로 아스키코드를 문자로 바꿀 수 있다.

A-Z의 문자는 아스키 코드로 65-90에 대응되고, a-z는 97-122에 대응됨을 이용하여 아스키 코드가 90, 122를 넘어가면 26을 빼줘서 처음으로 돌아가게끔 해주었다. n이 큰 수가 들어오는 조건이였다면 나머지 연산으로 문제를 해결해야 했겠지만 25까지 들어오기 때문에 그냥 범위를 넘어갈시 25를 빼주는 방법으로 문제를 해결할 수 있다.

소스 코드

def solution(s, n):
    answer = ''
    for letter in s:
        if letter == ' ':
            answer += ' '
            continue
        temp = ord(letter) + n
        if 'A' <= letter <= 'Z':  # letter.isupper()로도 판단 가능
            if temp > 90:
                temp -= 26
        else:  # letter.islower()로도 판단 가능
            if temp > 122:
                temp -= 26
        answer += chr(temp)

    return answer

https://programmers.co.kr/learn/courses/30/lessons/42577

풀이 과정

1. 정렬해서 풀기

처음 풀었을 때는 phone_book.sort(key=lambda x: len(x)) 방법으로 길이순으로 정렬하고 string.find() 명령어를 이용해서 풀었다. len(phone_book)이 4라고 한다면 (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)의 순서쌍에 대해 뒤의 인덱스가 앞의 인덱스의 문자열을 포함하고 있는지를 살펴봤으나 이렇게 풀면 문제를 잘못 읽은 것이다. 특정 전화번호가 다른 전화번호를 포함하고 있는지를 묻지 않았고 다른 전화번호로 시작했는지를 물어봤으니 다른 전화번호를 문자열 중간에 포함하고 있는 경우에 잘못된 답을 출력하게 된다.

그리고 위와 같은 순서쌍을 만들어서 비교하는 방법은 2중 for문을 돌려야 하는데 시간복잡도 문제때문에 효율성 테스트 3, 4번을 통과할 수 없다. 예전에는 효율성 테스트 3, 4번 케이스가 없었으므로 2중 for문으로 해결한 코드도 좀 보이는 것 같은데 지금은 for문을 2번 사용해서는 효율성 테스트에서 통과할 수가 없다.

파이썬에서 문자열에 대해 sort()를 사용하면 첫번째 문자에 대해 정렬, 첫번째 문자가 같다면 두번째 문자에 대해 정렬... 순으로 이루어진다 아래 예시를 보자

a = ['567', '88', '123', '1235', '12']

a.sort()

a = ['12', '123', '1235', '567', '88']

예시를 보면 이미 한번 정렬을 했으면 for문을 2번 돌릴 필요가 없다는 것을 알게 된다. 그냥 뒤의 문자열이 앞의 문자열로 시작하는지만 체크해주면 모든 문자열의 접두어 시작 여부를 알 수가 있게 된다.

2. 해쉬로 풀기

모든 전화번호를 딕셔너리에 넣은 후, 각 전화번호의 처음부터 일정 부분까지의 부분 문자열을 딕셔너리의 키 값으로 주고 딕셔너리를 조회하면서 각 전화번호의 부분 문자열이 다른 전화번호와 같은지 확인하면서 푸는 방법이 있다.

부분 문자열은 문자열과 같아서는 안된다. 그러면 부분 문자열이 문자열과 같아지면 딕셔너리에 항상 존재하게 되고, 한 번호가 다른 번호의 접두어인 경우가 아니더라도 접두어가 존재한다고 판단하게 된다.

만약에 처음부터 일정 부분까지의 부분 문자열이 다른 전화번호와 동일하다면 다른 전화번호가 문자열의 접두사가 된다.

소스 코드

1번

def solution(phone_book):
    answer = True
    phone_book.sort()
    length = len(phone_book)
    for i in range(length-1):
        if len(phone_book[i+1]) >= len(phone_book[i]) and phone_book[i+1][:len(phone_book[i])] == phone_book[i]:
            answer = False
            break
    return answer

2번

def solution(phone_book):
    answer = True
    phone_hash = {}
    
    for address in phone_book:
        phone_hash[address] = 1
    
    for address in phone_book:
        temp = ""
        if not answer:
            break
        for number in address:
            temp += number
            if temp in phone_hash and temp != address:
                answer = False
                break
    
    return answer