def solution(n, lost, reserve):
new_lost = list(set(lost) - set(reserve))
new_reserve = list(set(reserve) - set(lost))
for i in new_reserve:
if i-1 in new_lost:
new_lost.remove(i-1)
elif i+1 in new_lost:
new_lost.remove(i+1)
return n - len(new_lost)
def solution(n, lost, reserve):
new_lost = list(set(lost) - set(reserve))
new_reserve = list(set(reserve) - set(lost))
for i in new_reserve:
if i-1 in new_lost:
new_lost.remove(i-1)
elif i+1 in new_lost:
new_lost.remove(i+1)
return n - len(new_lost)
> lost 변수와 reserve 변수 모두 set 으로 변형해서 차집합을 new_lost 변수에서, 그리고 reserve 변수와 lost 변수의 위치를 바꿔서 차집합을 진행해서 new_reserve 변수를 만들어주었습니다.
> 이런 작업을 한 이유는 lost 변수와 reserve 변수에서 동일한 값이 존재할 수 있기 때문에 두 변수에서 나온 중복값을 제거하기 위해서 코드를 작성한 것이다.
> new_reserve 반복문을 사용해서 여벌의 옷을 가지고 있는 학생을 한 명씩 추출합니다.
> 거기서 i -1 , i + 1 을 if 문으로 설정해서 new_lost (도둑맞은 학생 리스트)에 있으면 new_lost 변수에서 해당하는 값을 pop 시켜줍니다.
> 그러면 new_lost에는 도둑맞은 학생 중 여벌의 옷을 가지고 있는 학생에게 빌려입지 못한 학생들만 남게됩니다.
> 처음에 for문을 new_reserve가 아닌 new_lost 로 하니까 코드도 길어지고 결과값도 도출하지 못했습니다.
from collections import deque
import sys
input = sys.stdin.readline
# N, M, V
n, m, v = map(int, input().split())
graph = [ [] for i in range(n+1)]
for i in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
for i in graph:
if not i:
continue
else:
i = i.sort()
def dfs(graph, v, visited):
visited[v] = True
print(v, end= ' ')
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
def bfs(graph, start, visited):
queue = deque([start])
visited[start]= True
while queue:
v = queue.popleft()
print(v, end = ' ')
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
visited = [False] * (n + 1)
dfs(graph, v, visited)
print()
visited = [False] * (n + 1)
bfs(graph, v, visited)
코드 설명
from collections import deque
import sys
input = sys.stdin.readline
> 큐를 사용하기 위해서 deque 모듈을 불러왔고, 빠른 데이터 입력을 위해서 sys 모듈을 불러왔습니다.
> input = sys.stdin.readline 코드는 데이터를 빠르게 입력할 수 있는 코드입니다.
n, m, v = map(int, input().split())
graph = [ [] for i in range(n+1)]
> n, m, v 변수는 정점의 개수, 간선의 개수, 탐색을 시작할 정점의 번호를 의미하는 변수입니다.
> graph 변수는 정점끼리 연결된 그래프 정보를 의미하는 변수입니다.
> [ [] for i in range(n+ 1) ] 로 코드를 작성한 이유는 정점의 수는 1부터 시작하기 때문에 range(n + 1)로 기존의 길이보다 1을 추가해서 빈 리스트를 만들었습니다.
for i in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
> 간선의 개수만큼 반복문을 진행하기 위해서 for문을 사용했습니다.
> a, b는 연결되는 정점을 의미하는 각 정점입니다.
> 여기부분에서 굉장히 에러가 많이 발생했습니다.
> 처음에 graph[a].append(b) 만 작성하고 아래 graph[b].append(a)는 작성하지 않았습니다.
> 이렇게 되면 단방향 그래프가 되는데 예제 입력 2에서 에러가 계속 발생하게 됩니다.
> 양방향 그래프를 만들어주기 위해서 graph[b].append(a) 코드를 추가로 작성을 해주었습니다.
for i in graph:
if not i:
continue
else:
i = i.sort()
> 예제 출력에서 보시면 각 정점에서의 출력이 오름차순으로 출력됨을 인지할 수 있습니다.
> 그러므로, 각 정점에서 연결된 정점들을 오름차순으로 정렬해주기 위해서 반복문 for문을 사용하였습니다.
def dfs(graph, v, visited):
visited[v] = True
print(v, end= ' ')
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
def bfs(graph, start, visited):
queue = deque([start])
visited[start]= True
while queue:
v = queue.popleft()
print(v, end = ' ')
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
> 이 dfs, bfs 코드는 '이것이 코딩테스트다' 책에서 나온 코드를 그대로 외워서 작성했습니다. 이런건 외우는거 밖에 답이 없는거 같습니다 ㅜㅜ
import sys
input = sys.stdin.readline
# 파일의 개수 N 입력
n = int(input())
file_dict = {}
for i in range(n):
file_n = input().split('.')[1].replace('\n', '')
if file_n not in file_dict.keys():
file_dict[file_n] = 1
else:
file_dict[file_n] += 1
result = sorted(list(file_dict.keys()))
for i in result:
print(i + ' ' + str(file_dict[i]))
코드 설명
import sys
input = sys.stdin.readline
> 'sys.stdin.readline' 코드는 데이터를 빠르게 입력할 수 있는 코드입니다. 대량의 데이터를 입력받아야 하는 문제일 때를 대비해서 항상 작성하고 있습니다.
n = int(input())
file_dict = {}
> 변수 n 은 파일의 개수를 받기 위한 변수입ㄴ디ㅏ.
> file_dict 변수는 파일의 확장자별 수를 저장하기 위해서 빈 dict 자료형을 만들었습니다.
for i in range(n):
file_n = input().split('.')[1].replace('\n', '')
if file_n not in file_dict.keys():
file_dict[file_n] = 1
else:
file_dict[file_n] += 1
> 파일의 개수만큼 파일을 받기 위해서 for문을 사용하였습니다.
> 파일이 'sbrus.txt' 와 같이 들어오는데 이 중에 필요한 'txt' 와 같은 확장자명입니다.
> 그래서 input().split('.')[1] 을 사용하면 결과가 ['sbrus', 'txt\n'] 으로 나오는데 그 뒤에 나오는 값을 추출한 것이다.
> 처음에 input().split('.')[1]을 하면 'txt'로만 나오는 줄 알았는데 'txt\n'으로 결과가 나와서 놀랐다.
> 그래서 replace('\n', '')을 사용해서 '\n' 을 제거해주었다.
> 그리고 if-else문을 사용해서 file_dict.keys()에 확장자명이 없다면 file_dic[file_n] = 1로 설정해주고, 있다면 file_dict += 1로 설정해주었습니다.
> 이렇게 하면 확장자별 수를 file_dict 변수에 담을 수 있게 됩니다.
result = sorted(list(file_dict.keys()))
> 확장자 이름을 사전순으로 출력해야 하므로, sorted(list(file_dict.keys())) 를 사용해서 확장자명만 추출해서 오름차순으로 정렬된 값을 result 변수에 담았습니다.
for i in result:
print(i + ' ' + str(file_dict[i]))
> 확장자 이름이 사전순으로 정렬된 변수 result를 for문을 사용해서 사전순으로 출력시켰습니다.
> 원하는 출력값에 맞게 print(i, file_dict[i]) 를 사용해서 확장자명과 확장자 파일의 개수를 출력시켰습니다.
import sys
# pypy3 해결.. python(3%) 시간초과
# 대각선의 퀸이 있는지 확인
def check(x):
for i in range(x):
if abs(graph[x] - graph[i]) == x - i:
return False
return True
# 체스 판의 열을 dfs 탐색
def dfs(queen):
global res
# n번째 퀸을 놓으려 한다면 리턴 (n개의 퀸을 놓았기 때문.)
if queen == n:
res += 1 # 방법의 수 카운트
return
# 모든 체스판의 열을 확인
for i in range(n):
# i 번째 열의 퀸을 놓지 않았다면
if not visited[i]:
graph[queen] = i # (queen, i)에 퀸을 둔다.
# 대각선의 겹치는 퀸이 있는지 확인
if check(queen):
# 백 트래킹
visited[i] = True # 퀸을 놓는다.
dfs(queen + 1) # 재귀적으로 퀸을 놓을 수 있는 열을 찾는다.
visited[i] = False # 재귀 탐색 후 퀸을 n개 놓을 수 없다면 퀸을 놓지 않는 것으로 초기화 후 다른 열을 탐색
n = int(sys.stdin.readline())
graph = [0 for _ in range(n)] # n번째 열의 퀸의 위치
visited = [False for _ in range(n)] # 체스판의 탐색 여부
res = 0 # 퀸을 놓는 방법의 수
dfs(0)
print(res)
def check(x):
for i in range(x):
if abs(graph[x] - graph[i]) == x - i:
return False
return True
> 이 코드는 대각선의 퀸이 있는지 확인하는 코드이다. 일단 퀸은 상하좌우 대각선 모두 움직일 수 있다.
> for문을 사용해서 x의 길이만큼 반복문을 진행한다.
> abs(graph[x] - graph[i]) == x - i 의 의미는 두 값이 같게 된다면 대각선이라는 의미이다. 솔직히 아직도 이해가 잘안됐닼ㅋㅋ
> 반복문을 통과한다면 True, 아니면 False
# 체스 판의 열을 dfs 탐색
def dfs(queen):
global res
# n번째 퀸을 놓으려 한다면 리턴 (n개의 퀸을 놓았기 때문.)
if queen == n:
res += 1 # 방법의 수 카운트
return
# 모든 체스판의 열을 확인
for i in range(n):
# i 번째 열의 퀸을 놓지 않았다면
if not visited[i]:
graph[queen] = i # (queen, i)에 퀸을 둔다.
# 대각선의 겹치는 퀸이 있는지 확인
if check(queen):
# 백 트래킹
visited[i] = True # 퀸을 놓는다.
dfs(queen + 1) # 재귀적으로 퀸을 놓을 수 있는 열을 찾는다.
visited[i] = False # 재귀 탐색 후 퀸을 n개 놓을 수 없다면 퀸을 놓지 않는 것으로 초기화 후 다른 열을 탐색
import heapq
def solution(operations):
h = []
for i in operations:
a, b = i.split()
if a == 'I':
heapq.heappush(h, int(b))
else:
if len(h) > 0:
if b == '1':
h.pop(h.index(heapq.nlargest(1, h)[0]))
else:
heapq.heappop(h)
if len(h) == 0:
return [0, 0]
else:
return [heapq.nlargest(1, h)[0], h[0]]
for i in operations:
a, b = i.split()
if a == 'I':
heapq.heappush(h, int(b))
else:
if len(h) > 0:
if b == '1':
h.pop(h.index(heapq.nlargest(1, h)[0]))
else:
heapq.heappop(h)
> 값이 저장된 operations을 for문(반복문)을 사용하여 하나씩 값을 받게 합니다.
> i.split() 함수를 사용하여 a, b로 각 값을 받게 합니다.
> a == 'I' 일때는 값을 h변수에 넣으면 되는데, 최소, 최대값을 빼기 위해서는 heapq 모듈에서 heapq.heappush 를 사용했습니다.
> heapq.heappush 를 사용하면 출력하면 최소값이 먼저 빠지게 된다.
> 그리고 else문에는 a가 D일 경우이므로, b == -1이면 최소값 제거, b == 1이면 최댓값 제거이다.
> if len(h) > 0 을 사용한 이유는 최소값, 최대값 제거를 하다보면 h 리스트가 빈 값일 경우가 존재한다. 그 경우를 대비해서 len(h) >0 일때만 아래 코드가 수행되게 작성을 한 것이다.
> 다시 한 번 if - else문을 사용하여 b == 1일 때 , h.pop(h.index(heapq.nlargest(1, h)[0])) 을 사용하게 해준다.
> 먼저 heapq.nlargest(1, h) 의 의미는 h 리스트에서 최대값 1개를 출력하는 것이다. 만약 2개의 가장 큰 값이면 heapq.nlargest(2, h) 를 작성하면 된다.
> 이 코드는 리스트로 출력이 되기 때문에 heapq.nlargest(1, h)[0] 을 통해서 값만 출력하기 위해서 뒤에 [0]을 작성한 것이다.
> h.index() 를 해주면 h 변수에 있는 값의 index 위치를 출력시켜준다.
> 그 index를 h.pop(index)를 해주면 h 변수에서 해당하는 index 값이 빠져나가게 된다.
> 그러면, 최종적으로 h변수에서의 최댓값이 빠져나가게 되는것이다.
> else 문에서 heapq.heappop()을 해주면 h변수에 최소값이 출력하게 된다.
# N, M 입력
n, m = map(int, input().split())
s = []
def dfs():
if len(s) == m:
print(' '.join(map(str, s)))
return
for i in range(1, n + 1):
s.append(i)
dfs()
s.pop()
dfs()
> 처음으로 백트래킹 맞췄다!!!
> 점점 감을 잡아가는 듯!!!
코드 설명
n, m = map(int, input().split())
s = []
> 여기는 N과 M 값을 받는 변수이고, s 라는 빈 리스트를 생성해서 값을 출력시키기 위한 리스트입니다.
def dfs():
if len(s) == m:
print(' '.join(map(str, s)))
return
for i in range(1, n + 1):
s.append(i)
dfs()
s.pop()
> 이번 N과 M 문제는 중복되는 값이 나와도 될 뿐만 아니라, 같은 수가 나와도 된다는 점입니다.
> 이전에는 for 문 안에 if i not in s : 라는 if 문을 사용해서 같은 수를 제거하기 위한 코드를 작성했었는데, 이번에는 같은 수가 나와야 되므로 if문을 제거해주었습니다.
