[해커랭크] Journey to the Moon

문제 링크 : https://hackerrank.com/challenges/journey-to-the-moon

참고 : https://www.snoopybox.co.kr/1766

 

유형 : Algorithms > Graph Theory
난이도 : Medium

---

1. 문제 설명

문제는 링크타고 들어가면 자세히 볼 수 있고, 나중에 다시 볼 나를 위해 대략 설명하겠다.

4 1
0 2

위와 같은 예시가 있다고 했을 때, 결과는 5가 나와야 하는데 왜 5가 나와야 하는지 알아보자!

 

첫 번째 줄에 있는 숫자 2개 중 첫 번째(4)는 우주비행사 수를 나타내고, 두 번째(1)는 그 다음 줄을 몇 번 입력받을 지를 알려준다. 먼저 우주비행사 수가 4이므로 우주비행사가 [0,1,2,3] 이렇게(?) 있다.

첫 번째 줄을 제외한 나머지 입력받은 것은 같은 위치에 있는 숫자들을 알려준다. 따라서 0 2라고 입력받으면, 0과 2는 같은 위치에 있고 나머지 1, 3은 (0,2)와 다른 위치에 있다고 본다.

 

이를 간단하게 표현하자면 다음과 같다.

우주비행사 = [0,1,2,3]  # 총 4명
(0, 2) , (1) , (3)  # 집합이라고 설명하겠다

 

그래서 집합을 구분하고, 여기서 다른 위치에 있는 사람을 골라 총 2명을 선택할 수 있는 경우의 수를 따지면 된다.

이 예시에서는 (0, 1), (2, 1), (0, 3), (2, 3), (1, 3) 이렇게 경우의 수가 5가 나오기 때문에, 5를 출력하면 된다.

 

2. 코드

def find_set_index(a):
    for i in range(len(_list)):
        if a in _list[i]:
            return i

def journeyToMoon(n, astronaut):
    for a1, a2 in astronaut:
        i1, i2 = find_set_index(a1), find_set_index(a2)
        if i1 != i2:
            _list[i1] = _list[i1].union(_list[i2])
            del _list[i2]
            
##===============================
    _sum2 = 0
    for i in range(len(_list)-1): # timeout
        _sum1 = 0
        for j in range(i+1,len(_list)):
            _sum1 += len(_list[j])
        _sum2 += len(_list[i]) * _sum1
##===============================

    return _sum2


n, p = map(int, input().split())
astronaut = []
for _ in range(p):
    astronaut.append(list(map(int, input().split())))

_list = [{x} for x in range(n)]
print(journeyToMoon(n, astronaut))

 

3. 결과

이중 반복문을 써서 time limit에 걸린 것 같다. 다른 블로그에서 참고해서 코드를 썼는데, 주석이 달려있는 부분만 다르게 하고 싶어서 대략 생각했지만.. 아직 부족하네..쩝.. 참고로 점수는 46.43/50이다.