[백준15663] N과 M (9)

문제

---

https://www.acmicpc.net/problem/15663

15663번: N과 M (9)

 

생각의 흐름

---

좀 많이 헤멨던 문제이다...에러 원인을 찾지 못해서...

일단 문제를 분석해보자면 리스트의 원소들을 입력으로 받아 순열을 구하는 문제인데 까다로운 부분은 원소 중에 중복되는 것들이 있다는 점이다.

다시 말해 [1,9,3,9]과 같은 리스트인데 순열을 구할 때 두 개의 9를 서로 다른 원소로 생각해 (9,9)가 두 번 나오게 되는 경우가 발생한다. 

이를 해결해야 한다.

 

나의 경우 우선 중복제거를 위해 집합을 사용하고 print할 때마다 이 집합에 해당 순열을 넣어주었다.

그리고 if not in 문을 사용하여 이 집합에 없는 경우(즉 출력되지 않은) 라면 출력을 하도록 짰다.

 

깨달은 점

---

아래의 코드에서 result를 set으로 하였는데 이를 list로 하였을 때 시간초과가 발생했다.

이유는 파이썬 자료구조의 특징에 기반한 것인데 list와 달리 set은 다음과 같은 특징이 있다.

• 기본적으로 order의 개념이 없다. 그래서 index로 참조하는 것이 불가능하다. 출력 시에도 어떠한 원소가 먼저 나올지에 대한 보장이 없다.
• 이와 비슷한 자료구조에는 dictionary가 있는데 때문에 set의 값들은 dictionary의 key와 같다고 생각해도 무방하다. 다시 말해, set은 value 없이 key만 모아둔 dictionary인 셈이다.

list를 사용하여 if not in 문을 실행시키게 되면 어떤 값 x가 있는지를 검사하기 위해 list의 원소와 하나하나 비교하며 최악의 경우 O(n)의 cost가 걸린다. 하지만 set을 사용하면 x와 동일한 key값이 존재하는지를 바로 비교하기 때문에 시간을 좀 더 줄일 수 있다.(Hash table의 원리와 유사하다고 보면 된다.)

 

코드

---

from itertools import permutations

N,M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
result = []
result = set(result)
for case in permutations(arr, M):
    if case not in result:
        result.add(case)
        print(' '.join(map(str, case)))