[Novice Mid : 프로그래밍 연습] 정렬 : 객체 정렬 - 원점으로부터의 거리

 

 

★ "왜?" 라는 질문을 스스로에게 하면서 학습하자.

 

 

0. 문제 풀이 순서

• 논리적 순서 확정
• 관련 카테고리 혹은 문제 끌어오기
• 필요한 자료연산 리스트업
• 이에 제일 유리한 자료구조 선택
• 구현

 

1. 설명

 

문제 링크 : https://www.codetree.ai/missions/5/problems/distance-from-origin?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 사진 :

 

문제 설명 : 원점(0, 0)으로 부터 N개의 점의 갯수만큼 가까운 점부터 순서대로 번호를 출력하는 프로그램이다. 여기서 거리란 맨하턴 거리로 정의하며, 값을 구할 때에는 절대값을 이용하는 점을 명심하자.

 

 

---

 

 

나의 소스 코드 :

 

코드 설명 : 맨해튼 거리를 구하는 것은 어찌저찌 처리하였지만, 이후 값에 따라 가까운 위치에 따라 번호 부여하여 정렬하는 방법을 어떻게 처리해야 하는지를 몰라 헤매었다. 풀이에 필요한 13분 보다 훨씬 더 많은 시간 25분을 사용했지만, 답을 몰라 풀이를 보았다.

 

😑.. 코드트리 내에서는 문제 풀이를 pair 클래스를 이용해서 풀었는데.. 난 pair 클래스를 사용하지 않고 여태껏 문제를 풀고 있어서 답 코드를 봐도 아무런 도움이 되지 않았다. 따라서 킹왕짱 챗-GPT에게 물어보니 위의 소스코드를 아래와 같이 바꿔주었다.

 

 

 바뀐 cmp를 보니 bool 값을 리턴하여서 값을 처리했고, 문제에서는 거리가 같은 경우는 없다고 했지만 거리가 같은 경우에는 작은 번호를 우선으로 하는 로직까지 처리해주었다. 이 작은 번호를 우선으로 처리하는 로직은 메인 메서드에서 idx의 값을 기존의 0이 아닌 1로 처리하고 Pos 클래스를 생성할 때 idx++을 이용해 값을 넘겨주었다. 따라서 반환할 때 작은 번호를 우선으로 반환할 수 있도록 도운 것이다. 이런 걸 보면 굉장히 똑똑하다. 어쩌면 내가 무식한 것일 수도 있고. 😥..

 

 

2. 시간

• 문제 풀이를 위해 설정한 시간 : 13분
• 실제 풀이 시 걸렸던 시간 : 30분

 

 

3. 질문

• 시간 복잡도 : 단순 for문을 사용하였고, n만큼 반복문을 수행하였기 때문에 O(n)의 시간이 걸린다.
• 공간 복잡도 : 3개의 int 변수를 사용하였으므로, 3n + 12의 값을 가진다. 따라서 메모리의 입력 값에 따라 선형적으로 증가하기 떄문에 O(n)의 시간이 걸린다.
• 어려웠던 부분 : 정렬하는 메서드 내부에서 작은 번호를 어떻게 부여하고 처리해야 하는지에 대해 어려움을 느꼈다.

 

 

4. 기타

• 최초 풀이 : 23.09.13
• 재 풀이 : ❌
• 왜? : ❌