문제
A, B 두 사람이 볼링을 치고 있다. 두 사람은 서로 무게가 다른 볼링공을 고르려고 한다. 볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여된다. 또한 같은 무게의 공이 여러 개 있을 수 있지만, 서로 다른 공으로 간주한다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재한다.
예를 들어, N이 5이고, M이 3이며 각각의 무게가 차례대로 1,3,2,3,2일 때 두 사람이 공을 고르는 경우의 수는 8가지이다.
입력
첫 째줄 -> 볼링공의 개수 N(1 ~ 1000), 공의 최대 무게 M(1 ~ 10)
둘 째줄 -> 각 볼링공의 무게 K (1 ~ M)
출력
두 사람이 볼링공을 고르는 경우의 수
풀이
3가지 풀이를 해봤다.
1. 이중 loop
n,m=map(int,input().split()) data=list(map(int,input().split())) result=0 for i in range(n-1): for j in range(i,n): if data[i] != data[j]: result+=1 print(result)
단순히 data를 이중 loop를 돌려서 서로 무게가 다르면 result 값을 증가하는 알고리즘이다.
-> O(n2)
2. 데이터 정렬 후 loop
n,m=map(int,input().split()) data=list(map(int,input().split())) data.sort() count=1 result=0 for i in range(n-1): if data[i]!=data[i+1]: result+=count*(n-i-1) count=1 else: count+=1 print(result)
오름차순으로 정렬한 data를 탐색하면서 중복되는 무게 x의 개수(count)를 체크한다.
이 때, 다른 무게값이 탐색된다면 이전 무게 x의 개수와(count) 앞으로 남은 볼링공들의 개수를 곱한 값이 A가 무게 x를 선택했을 때 B가 다른 무게를 고를 경우의 수가 된다.
이를 바뀐 다른 무게에 대해서 반복한다.
-> O(nlogn)
3. 각 무게별 개수 측정
n, m = map(int, input().split()) data = list(map(int, input().split())) # 1부터 10까지의 무게를 담을 수 있는 리스트 array = [0] * 11 for x in data: # 각 무게에 해당하는 볼링공의 개수 카운트 array[x] += 1 result = 0 # 1부터 m까지의 각 무게에 대하여 처리 for i in range(1, m + 1): n -= array[i] # 무게가 i인 볼링공의 개수(A가 선택할 수 있는 개수) 제외 result += array[i] * n # B가 선택하는 경우의 수와 곱해주기 print(result)
각 무게별로 개수를 저장하는 리스트를 만든다.
리스트에 각 무게에 해당하는 볼링공의 개수를 저장한다.
무게 1부터 무게 m까지 loop를 돌린다.
각 무게별로 풀이 2와 같이 무게 x인 볼링공의 개수와 남은 볼링공들의 개수를 곱한 값을 차근차근 더해준다. (주석 참고)
-> O(n)
'algorithm > problems' 카테고리의 다른 글
백준 2887 - 행성 터널 (0) | 2021.03.06 |
---|---|
커리큘럼 (0) | 2021.03.06 |
편집 거리 (0) | 2021.02.05 |
못생긴 수 (0) | 2021.02.04 |
백준 18353 - 병사 배치하기 (0) | 2021.02.04 |