[백준 / python] 7568번 덩치

오늘은 구현 유형인 백준 7568번 문제, 덩치를 풀어보겠습니다!

 

< 문제 확인 >

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

---

📌 문제 탐색하기 

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시됩니다.

두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면

A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 즉, 몸무게와 키가 모두 커야만 성립하는 것이다!

 

덩치 등수는 자신보다 큰 덩치(몸무게와 키 모두 큰 경우)의 사람 수에 1을 더한 값으로 표현되고,

위 조건으로 등수를 나열하면 같은 등수가 생길수도 있습니다!

 

문제의 정답을 맞추기 위해서는,

자기 자신을 제외한 다른 모든 사람들과 비교하여 자신의 등수를 알아내야 할 것 같습니다!

 

따라서, 브루트 포스를 이용해보겠습니다 :)

 

✔️ 가능한 시간복잡도

O(n^2) 시간복잡도를 가지며, 이 문제에서는 최대 50명의

사람들의 몸무게와 키를 입력할 수 있으므로 충분히 제한 시간 내에 해결이 가능합니다.

---

📌 코드 설계하기

- 문제 탐색하기 과정을 기반으로 이 문제를 해결하기 위한 로드맵을 그리는 과정
- 어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

 

1. 입력할 사람의 수인 N을 입력받습니다.

2. 각 사람의 몸무게, 키를 입력받고 리스트에 저장합니다.

3. 개인별로 나머지 사람들과 비교하여 자신의 덩치보다 큰 사람이 몇 명인지 계산합니다.

4. 각 과정에서 덩치가 큰 조건이 성립할 경우 등수에 1을 더합니다.

5. 모든 사람의 등수를 공백을 기준으로 한 줄에 출력합니다.

---

📌 시도 회차 수정 사항 (Optional)

무문별하게 “맞았습니다”가 나올때 까지 수정하는 형태의 문제 풀이를 반복하면,

내가 어떤 실수를 해서 해당 문제를 틀렸는지 모른다.

- 틀렸습니다를 받았다면 왜 틀렸는지, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

런타임에러 발생! 그 이유는 "변수 이름 중복"이었습니다!

덩치 등수를 저장할 리스트명과 개인의 등수를 저장하는 변수를 모두 rank로 작성했었기 때문입니다 ㅠ

리스트에 append할 때 rank 변수가 리스트가 아닌 정수로 인식되어 오류가 발생할 수 있다고 합니다!

---

📌 정답 코드

# 사람 수 입력
N = int(input())

# 사람의 몸무게와 키를 저장
people = []

for _ in range(N):
    weight, height = map(int, input().split())
    people.append((weight, height))

# 덩치 등수를 저장
ranks = []

for i in range(N):
    rank = 1 # 초기 등수는 1로 설정하고 비교 후 더하기
    for j in range(N):
        if (i != j): # 자신을 제외한 다른 사람과 비교
            if (people[i][0] < people[j][0] and people[i][1] < people[j][1]):
                rank += 1
    ranks.append(rank)

print(" ".join(map(str, ranks)))

일주일동안 매일 하루에 한 문제씩 문제를 푸니까 너무 재밌어요!

코딩테스트 준비 더 힘내서 해볼게요 ㅎㅎ

 

 

코테 챌린지 3기 파이팅 :)

@why_dev_says_no