[알고리즘] 덩치 - 구현

문제 링크

 

덩치 : https://www.acmicpc.net/problem/7568

 

문제탐색

기본 원리 탐색

•  두 숫자가 모두 차이가 날 때 우위를 가려 등수를 매기는 문제입니다.
•  단, 조건 정렬을 해서 줄을세워 순위를 매기는것은 애매합니다.
  • 예) ['60', '80'], ['56', '88'], ['62', '86']  => 1번과 2번은 동점이고 2번과 3번은 동점이지만 1번과3번은 우위가 가려짐

•  그러므로 문제에 나와있는 "만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다" 는 조건을 바탕으로 구현을 해야합니다.

 

시간복잡도와 알고리즘

• 시간제한 : 1초
  • 약 1억번의 연산이 가능하다고 가정합니다.
• 사람수 : 최대 50 명
  • 요소 1개당 모든요소를 순환하며 등수를 매기므로, N x N  O(n²)의 시간복잡도가 발생합니다. 시간복잡도가 최대 O(n²) 일때 약 2500회의 연산을 수행하므로 시간복잡도는 문제가 없을것으로 예상됩니다.

 

=>이중 반복문을 통해 구현합니다. 모든 사람에 대해(1중) 모든 사람과 비교하여 등수를 매깁니다(2중)

 

코드설계하기

1. 입력값을 이중 리스트로 받습니다.
2. 모든사람을 순회하며 x>p and  y>p  조건에 따라 등수를 매깁니다.  (이 때 자기자신과 비교하지 않도록 주의합니다.)
3. 해당 과정으로 모든 사람의 등수를 매깁니다.
4. 리스트에 담은 등수를  출력합니다.

 

시도회차 수정사항

• 1회차 : 입력받은 값을 숫자로 변환하는 과정을 까먹어서 문제 발생
  • 입력받은값을 int로 바꿔준다음 재시도

 

정답코드

import sys
n=int(sys.stdin.readline())

people=[]
ranks=[] 

for x in range(n):
    weight,height = sys.stdin.readline().split()
    weight,height = int(weight),int(height) #입력값 숫자로 변환
    people.append([weight,height])
 

for x in range(n):
    rank=1 #x번 사람의 등수
    for y in range(n):
        if x!=y: #자기자신과 비교 방지
            if people[x][0]<people[y][0] and people[x][1]<people[y][1]: #다른사람이 x번 사람보다 키와 덩치가 크다면
                rank+=1 #x보다 덩치큰사람 추가
    ranks.append(rank)#최종 등수 기록 (k+1)

print(*ranks) #정답 출력