백준 2246 - 콘도 선정

문제

문제 링크

• 콘도마다 거리 D와 숙박비 C가 있다.
• 거리도 더 가깝고 숙박비도 더 싼 콘도가 있으면 그 콘도는 후보에서 탈락한다.
• 거리와 가격이 모두 다른 콘도에게 뒤지지 않아 후보가 될 수 있는 콘도의 개수를 구하는 문제

풀이

거리와 숙박비를 하나로 묶어 모든 입력을 배열에 저장한다. 배열의 요소들을 모두 하나씩 검사한다. 현재 요소와 다른 모든 요소를 비교하였을 때 거리도 더 가깝고 숙박비도 더 싼 콘도가 있으면 후보에서 탈락시킨다. 후보에 탈락하지 않은 요소의 개수를 카운팅한다.

카운팅된 후보 갯수를 최종 출력한다.

시간 복잡도

이중 반복문 사용.
둘 다 N번 반복하였으므로 시간복잡도는 O(N^2)

코드

내 제출

후기

시간복잡도를 고려하지 않고 문제를 풀이하여서 그닥 좋은 풀이는 나오지 않았다.
배열의 요소를 한번 정렬하고 배열의 크기만큼만 배교를 하면 굳이 전체 요소를 비교하지 않아도 될 것이다..
그렇게 할 경우에 시간복잡도는 대략 O(N Log N)이 나온다.