인프런 커뮤니티 질문&답변
작성한 질문수
씨름 선수 문제 질문드립니다.
작성
·
159
0
잘이해가 가지 않아 질문을 살펴보던 도중 하기와 같이 답변하신 것을 보고 질문드립니다.
'''
키순으로 정렬했다면
183 65는 어느 누구에게도 키와 몸무게 모두 작지는 않습니다. 그래서 선발되는 것입니다.
181 60은 183 65와 비교해서 키, 몸무게 모두 작기 때문에 선발되지 않습니다.
179 61은 183 65와 비교해서 키, 몸무게 모두 작기 때문에 선발되지 않습니다.
...
172 67은 키는 위에 모든 사람보다 작지만 몸무게는 위에 사람 누구에게도 작지 않습니다. 그래서 선발됩니다.
170 72도 키는 위에 모든 사람보다 작지만 몸무게는 위에 사람 누구에게도 작지 않습니다. 그래서 선발됩니다.
'''
만약 면접을 170 72 인 지원자가 먼저 본다면 합격자는 2인이 되는게 맞을까요?
선생님은 키순으로 정렬하여 문제를 해결하셨으나 문제에 키순으로 면접본다는 내용은 없습니다.
면접 순서에 따라 합격자 수가 변경된다면
기존 주어진 순서대로 문제를 풀어야하는게 아닌가라는 생각이 들었습니다.
이에 대해 답변 부탁드립니다.
감사합니다
답변 1
0
안녕하세요^^
면접 순서에 의해서 어떤 사람은 합격하고 합격하지 않고 그렇지는 않습니다.
모든 사람과 비교해서 자신이 어떤 한 사람에게라도 키와 몸무게 모두 작으면 불합격하는 문제입니다.
키순으로 정렬을 했기 때문에 정렬한 순서대로 처리하는 것입니다. 키순으로 내림차순 정렬을 해놨기 때문에 그 순서대로 처리하면 나보다 앞에 있는 사람은 무조건 나보다 키가 큰 사람들입니다. 이(앞에 사람들) 사람들 모두 보다 내가 몸무게가 크면 나는 합격인 것입니다. 내 뒤에 정렬된 사람은 볼 필요가 없는게 나보다 키가 작은 사람들이므로 뒤에 있는 사람들때문에 내가 불합격이 될리는 없습니다.
그래서 이 문제의 해법이 내림차순 정렬을 하고 현재 내가 합격이냐 불합격이냐는 앞에 탐색되는 사람들만으로 내가 합격인지 불합격인지 판단하는 알고리즘입니다.