[python] 알고리즘 문제 해결 전략 1권 :: 소풍 (p155) 문제

6.3 문제: 소풍 (문제 ID: PICNIC, 난이도: 하)

문제

안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어야 합니다.

각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝 지을 수 있는 방법의 수를 계산하는 프로그램을 작성하세요. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 봅니다. 예를 들어 다음 두 가지 방법은 서로 다른 방법입니다.

• (태연,제시카)(써니,티파니)(효연,유리)
• (태연,제시카)(써니,유리)(효연, 티파니)

시간 및 메모리 제한

프로그램은 1초 내에 실행되어야 하고, 64MB 이하의 메모리만을 사용해야 합니다.

입력

입력의 첫 줄에는 테스트 케이스 수 C(C<=50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 학생의 수 n(2<=n<=10)과 친구 쌍의 수 m(0<=m<n*(n-1)/2)이 주어집니다. 그 다음 줄에 m개의 정수 쌍으로 서로 친구인 두 학생의 번호가 주어집니다. 번호는 모두 0부터 n-1 사이의 정수이고, 같은 쌍은 입력에 두 번 주어지지 않습니다. 학생들의 수는 짝수입니다.

출력

각 테스트 케이스마다 한 줄에 모든 학생을 친구끼리만 짝지어줄 수 있는 방법의 수를 출력합니다.

나의 답

import sys
import copy

test_case=int(input())
result = list()

def makePartner(std_in,dic_in,c):
    first_std = str(std_in[0])
    if first_std in dic_in:
        for value in dic_in[first_std]:
            std = copy.deepcopy(std_in)
            dic = copy.deepcopy(dic_in)
            if int(value) in std:
                del std[0]
                std.remove(int(value))
            else:
                continue
            if not(len(std)):
                result[c]+=1
            else:
                makePartner(std,dic,c)
    else:
        result[c]=0

for case in range(0,test_case):
    try:
        n_m = ""
        partner = ""
        n_m=input()
        partner = input()

        tmp_index= int()
        partner_dic = dict()

    except:
        print("input error")
        sys.exit()

    # make n, m
    for i in range(0,len(n_m)):
        if n_m[i]==" ":
            tmp_index = i

    n = int(n_m[:tmp_index])
    m = int(n_m[tmp_index:])

    # make student list
    student = list()
    for i in range(0,n):
        student.append(i)

    # make partner dictionary
    i=1
    while len(partner):
        if partner[i]==" ":
            key= partner[i-1]
            value = partner[i+1]
            partner= partner[i+3:]
            i=1
            if key>value:
                tmp = key
                key = value
                value = tmp
            if not(key in partner_dic):
                partner_dic[key]=list()
            partner_dic[key].append(value)
        else:
            i+=1

    check_bool = test_case>50 or n<2 or n>10 or m<0 or m>n*(n-1)/2
    if check_bool :
        print("input bool error")
        sys.exit()

    result.append(0)
    makePartner(student,partner_dic,case)

for i in result:
    print(i)

설명

std_in, 즉 student list는 현재 짝이 되지 못한 학생들을 나타내는 리스트이다.

dic_in, 즉 partner_dic dictionary는 친구 관계를 나타내는 딕셔너리이다. 다음과 같이 key 값이 value 값보다 작게 정렬하여, a=>b가 되도록 만들었다.

1. 다음과 같이 std_in에서 첫번째 요소를 받아오고 dic_in의 key값에 있는지 확인한다.

   (위에서 dic_in을 정렬하지 않았다면 3=>0은 찾을 수 없었을 수도 있음)

   첫번째 학생을 불러옴

2. 있다면

   친구가 있다면

3. dic_in에서 해당 key 값과 연결된 value 값들을 for문으로 받아온다.

   친구들을 불러온다.

4. 해당 key, value 모두가 std_in에서 존재한다면 std_in에서 삭제

   친구관계가 있고, 아직 짝이 맺어지지 않았다면 짝을 맺어주기

5. std_in의 길이가 0이면 경우의 수에 1 더하기

   짝짓기가 끝났으면 경우의 수 하나에 해당

6. std_in이 남아있으면 남아있는 std_in의 첫번째 요소를 받아와서 1부터 다시 반복

   아직 안 끝났으면 남아있는 학생의 짝을 찾아주기

시간 복잡도

최악으로 계산했을 때, N이 최댓값 10이고 M이 45라고 가정하면 학생들이 모두 짝을 이룰 수 있는 상태가 된다. 이 경우의 수를 모두 계산하기 위해 위의 코드를 돌리면, 9*7*5*3*1 = 945이 나오므로 최대 945의 복잡도가 나온다.

메모리

메모리는 약 10MB 사용하였음

Partition of a set of 140543 objects. Total size = 10,296,461 bytes.
Index Count % Size % Cumulative % Kind (class / dict of class)
0 45995 33 3303978 32 3303978 32 str
1 34802 25 1466880 14 4770858 46 tuple
2 17277 12 1025011 10 5795869 56 bytes
3 8665 6 729928 7 6525797 63 types.CodeType
4 1395 1 670536 7 7196333 70 type
5 8042 6 579024 6 7775357 76 function
6 2116 2 506052 5 8281409 80 dict (no owner)
7 1395 1 405012 4 8686421 84 dict of type
8 361 0 291624 3 8978045 87 dict of module
9 367 0 149324 1 9127369 89 set
<381 more rows. Type e.g. '_.more' to view.>

 

python 메모리 측정법 : http://egloos.zum.com/mcchae/v/11174965

주어진 답과 다른 점

1. 주어진 답은 '짝을 찾았는지', '친구인지'의 여부를 직관적으로 알기 쉽게 배열로 표현하였다. 하지만 이는 쓸모없는 값들도 많이 담고 있으므로 메모리 낭비로 볼 수도 있다. (자료구조 차이)

   본인은 '짝을 찾았는지'는 list인 student로 표현하고 '친구인지'는 dictionary인 partner_dic로 표현하였다. 이는 보기에 메모리를 절약한 것처럼 보이지만 반복문을 돌 때마다 deepcopy를 썼어야했으므로 절약했다고 볼 수도 없다.

2. 경우의 수 측정 후, 원래 배열로 돌려 놓기

   taken[firstFree] = taken[pairWith] = true;
   ret += countPairings(taken);
   taken[firstFree] = taken[pairWith] = false;

   본인은 std의 요소를 지웠다가 돌려놓는 것 대신에, copy 라이브러리를 사용하여 deepcopy로 배열들을 복사해서 사용하였다. 따라서 돌려 놓을 필요가 없었다.

3. return 값을 이용

   결국 마지막에 ret이라는 값을 return하여 문제의 답을 출력함

   본인은 외부 변수에 더하는 식으로 구현하였음

   안 좋은 방법인듯함! (고치기)

4. 중복을 제거하기 위해 남은 학생들 중 빠른 번호를 불러오는 방식을 사용

   본인은 중복을 제거하기 위해 친구 관계를 표현하는 dictionary를 key가 value보다 작도록 하여 정렬하였음