브루트 포스> 7568. 덩치

 

<문제링크: www.acmicpc.net/problem/7568>

7568번: 덩치

문제설명: 각 사람의 몸무게와 키가 주어지고, 서로의 몸무게와 키를 비교하는데

자신보다 몸무게와 키가 모두 큰 사람의 수+1이 자신의 등수가 된다. 

이 때 등수의 중복은 허용된다.

 

 

[1차 시도]

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

for i in people:
    weight, height = i[0], i[1]
    cnt = 0
    for j in people:
        if i != j:
            if j[0] > weight and j[1]>height:
                cnt+=1
    ans.append(cnt+1)
print(' '.join(map(str,ans)))

 

풀이: 먼저 새로운 people 배열에 각 사람의 몸무게와 키 그리고 인덱스를 저장해주었다.

 

people 배열을 for문으로 돌면서 현재 기준이 되는 사람의 몸무게와 키를 weight, height 변수로 생성했다.

현재 사람보다 큰 사람들을 count해줄 cnt를 0으로 초기화해주고, 

 

다시 people 배열을 돌면서 현재 기준점인 나를 제외한 사람들 중 몸무게와 키를 비교해서

둘 다 나보다 크다면, cnt+1해준다.

 

모든사람과의 비교가 끝났다면, ans 배열에 나보다 큰사람들+1이 내 등수이므로 cnt+1을 추가한다.

최종적으로 출력형식에 맞게 print하면, 

 

채첨결과: 정상적으로 잘 통과한다.

 

 

[2차 시도]

N = int(input())
people = []
for i in range(N):
    weight, height = map(int,input().split())
    people.append([weight,height,i])
people.sort(reverse=True)
ans = [0]*N
ans[people[0][2]] = 1
for i in range(1,N):
    cnt = 0
    h=i-1
    while h >=0:
        if people[h][0] > people[i][0] and people[h][1] > people[i][1]:
            cnt+=1
        h-=1
    ans[people[i][2]] = cnt+1
print(' '.join(map(str,ans)))

 

풀이: 앞에서 풀었던 풀이방법은 이중 for문을 돌면서 모든 사람들과 비교를 해주어야하기 때문에, sort를 사용한 다른 풀이를 생각해봤다.

 

새로운 people 배열에 각 사람의 몸무게와 키 그리고 인덱스를 저장해주고 내림차순 정렬을 했다.

그리고 어차피 처음 몸무게가 가장 큰 사람은 1등이 되므로, 처음 사람은 ans에 1등으로 저장했다.

 

2등부터 for문을 돌면서 while문으로 인덱스를 하나씩 줄여가며 현재 나보다 큰 사람들만 비교를 했다.

나보다 큰사람들은 cnt+1씩 증가시켜주고, 처음사람과의 비교까지 끝났을 때, 현재 나의 원래 인덱스 위치를 찾아 ans배열에 cnt+1등의 등수를 저장했다.

 

최종적으로 출력형식에 맞게 print하면, 

 

채첨결과: 64ms-> 60ms로 아주 조금 시간을 단축할 수 있었다.

 

 

 

 

'쫄보의삽질' 블로그 탄생스토리가 궁금하다면:

Git push 취소 방법 (feat. '쫄보의삽질' 블로그 탄생 배경)