문제 05 : 볼링공 고르기(난이도 : 1/3)

1. 문제 설명

(1) 볼링공 고르기

• A, B 두 사람이 서로 무게가 다른 볼링공을 고르려고 한다.
• 볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀있고 공의 번호는 1번부터 순서대로 부여된다.
• 같은 무게의 공이 여러 개 있을 수 있지만, 서로 다른 공으로 간주한다.
• 볼링공의 무게는 1부터 M까지 자연수의 형태로 존재한다.
• N개의 공의 무게가 각각 주어질 때, 두 사람이 볼링공을 고르는 조합의 경우의 수를 구하는 프로그램을 작성하시오.

(2) 입력 조건

• 첫째 줄에 볼링공의 개수 N, 공의 최대 무게 M이 공백으로 구분되어 각각 자연수 형태로 주어집니다.(1 <= N <= 1,000, 1 <= M <= 10)
• 둘째 줄에 각 볼링공의 무게 K가 공백으로 구분되어 순서대로 자연수 형태로 주어집니다.(1 <= K <= M)

(3) 출력 조건

• 첫째 줄에 두 사람이 볼링공을 고르는 경우의 수를 출력합니다.

---

2. 내가 생각한 풀이

(1) 문제 분석

• i번과 j번 등 볼링공의 번호 자체가 중요한 것이 아닌, 무게가 다른 모든 조합의 경우의 수만을 알고 있으면 된다.
• 따라서, 볼링공의 무게가 서로 다른 조합을 모두 만들어 보고 그 조합의 수를 출력하면 될 것이다.

 

• 입력받은 볼링공의 무게를 오름차순으로 정렬한다.
• 이중 반복문을 이용하여 무게가 낮은 볼링공부터 뒤에 위치하는 볼링공들을 비교해, 무게가 다른 경우에만 조합을 생성한다.
• 생성한 조합을 리스트에 저장한다.
• 반복문이 끝날 경우 '리스트의 길이 == 만들 수 있는 조합의 수' 이므로 리스트의 길이를 출력한다.

(2) 코드 구현

# 볼링공의 개수와 무게 입력
n, m = map(int, input().split())

# 각 볼링공의 무게 입력
k = list(map(int, input().split()))

### 내가 생각한 풀이 방법 ###

data = [] # 볼링공을 선택한 경우의 수를 저장하는 리스트
# 볼링 공의 무게를 낮은 순 부터 오름차순 정렬
k.sort()

for i in range(n):
    for j in range(i+1, n):
        if k[i] != k[j] and (i, j) not in data:
            data.append((i, j))

print(len(data))

(3) 틀린 이유

• 문제 풀이 해설 방법과 비교하니 내 코드는 비효율적이다.
• 조합의 수 자체는 맞는거 같긴 한데, 나는 이중 반복문으로 구현해서 시간 복잡도가 O(n^2)가 되지만 해설에서 설명하는 방법은 O(n)의 시간 복잡도로 구현되어 있다.

---

3. 문제 풀이 해설

(1) 문제 분석

• 먼저, 무게마다 볼링공이 몇 개 있는지 계산해야 한다.
• 문제의 조건에서 볼링공의 무게는 1부터 최대 10까지 밖에 존재하지 않으므로 길이가 10인 리스트에 각 무게별로 볼링공이 몇 개 존재하는지 기록할 수 있다.
• 그리고 A가 먼저 볼링공을 선택할 때, B가 이어서 볼링공을 선택하는 경우를 차례로 계산하여 경우의 수를 구할 수 있다.

 

• 입력된 볼링공의 무게가 차례로 [1, 3, 2, 3, 2]일 때,
• 무게가 1인 볼링공의 수 = 1
• 무게가 2인 볼링공의 수 = 2
• 무게가 3인 볼링공의 수 = 2

 

• A가 무게가 1인 볼링공을 선택했을 때, 만들 수 있는 경우의 수
• (무게가 1인 볼링공의 수) * (B가 선택하는 무게가 2인 볼링공의 수 + B가 선택하는 무게가 3인 볼링공의 수) = 1 * (2+2) = 4

 

