TIL 2021.06.01 [자료구조/LinkedList] [Airbnb/지도]

Kyu·2021년 6월 1일

Map airbnb data structure linkedlist 자료구조

TIL

목록 보기

142/322

Linked List

링크드 리스트는 품목들의 컬렉션을 보관하기 위한 데이터 구조이다.

How to implement

예를 들어서, 아래와 같이 int 가 담긴 연결된 박스가 있다고 가정하자.

그리고 이 박스를 자바 코드로 구현하면 아래와 같을 것이다.

class Box {
	int data; // ---- (1)
	Box next; // ---- (2)
}

(1) - 박스안에 Int가 들어가든 String이 들어가든 객체가 들어가든 그것은 상관없다. 여기선 일단 int로 함.

(2) - 박스는 다음 박스를 가리키고 있다.

6이 담긴 첫번째 박스를 head라고 이름을 지어보자.

그러면 head.data는 6이고, head.next.data는 다음 박스의 data를 가리키므로 3이 된다.

또 4가 담긴 박스를 middle이라고 하면 middle.next는 2가 담긴 박스를 가리키는 것이 된다.

생성자를 포함해서 박스 클래스를 만들어보자.

class Box {
	int data;
	Box next;
	Box(int givenData) {
		this.data = givenData;
	}
}

그런데 보통 이 Box 를 Node 라고 한다고 한다. 그리고 생성자 파라미터 컨벤션이 있어서 필드명과 같이 해줘야한다. 다시 만들어보자.

class Node {
	int data;
	Node next;
	Node(int data) {
		this.data = data;
	}
}

이제 이걸가지고 처음에 보여준 숫자가 담긴 박스들을 만들어보자

생성자를 이용해서 다음과 같이 만들면 된다.

Node nodeA = new Node(6);
Node nodeA = new Node(3);
Node nodeA = new Node(4);
Node nodeA = new Node(2);
Node nodeA = new Node(1);

하지만 이렇게하면 각각의 박스만 만들어진 상태이다.

연결 시켜주려면 각 Node의 next를 다음과 같이 지정해주면 된다.

nodeA.next = nodeB;
nodeB.next = nodeC;
nodeC.next = nodeD;
nodeD.next = nodeE;

그런데 사실 이렇게 일일이 해주는 건 분명히 한계가 있고 어딘가 어색해 보인다.

그러면 어떻게 해야할까?

이걸 담당해주는 LinkedList 라는 이름으로 클래스를 하나 만들어서 해결한다.

public class LinkedList {
    
    private Node head;
  
    public LinkedList() {
        head = null;
    }

    public void insertNode(int data) {       
        Node newNode = new Node(data);  
        preNode.next = newNode;
    }
}

현재 만든 메서드를 가지고 차례대로 노드를 생성해주면 된다.

참고
https://youtu.be/WwfhLC16bis
https://freestrokes.tistory.com/84

Airbnb 프로젝트

지도에서 List

프론트에서 지도 API를 이용해서 위치에 따라서 숙소들 리스트를 뽑아줘야한다.
처음에 위도,경도만 생각하고 요청이 오면 어떻게 처리해야할지 생각을하다가...
생각해보니 이걸 어떤 기준으로 응답해줘야할지 알수가없었다.

예를들어서 현재 사용자가 보고있는 지도의 중심좌표가 (30,30)이라면,
어떤 기준으로 숙소들을 보여줘야할까?
당근 사용자가 보이는 위치에 있는 숙소들을 다 보내주면 된다.
근데 중심좌표에서 얼마나 멀리 떨어져있는지 알수가 없다.

구글 지도 API에서는 줌인/아웃을 총 16단계로 표현한다고 한다.
각 16단계는 좌표가 얼만큼 떨어져있는지 그 거리를 가져올수있다고 한다.

그래서 이걸 기준으로 삼는다.
예를들어서, 그 기준이 10이라면, 중심좌표의 +-10 에 해당하는 것을 모두 가져오면된다.

아, 그리고 Double 끼리 사칙연산 부동연산인가 뭔가 땜에 오차가 발생해서 BigDecimal을 사용해야함

첨에 이걸 어떻게 디비에서 탐색할까 이런 깜찍한 그림도 그려가면서 생각해봤는데,

그림에 열중한 시간이 무색하게 조금 찾아보니 SQL 문법에서 바로 해결이 가능하더라. ㅋㅋㅋ(https://github.com/kyu-kim-kr/airbnb/issues/63#issuecomment-851908216)