23.02.08 파이썬 코딩 퀴즈#139 전력망을 둘로 나누기(프로그래머스 스쿨)

이번 문제는 전력망을 둘로 나누기 문제이다.

하나의 트리 형태로 연결된 전력망의 임의 부분의 연결을 끊었을때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고, 그 개수 차이(절대값)을 return 해야 한다.

입출력 예 처럼 전력망은 각 배열마다 중복된 요소들이 존재하게 된다.

1번을 그림으로 나타내면 위와 같고, 여기서 3-4 또는 4-7을 끊어서 두개의 전력망으로 나누면, 각 3개 6개의 송전탑을 가지게 된다. 

3번의 경우는 위 그림과 같다.

제한사항에 의해 전달받는 wires는 항상 트리 형태의 구조를 가진다.

다양한 방법들이 있겠지만, 내가 작성한 코드는 위와 같다.

(사실 구글링을 통해 어디에든 나오는 코드를 사용하기 싫을 뿐이다.)

전달받은 배열을 정렬할 필요는 없다. (다 쓰고나니 왜 넣어 놨는지 모르겠다.)

target 은 전선을 절단할 구간을 설정하기 위해 사용하였다.

이 경우는 모든 경우의 수를 다 따져봐야 하기에, while문을 통해 target 의 값이 전부 사라질 때까지 작동하게 된다.

그리고 while 문안에 temp 배열을 하나더 만들어서 값을 비교하게 된다.

먼저 pop()을 통해 전선을 전달한 구간을 찾고, 절단된 구간의 값을 각 set1, set2 에 넣어준다.

이렇게 두개의 배열이 생성 되었다면, 다시 temp 를 돌면서 set1 과 set2에 연결된 값들을 찾아 넣어주면 된다.

굳이 또 while문으로 temp 값을 제거해가며 작성한 이유는, 연결된 값이 항상 먼저 나오는게 아니기 때문이다.

만약 set1 에 '1' 이 set2 에 '7'이 들어갔다고 가정해보자.

다음으로 확인할 값을 [3,4]를 전달 받으면, 해당값을 넣을 기준이 없기 때문에 건너뛰게 된다.

따라서 for문을 통해 temp 의 모든값을 제거해 나가며 연결된 값들을 넣어주었다.

각 그룹의 길이는 set()을 통해 중복값을 제거하고 난 뒤의 길이를 구하였다.