안녕하세요 구름알고리즘 먼데이 챌린지 3주차에 참여했습니다. 역시나 풀이를 진행해보겠습니다.
해당 게시물의 모든 출처는 구름 레벨의 알고리즘 먼데이 챌린지에 있습니다.
1번 문제
문제설명:
지인의 수가 짝수만큼 있다. 이때 다음의 규칙을 지키면서 최대한 많은 커플을 성사시키면 된다. 각각의 지인들은 모두 점수를 가지고 있다.
- 구름이의 지인의 수는 항상 짝수이다.
- 모든 점수는 0점을 제외한 정수이다.
- 지인들 중 같은 점수를 가지고 있는 경우는 없다.
- 만약에 n점이 있다면 -n이 항상 존재한다.
그러나 실수록 마지막 규칙을 지키질 못했다. 그래서 두사람이 소개팅을 못하게 되었다. 이떄, 구름이가 소개팅을 성사시키지못한 두명의 점수의 합을 구하시오.
해설:
문제 해설에 적혀있듯이 hash를 사용하면 쉽게 풀수있다. dictionary를 두개를 작성하고 모두 양수로 변환하여 dic2에 넣는다. 그리고, dic에도 대입을하는데 쌍이없는친구(처음나오는애)는 1로해서 대입을해준다. 그러면 그 1이있는 친구들이 바로 소개팅을 못한 친구이므로 한번의 탐색을 더해서 해결한다.
n = int(input())
dic = {}
dic2= {}
l1 = list(map(int,input().split()))
for k in l1:
dic2[abs(k)] = k
if abs(k) in dic:
dic[abs(k)] = dic[abs(k)]+1
else:
dic[abs(k)] = 1
total = 0
for k in dic:
if dic[k] == 1:
total = total + dic2[k]
print(total)2번 문제
문제설명:
다음과 같은 폴더폰의 자판이 있다.
이때, 버튼을 누르면 각 자판에서 다음 문자로 넘어간다.(처음으로 되돌아올수도있다) 어떤문자를 몇번눌렀는지를 입력을 줄때, 출력이 무엇일지를 확인하라.
해설:
옛날생각이 나게 만드는 문제이다. 우선 각 숫자에 알맞게 문자들이 들어있는 l1이라는 길이 9짜리 배열을 만들어놓았다. 그리고나서, for문을 통하여 전체 입력을 순회하면서, 앞뒤 글자가 같을때 count를 더해간다. 만약 앞뒤 글자가 다른것이나오면, 그러면 앞의 문자의 입력이 끝난것으로 이해하고, count만큼 입력을한것이 무엇인지를 찾아낸다. 이때 나머지 연산자를 사용하여 어떠한 수가 입력이됐을지를 indexing할수있다. 앞뒤글자를 비교해야하므로 마지막 인덱스에 패딩숫자 -1을 하나 넣어주었다.
l1 = [['1','.',',','?','!'],['2','A','B','C'],['3','D','E','F'],['4','G','H','I'],['5','J','K','L'],['6','M','N','O'],['7','P','Q','R','S'],['8','T','U','V'],['9','W','X','Y','Z']]
n = int(input())
res = ""
a = list(map(str,input()))
a.insert(n,-1)
tmp = a[0]
count = 1
for k in range(n):
if a[k] != a[k+1]:
res = res + l1[int(tmp)-1][(count%(len(l1[int(tmp)-1])))-1]
tmp = a[k+1]
count = 1
else:
count = count + 1
print(res)3번 문제
문제설명:
N개의 섬으로 이루어진 나라가있다. 각 섬에는 1부터 N까지의 번호가 붙어있고, 섬과 섬사이에 M개의 다리가 있다. 설치된 다리들은 다음과 같은 특징들을 만족한다
- 모든 다리는 양방향으로 이동할 수 있습니다.
- 서로 다른 두 섬을 잇는 다리는 최대 하나입니다.
- 다리가 잇는 두 섬은 항상 다른 섬입니다.
1번섬에서 출발해서 N번섬으로 가려고 하는데 통과하는 다리의 개수가 k개이하가 되길 원한다. k개이하의 다리로 도착할수있는지를 알아보자.
해설:
우선 그래프탐색 문제이다. 또한 어떻게 보면 최단거리문제이기도 하다. 최단거리로 N번섬에 도착했을때 k개이하의 다리를 이용했는지를 파악해서 결과만 내면 되기 때문이다. 따라서 최단거리 알고리즘으로 가장 유명한 다익스트라를 사용하였다.
다익스트라에는 각 다리마다 비용이 필요하다. 이문제에선 모든 다리가 똑같고, 다리의 개수가 중요하므로 다리하나의 비용이 1인것으로 해서 풀면된다. 또한 입력의 개수가 크지 않으므로 heap을 사용하지않고 최솟값 탐색하는 방식으로해서 다익스트라를 구현하였다.
해설에서는 BFS로 더 간략하게 탐색을 하였다... 이방법도 좋을듯싶다
n,m,k = map(int,input().split())
INF = int(1e9)
#비용이 1인 다리로 다익스트라 돌리기
start = 1
graph = [[] for i in range(n+1)]
visited = [False] * (n+1)
distance = [INF] * (n+1)
for _ in range(m):
a,b = map(int,input().split())
c = 1
graph[a].append((b,c))
graph[b].append((a,c))
def get_smallest_node():
min_value = INF
index = 0
for i in range(1,n+1):
if distance[i]<min_value and not visited[i]:
min_value = distance[i]
index = i
return index
def dijkstra(start):
distance[start] = 0
visited[start] = True
for j in graph[start]:
distance[j[0]] = j[1]
for i in range(n-1):
cur = get_smallest_node()
visited[cur] = True
for j in graph[cur]:
cost = distance[cur] + j[1]
if cost<distance[j[0]]:
distance[j[0]] = cost
dijkstra(start)
if distance[-1] <= k:
print("YES")
else:
print("NO")4번 문제
해설:
이 문제를 계속 분리집합문제라고 생각해서... 유니온-파인드를 억지로 구현하다가 결국 풀질 못했다... 생각해보면 그냥 탐색 돌리면서 방문한적있는점으로 돌아오는게 있는지를 확인하면되는것을... 너무 어렵게 생각한것 같다.
총평:
너무 어려워졌다 갑자기 하하하 큰일난듯 싶다 다음주부터
