(이것이 코딩테스트다 - 그리디) 볼링공 고르기

무지성과 지성의 대결...

 

조합을 써야 하는 문제면 그냥 아무 생각 없이 combinations을 갈겨버리는 나...

 

from itertools import combinations

n,m = map(int,input().split())
k = list(map(int,input().split()))

count = [0] * m
# print(count)
for i in k:
    idx = i-1
    # print(idx)
    count[idx] += 1
c_zero = 0
minus = 0
for i in count:
    if i == 0:
        c_zero += 1
    elif i >1:
        minus += len(list(combinations(range(i),2)))

result = len(list(combinations(range(len(k)),2))) - minus

print(result)

 

 

이 와중에 combinations 어디에 속해 있는지 몰라서 어버버했음.

1. combinations, permutations는 itertools에 속해있다.

2. 이들은 시간 복잡도가 높으므로 안 쓰는 게 좋다.

3. combinations의 길이를 알고 싶으면 list()로 감싼 후, len()으로 개수 세면 됨. 근데 벌써 시간 복잡도가 O(n^3)...

 

동빈나씨는 문제를 이렇게 풀었습니다.

 

어차피 해결책에서 A의 볼링공 번호가 무조건 B보다 작고, 적은 무게를 선택한다. -> 조합의 문제.

공의 최대 무게는 어차피 10까지밖에 없다 -> 계수정렬 사용 시 10개로 리스트 크기 제한.

만약 N이 5이고, M이 3일 때 무게가 각각 1, 3, 2, 3, 2라고 할 때

 

A가 1번 무게 선택 -> B는 4가지의 경우의 수 생각 가능.

A가 2번 무게 선택 (2가지) -> B는 3번 무게만 선택 가능 ( 2가지)

A가 3번 무게 선택 -> B는 선택의 가능성 x.

 

n,m = map(int,input().split())
k = list(map(int,input().split()))

solution = 0
count = [0] * 11

for i in k:
	count[i-1] += 1
inner_counter = 0
for i in count:
	inner_counter += i
    solution += i * (n-inner_counter)
print(solution)

 

 

단순한데 이거를 풀려고 하니까 팍 떠오르지 않네요,,,

 

너무 슬픕니다용,,,

 

이걸 이렇게 못 풀었던 이유는 일단 순열이라고 생각했었고, 이를 조합으로 바꾸는 과정에서 시간복잡도 이슈.