📌 구해야 하는 정답

우리는 모든 사람들의 덩치 등수 즉, 자신보다 덩치가 큰 사람 수 + 1의 값을 구해야 합니다.

이때 ‘A가 B보다 덩치가 크다’ 라고 판단하는 조건은 아래와 같습니다.

→ X>P Y > Q

📌 풀이 하기

1️⃣ 모든 사람의 덩치 등수 구하기

덩치 등수를 구하기 위해서는 모든 사람들과 한번씩 자신을 비교해야 합니다.

즉, N명의 사람이 있다면 N-1번의 비교가 필요하겠죠.

시간복잡도는 O(N) * O(N-1) 즉, O(N^2)가 됩니다.

여기서 N은 최대 50으로, 연산 약 2,500개로 시간복잡도 1초 안에 충분히 들어오게 됩니다.

🍯 TIP ! 이렇게 모든 경우의 수를 탐색해보는 알고리즘을 완전탐색 또는 브루트포스라고 합니다.

2️⃣ 덩치 비교 구현하기

한 사람에 대해, 0부터 N-1까지의 각각의 사람에 대해 자신과 덩치를 비교합니다.

단 이 때 자신과는 비교할 필요가 없겠죠?

0 ~ N-1 까지의 사람들과 비교할 때 자기 자신과 비교하는 경우라면 비교를 넘어가줍시다.

비교는 문제의 조건 대로 진행합니다.

→ X > P Y > Q