1. 문제 해석
추가로 정점을 하나 생성하여 각 그래프의 특성에 따라 간선을 연결하고 번호를 부여한다. 이때 주어진 간선 정보를 바탕으로 각 그래프 형태에 대한 정보를 계산한다.
예를 들어, 다음과 같은 간선 입력이 들어온다.
이 간선 정보를 가지고 그래프를 그리면 아래와 같다.
여기서 우리는 2가 추가 된 임의의 정점이라는 것을 알 수 있고, 3-4 막대그래프와 1번 도넛 그래프가 하나 있다는 것을 알 수 있다.
아래 그래프도 마찬가지이다.
4번이 추가된 정점임을 알 수 있고, 2번 막대그래프 하나 그리고 8자 모양 그래프 두 개가 있다.
이 정보들을 출력하면 된다.
2. 문제 접근
범위가 1 ≤ edges의 길이 ≤ 1,000,000으로 주어졌고, 최대 Nlog(N)의 알고리즘을 이용해야 한다.
해당 문제는 어떤 정점이 몇개의 간선을 가지고 있느냐로 구분 지어야 하기 때문에 딕셔너리를 이용하기로 한다.
3. 알고리즘 풀이
문제를 살펴보면, 먼저 추가된 정점을 찾아야 구분짓기가 편할 것 같다.
추가된 정점은 그래프 개수만큼 나가는 간선을 가지고 있고 들어오는 간선은 없다.
그렇다면 다른 그래프는 어떨까?
먼저 막대그래프 또한 들어오는 간선만 있고 나가는 간선이 없는 정점을 하나씩 가지고 있는 것으로 보인다.
8자 그래프는 2개 이상 들어오고, 2개가 나가는 정점을 하나씩은 가지고 있다.
마지막으로 도넛 그래프는 전체 그래프의 개수 중에 (막대그래프 + 8자 그래프) 개수를 뺀 것과 같다.
전체 그래프의 개수는 임의 정점에서 나가는 간선의 개수와 같다.
def solution(edges):
answer = [0,0,0,0]
edge={}
# 오가는 간선의 개수를 파악
for a,b in edges:
if not edge.get(a):
edge[a]=[0,0]
if not edge.get(b):
edge[b]=[0,0]
edge[a][0] +=1
edge[b][1] +=1
for key, value in edge.items():
# 임의의 정점
if value[0]>=2 and value[1]==0:
answer[0]=key
# 막대 그래프
elif value[0]==0 and value[1]>=1:
answer[2]+=1
# 8자 그래프
elif value[0]==2 and value[1]>=2:
answer[3]+=1
answer[1] = edge.get(answer[0])[0]-(answer[2]+answer[3])
return answer이번 문제는 딕셔너리에 대해 연습해볼 기회가 되었다.
.items() 함수와 .get() 가 어떤 기능을 하는지 확실하게 짚고 넘어가야겠다.
items()는 어떤 key와 value의 값이 있는지 확인한다.
keys() 와 values()도 있다. 이는 어떤 key와 value가 있는지 각각 확인한다.
.get()은 보통 없는 key에 접근할 때 발생하는 오류를 막기 위해서 사용된다. print(edge['a'])를 하게 되면 a의 value를 출력하는데, 이때 a라는 key가 없다면 오류가 발생한다.
여기서 사용된 원리는edge.get(a)라고 사용하면, key='a'가 있다면 True 없다면 False를 반환한다.
- 딕셔너리 Values 에서 가장 큰 값은 max(my_dict.values())
- Keys 에서 가장 큰 키는 max(my_dict, key=my_dict.get)이다.
- dict정렬은 키 값으로 정렬 dict(sorted(my_dict.items()))
- values 값으로 정렬 dict(sorted(my_dict.items(), key=lambda item: item[1]))
