[알고리듬] #75 순위 구하기

[key word] 랭크, 동점동석차, 골프 순위, 골프 용어

파이썬 실습창을 열 수 있습니다.실습창 열기

 

 

순위 구하기

순위(rank)는 어떤 항목의 상대적인 위치를 중요도에 따라 오름차순이나 내림차순으로 정리한 것입니다.

정렬(sort)은 원래의 data 순서를 바꾸지만 순위는 원래의 data는 그대로 두고, 값의 크기에 따라 순위를 표시합니다.
다음은, 같은 점수이면 같은 석차로 표시하는 ‘동점 동석차’ 순위의 예입니다.

 55 6
 33 8
 0 10
 77 3
 44 7
 33 8
 77 3
 88 2
 77 3
 99 1

 

순위를 구하는 방법을 생각하여 봅시다.

• 각각의 데이터에 대하여 나머지 전체와 비교하여 순위를 정한다.
  기본적인 방법으로 언제나 사용할 수 있는 방법입니다.
  그러나 시간이 많이 걸릴것 같습니다.
• 전체를 정렬(sort)한 다음에 순위를 정하여 나간다.
  정렬하는데 시간이 걸리고,
  또 순위를 정하여야 하는데 같은 점수면 같은 순위를 매기는 것도 신경이 쓰입니다.
• 더 좋은 방법이 없을까요?

1. 순위 구하는 방법 1

순위를 정하는(ranking) 다음과 같은 방법은 어떠할까요?

코드를 분석하고 의견을 말하여 주세요.

분석을 간단하게 하기 위하여 5개의 데이터를 예로 들었습니다.

a=[3,5,3,0,3] 
n,m=len(a),max(a)
r=[0 for i in range(m+2)]
r[m+1]=1
for i in range(n):r[a[i]]+=1
for i in range(m,-1,-1):r[i]+=r[i+1]
for i in range(n):
    print(a[i],r[a[i]+1])
    
''' 
결과입니다.
3 2
5 1
3 2
0 5
3 2
'''

 

분석을 할 때 바뀌는 모습을 중강중간 확인하면 도움이 됩니다. 

다음과 같이 변화 내용을 출력하면서 다시 한 번 분석하세요.

복잡해 보이지만 원리가 간단합니다.

a=[3,5,3,0,3] 
n,m=len(a),max(a)
r=[0 for i in range(m+2)]
print(r)                              # 이곳 추가           
r[m+1]=1
print(r)                              # 이곳 추가    
for i in range(n):r[a[i]]+=1
print(r)                              # 이곳 추가     
for i in range(m,-1,-1):r[i]+=r[i+1]
print(r)                              # 이곳 추가    
for i in range(n):
    print(a[i],r[a[i]+1])             # 자기(i) 앞의 인덱스 사용  
    
'''
결과입니다.
[0, 0, 0, 0, 0, 0, 0]   <--- 처음 상태
[0, 0, 0, 0, 0, 0, 1]   <--- 마지막에 1 삽입(순위를 쉽게 정함)
[1, 0, 0, 3, 0, 1, 1]   <--- 각 데이터의 개수
[6, 5, 5, 5, 2, 2, 1]   <--- 자기 보다 높은 순위를 더함
3 2
5 1
3 2
0 5
3 2
'''

 

충분히 이해가 될때까지 스스로 분석하세요.

이 방법은 너무 크지 않은 정수 data에 사용 가능합니다.
큰 정수, 실수, 문자 등은 정수 형태로 바꾸어 사용할 수 있습니다.

그러나 숫자 사이의 칸격이 큰 데이터에 사용하면 메모리 사용이 효율적이지 못합니다. 

 

2. 순위 구하는 방법 2

순위를 구하는 더 좋은 방법은 없을까요?

다음 방법은 매우 효율적입니다.

방법을 분석하여 보세요.

a=[3,5,3,0,3]
n=len(a)
b=[1]*n
for i in range(n):             
    for j in range(i+1,n):        
        if a[i]<a[j]: b[i]+=1
        if a[i]>a[j]: b[j]+=1
for x,y in zip(a,b):            # zip(집)은 a와 b를 짝지어 줍니다.
    print(x,y)
#for i in range(n):     # 출력 결과는 위와 같습니다.
#    print(a[i],b[i])

'''
출력입니다.
3 2
5 1
3 2
0 5
3 2
'''

 

3. 골프 순위

골프(golf)는 각 홀(코스)에서 공을 치고, 몇 번 만에 홀(구멍)에 볼을 넣는 것이 가능한가를 다투는 경기입니다. 홀마다 표준타수(파)가 정해져 있으며 파5, 파4, 파3 등이 있습니다. 한 홀에서 표준타수 보다 1타 적은 홀인을 한 경우를 버디(-1) 반대로 1타 많게 홀인한 경우를 보기(+1)라 부릅니다. 일반적으로 18홀의 합계 표준타수는 72이기 때문에 72회이면 점수는 0, 75타면 점수는 +3(3오버), 68타면 점수는 -4(4언더)가 됩니다. 골프는 점수가 적은쪽의 순위가 높습니다.

 

다음은 골프 대회에 참가한 10명의 선수가 얻은 점수입니다.

    -3  2  3  -1  -2  -6  2  -1  1  5

같은 점수이면 같은 순위가 되도록 순위를 정하여 보세요.

golf 순위와 같이 작은 쪽의 순위를 빠르게 하려면 어떤 큰 숫자(bias)에서 data를 뺀 값으로 순위를 정하면 됩니다.

score=[-3,2,3,-1,-2,-6,2,-1,1,5]
bias=10
a=[bias-i for i in score]      # a=[13, 8, 7, 11, 12, 16, 8, 11, 9, 5]
n=len(a)
b=[1]*n
for i in range(n):
    for j in range(i+1,n):
        if a[i]<a[j]: b[i]+=1
        if a[i]>a[j]: b[j]+=1
for x,y in zip(score,b):
    print(f'{x:4} {y}')
    
'''
출력 결과입니다.
  -3 2
   2 7
   3 9
  -1 4
  -2 3
  -6 1
   2 7
  -1 4
   1 6
   5 10
   
11번 줄의 고급 포멧입니다.
    w='{0:>4} {1}'.format(x,y)
    print(w)
'''

 

[참고] golf 용어

score 이름	내용
triple bogey	par보다 3타 더친 것
double bogey	par보다 2타 더친 것
bogey	par보다 1타 더친 것
par	실력있는 골퍼가 그 홀에서 정상으로 칠 수 있는 타수 그린 위에서는 항상 2타만 인정
birdie	par보다  1타 적게 친 것(albatross, double eagle)
eagle	par보다  2타 적게 친 것
double eagle	par보다  3타 적게 친 것

 

golf 용어	내용
appearance fee	유명 선수에게 별도의 참가비를 주는 것
shared leader	공동 선두
prize money	상금
tour purse	상금 총액
cut off	두 라운드의 결과로 다음 라운드 참여를 결정하는 것(예선)
make the cut	cut off를 통과하는 것
play off	72홀 경기후 동점자가 나오면 하는 연장전
sudden death	play off 때 먼저 낮은 스코어가 나오는 홀이 있으면 우승하는 방식
putt for championship	우승을 위한 마지막 퍼트
2 putt behind	2타 차이로 지는 상태
two up	2타 차이로 앞서는 상태

 

설명없이 코드만 보고 분석할 수 있었습니까?

축하합니다.

 

수고하셨습니다.

오늘 끝.