정점에 해당하는 n, 간선에 해당하는 computers를 줄테니 그래프의 연결 요소에 해당하는 네트워크의 개수를 구하라는 문제이다.
즉 그래프의 정보를 줄테니 모든 연결 요소의 개수를 구하라는 소리고, 연결 요소의 개수를 구하는 방법은 모든 정점을 살펴보면서 이미 방문한 정점이면 넘어가고, 방문하지 않은 정점이면 해당 정점에 대해 dfs (혹은 bfs) 탐색을 시행해 해당 정점, 연결된 정점들을 전부 다 방문한 정점으로 바꿔주고 연결 요소의 개수를 하나 늘려주면 된다.
인접 배열, 인접 리스트, 간선 리스트등으로 그래프의 연결 상태를 표현할 수 있고 이 문제에서는 인접 배열로 주어짐을 고려하면서 문제를 해결하였다.
소스 코드
def dfs(x, n, computers, check):
check[x] = True
for i in range(n):
if computers[x][i] and not check[i]:
dfs(i, n, computers, check)
def solution(n, computers):
answer = 0
check = [False for _ in range(n)]
for i in range(n):
if not check[i]:
answer += 1
dfs(i, n, computers, check)
return answer
양수들의 집합 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
정점 수, 간선 수, 시작 점을 입력 받고 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=' ')
문자열에 포함된 각 단어의 짝수번째 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)
나올 수 있는 최대 수까지 에라토스테네스의 체를 사용해 소수를 미리 구해준 후, 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)))
숫자의 앞자리 수가 큰 순서대로 정답 문자열에 추가하면 될 것 같지만 숫자의 앞자리 수가 같은 숫자를 어떻게 처리할지가 애매하다. 입출력 예 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)))
음식을 섞어가면서 모든 음식이 스코빌 지수 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) 알고리즘으로 문제를 해결할 수 있고, 효율성 테스트도 통과할수가 있게 된다.
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
딕셔너리를 하나 만들고, 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