백준 문제풀이/백준 Silver

BOJ 7568 - 덩치 [Python]

LKBaekjoon 2023. 10. 30. 14:03
반응형

7568번: 덩치 (acmicpc.net)

 

7568번: 덩치

우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩

www.acmicpc.net

문제 설명은 다음과 같다.

문제 설명
입력 / 출력

처음에는 다음과 같은 사고 방식으로 코드를 짰다.

 

1.먼저 집합 X와 집합 Y를 선언한다. 이 때 각 집합의 원소는 Tuple (몸무게, 키) 이다.

2. X는 몸무게 순으로 정렬하고, Y는 키 순으로 정렬한다. (이 때 정렬은 오름차순 정렬)

3. Loop를 돌면서, 각 집합 X, Y에서, 특정 원소의 오른쪽에 있는 원소들의 교집합의 개수를 센다.

-> 예를 들어, 예제 기준으로 살펴 보자.

 

예제 기준, 몸무게 순으로 정렬한 집합 X의 경우는 다음과 같다.

{ (46, 155), (55, 185), (58 183), (60, 175), (88, 186) }

 

예제 기준, 키 순으로 정렬한 집합 Y의 경우는 다음과 같다.

{ (46, 155), (60, 175), (58, 183), (55, 185), (88, 186) }

 

예를 들어 원소 (58, 183) 의 사람의 경우 이 사람보다 덩치가 큰 사람의 수를 구하는 방법은,

X의 오른쪽에는 (60, 175), (88, 186)이 있고, Y의 오른쪽에는 (55, 185) , (88, 186) 이 있다.

 

이 것의 교집합의 수는 (88, 186) 하나 이므로, 이 사람 위에는 한 명, 따라서 덩치 랭크가 2가 되는 것이다.

 

이런 식으로 코드를 짜려고 했으나,, 우선 매우 비효율적이라는 사실이 딱 한 눈에 보인다.

메모리 공간도 두 배로 잡아 먹는 일이고,, sort를 할 때 stable과 unstable 유무도 따져야 하는 것이 필요하다.

 

사실 시간초과가 날 것 같아서 시도해보지 않은 방법이 있었는데,,, 생각보다 단순하게 잘 돌아가서 당황했다.

그냥 일일이 비교하면 된다 ㅋㅋㅋㅋㅋ 나보다 키도 크고 몸무게도 큰지 if 한줄로 비교..

 

아래는 제출한 파이썬 코드이다.

n = int(input())
 
data = [] # 입력받은 정보를 저장할 리스트 data
ans = [] # 등수정보를 저장할 리스트 ans
for i in range(n):
    a, b = map(int, input().split())
    data.append((a, b)) # 몸무계와 키를 묶어서 append 해줌
 
for i in range(n):
    count = 0
    for j in range(n):
        if data[i][0] < data[j][0] and data[i][1] < data[j][1]: # 몸무게와 키 모두 자신보다 큰 사람의 수를 센다
            count += 1 
    ans.append(count + 1) # 덩치 등수는 자신보다 몸무계 키 모두 큰 사람의 수 + 1 이므로 count + 1을 ans에 append한다.
 
for d in ans:
    print(d,end=" ")

 

 

반응형