• A가 무게가 2인 볼링공을 선택했을 때, 만들 수 있는 경우의 수
• (무게가 2인 볼링공의 수) * (B가 선택하는 무게가 3인 볼링공의 수) = 2 * 2 = 4
• B는 여기서 무게가 1인 볼링공을 선택할 수 없다.
• 왜냐하면, 조합을 찾는 것이기 때문에 A가 1, B가 2를 선택한 경우와 A가 2, B가 1을 선택한 경우는 결국 같은 경우이다.

 

• A가 무게가 3인 볼링공을 선택했을 때, 만들 수 있는 경우의 수
• (무게가 3인 볼링공의 수) * (B는 아무 볼링공도 선택할 수 없다.) = 1 * 0 = 0
• 위의 경우와 마찬가지로 조합에서는 A가 1이나 2를 선택했을 때, B가 3을 선택한 경우와 같은 것으로 취급되기 때문에 B는 결과적으로 아무 볼링공도 선택할 수 없다.

 

• 무게가 낮은 볼링공 부터 차례로 시작하여 남은 볼링공의 갯수를 이용하면 효과적으로 문제를 해결할 수 있다.

(2) 코드 구현

# 볼링공의 개수와 무게 입력
n, m = map(int, input().split())

# 각 볼링공의 무게 입력
k = list(map(int, input().split()))

### 정답 해설 방법 ###

# 1부터 10까지의 무게를 담을 수 있는 리스트
# [0] * (m + 1)로 하는 것이 더 공간을 조금이나마 아낄 수 있을 듯 하다.
array = [0] * 11

for x in k:
    # 각 무게에 해당하는 볼링공의 개수 카운트
    array[x] += 1

result = 0
# 1부터 m까지의 각 무게에 대하여 처리
for i in range(1, m + 1):
    n -= array[i] # 무게가 i인 볼링공의 개수(A가 선택할 수 있는 개수) 제외
    # n에는 현재 A가 선택한 볼링공과 같은 무게인 볼링공의 수를 제외한 남은 다른 무게의 볼링공 갯수가 존재
    result += array[i] * n # A가 선택한 무게의 볼링공 갯수와 B가 선택할 수 있는 경의 수를 곱해서 더함

print(result)

• 먼저 리스트를 선언하고 무게가 i인 볼링공의 수를 리스트의 i번 인덱스에 저장한다.
• 따라서, 'array[i] = 무게가 i인 볼링공의 수'가 된다.

 

• 반복문을 통해 무게가 낮은 볼링공부터 경우의 수를 계산한다.
• 전체 볼링공의 수에서 무게 i의 볼링공의 수를 뺀다.
• (무게 i의 볼링공의 수) * (전체 볼링공의 수 - 무게 i의 볼링공의 수)가 'A가 무게 i의 볼링공을 선택했을 때, 만들어질 수 있는 조합의 수'이다.
• 이 계산 결과를 누적하여 마지막에 출력한다.

---

4. 후기

  코드의 효율성에 대해 처음으로 눈으로 확인할 수 있었던 문제였다. 이전 부터 누누이 말했던 것 처럼 문제를 너무 직관적으로 그리고 그대로 해석하려는 버릇이 있다. 그래서 이렇게 패턴을 찾고 코드로 구현할 수 있는 능력이 아직 부족함을 느낀다. 그래도 처음으로 문제의 해석을 봤을 때는 해석을 봐도 약간 이해가 안되는 부분이 있었는데 이제는 뇌구조가 바뀐건지 하도 많이 쳐다봐서 그런건지 확실히 이해하게 되었다. 이 문제 역시 두 번째 풀 때는 정답이었고, 두 달하고 보름정도 뒤에 세 번째 풀때는 또 오답이었는데, 세 번째 풀때 멍청하게 또 이중 반복문으로 구현하려고 했었다.... 그때는 너무 대충 대충 공부하고 넘어갔었나 싶다.

---

github : Algorithms/q5_0.py at main · LeeSeok-Jun/Algorithms (github.com)

LeeSeok-Jun/Algorithms