처음 작성한 코드는 위와 같다.
이중 for문을 이용하여 안테나 위치에서의 거리를 계산하고 매번 비교한 후 가장 거리가 작았을 때의 안테나 위치를 출력하도록 말이다.
이 문제는 N이 최대로 20만까지 들어갈 수 있기에 내가 해결한 방식처럼 단순 노동으로는 시간 초과가 걸릴 수 밖에 없다.
혼자 머리 싸메고 고민한 지 1시간 정도가 돼서 구글링을 시작했는데 해당 문제가 중앙값을 찾는 추론 문제라는 것이다. 왜... 왜지?
생각을 해보자 안테나가 가운데쯤이 아니라 끝에 가깝게 위치한다면 양 끝에 집이 있을 경우 거리가 굉장히 커질 수 밖에 없고 중앙에 가까워야만 거리가 최소가 될 수 있다. 당연한 부분인 것이다. 이런 간단한 추론 문제도 이해를 못 했다니 바버멍청이...
위와 같이 입력 받은 집의 위치들을 정렬하고 N이 홀수일 때는 중앙값을 출력하도록 N이 짝수일 때는 2개의 중앙값 중 작은 값이 나올 수 있도록 코드를 작성하였다.
통과!
