[DAY-4] JS 주요 문법(4)

😉 헷갈렸던 & 몰랐던 부분들만 정리하는 나만의 TIL
😯 모든 강의 내용은 적지 않아요!

오늘의 소감은?
두번째 실습 코드를 짜다가 머리가 터질뻔했다.
그리고 해석 강의를 확인하고 더 놀랐다.

어떻게 3문장만으로 solution함수를 짤 수 있을까?
JS 내장 함수를 여럿 이용하기 위해선 JS에 대한 깊은 이해가 우선 있어야 가능하다고 생각한다.
공부 열심히 해야겠다..

[1] 큐(Queue)

FIFO 구조를 가진 선형 자료구조입니다.

Linear Queue와 Circular Queue의 두 종류가 있습니다.

Queue는 배열로 표현할 수 있지만, 비효율적입니다.

따라서 연결 리스트를 사용해서 구현하는 것이 적절합니다. (shift 사용 금지)

[+] 실습 코드 1

😑 queue class를 구현해야 하는데 배열 이용해서 맘대로 풀어버렸다…
파이썬 queue 구현 방법을 JS로 그대로 옮겨놓은 듯한 코드 완성

function pop_val(queue) {
  let len = queue.length;
  let val = queue[0];
  for (let i = 0; i < len - 1; i += 1) {
    queue[i] = queue[i + 1];
  }
  queue.splice(len - 1, len);

  return val;
}

function solution(priorities, location) {
  let answer = 0;
  let queue = [];
  let count = 0;
  let val_arr = Array.from(Array(priorities.length), function (v, k) {
    return k + 1;
  });

  want_val = val_arr[location];

  for (let i = 0; i < priorities.length; i += 1) {
    queue.push([val_arr[i], priorities[i]]);
  }

  while (true) {
    let print = true;
    val = pop_val(queue);

    for (let i = 0; i < queue.length; i += 1) {
      if (val[1] < queue[i][1]) {
        queue.push(val);
        print = false;
        break;
      }
    }

    if (print == true) {
      count += 1;
      if (val[0] == want_val) {
        return count;
        break;
      }
    }
  }

  return answer;
}

[2] 해시 테이블(Hash Table)

키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조입니다.

삽입은 O(1)이며, 키를 알고 있다면 삭제, 탐색도 O(1)로 수행합니다.

따라서 키 값을 알고 있을 경우에, 빠르게 그 값을 찾아야 하는 경우 사용합니다.

해시 테이블에서 해시 함수의 결과가 동일하여 겹친다면 해시 충돌이 일어날 수 있습니다.

해시 함수
입력받은 값을 특정 밤위 내 숫자로 변경하는 함수입니다.

[2-1] 해시 충돌 해결법

• 선형 탐사법
  충돌이 발생하면 옆으로 한 칸 이동합니다. (인덱스를 한 칸 옆으로 옮깁니다.)
  최악의 경우에 탐색에 O(n)이 걸릴 수 있습니다.
• 제곱 탐사법
  충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동합니다.
• 이중 해싱
  충돌이 발생하면 다른 해시 함수를 이용합니다.
• 분리 연결법
  버킷의 값을 연결 리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가합니다.
  최악의 경우, 하나의 버킷이 무한정 늘어날 수 있습니다.

[2-2] JS 구현 방법

• 배열 구현

하지만 이 방법은 올바른 사용법이라 할 수 없습니다.

const table = [];
table["key"] = "value";
console.log(table["key"]); // value
delete table["key"];

• 객체 구현

제일 간단하고 정석적인 방법이며, 많이 사용합니다.

const table = {};
table["key"] = "value";
console.log(table["key"]); // value
delete table["key"];

• Map 구현

set 함수를 사용하여 값을 넣고, get함수를 사용하여 값을 찾을 수 있습니다.

편한 메소드를 제공하며 순회를 편하게 할 수 있다는 장점이 있습니다.

const table = new Map();
table.set("key", "value");
console.log(table.get("key")); // value
console.log(talbe.keys()); // {'key'}
console.log(table.values()); // {'value'}
table.delete("key"); // 하나의 요소만 삭제
table.clear(); // 전체 요소 삭제

• Set 구현

set은 키와 값이 동일하게 저장되는 방식입니다.

중복된 내용을 전부 제거할 때 사용할 수 있습니다.

const table = new Set();
table.add("key"); // Key와 value가 동일하게 들어갑니다.
console.log(table.has("Key")); // true
console.log(talbe.size); // 1
table.clear();
console.log(table.size); // 0

[+] 실습 코드 2

😂 어떻게 ..이런 코드가 나오죠?

우선 해당 문제의 요구사항은 4가지이다.

1. 같은 장르끼리 묶는다
2. 묶은 노래들을 재생 순으로 정렬한다
3. 장르별 노래를 2개까지만 자른다
4. 고유 번호를 출력한다.

풀다가 안풀려서 거의 울다시피 정답 코드를 봤습니다.

• 정답 코드

function solution(genres, plays) {
  // 해쉬 테이블을 사용하기 위해 Map 선언
  const genresMap = new Map();

  genres
    // --------------map
    // 값과 인덱스를 인자로 받아 자동으로 for문을 돌려 값을 빼준다.
    // 따라서 아래의 문장은 genre(값)과 index를 빼 [값, plays[인덱스]]의 형태로 반환한다.
    .map((genre, index) => [genre, plays[index]])
    // --------------forEach
    // forEach : 반환된 배열 요소 각각에 대해 주어진 함수를 실행한다.
    // `[장르 값, 인덱스에 맞는 play값], 처리할 현재 요소의 인덱스`를 인자로 넣어 함수 실행
    .forEach(([genre, play], index) => {
      // --------------const data 선언
      // 생성한 genresMap에 key값으로 genre가 있을 경우 해당 값을 data에 저장
      // 없을 경우 (||) {total : 0, songs : []} 으로 해당 genre에 대한 값 초기화
      const data = genresMap.get(genre) || { total: 0, songs: [] };
      // --------------set
      // Map에서 값을 넣을 때 사용하는 함수
      // Map의 key로 genre를 사용하며 후에 나오는 {} 안은 value
      genresMap.set(genre, {
        // value는 {total : (상수), songs : [...]}의 객체 형태
        total: data.total + play,
        // --------------songs의 내부 값
        // ...는 data(genresMap의 genre 키 값에 대한 value)를 전부 불러온다.
        // 기존에 기록되어 있는 값({total : ~, index : ~})들을 모두 불러와 뒤의 값을 덧붙힌다.
        songs: [...data.songs, { play, index }]
          // --------------sort
          // play 값을 기준으로 내립차순 정렬
          .sort((a, b) => b.play - a.play)
          // --------------slice
          // 시작 인덱스 0부터 끝 인덱스 2 전까지의 값만 포함하여 자른다. (0, 1)
          .slice(0, 2),
      });
    });

  // --------------entries()
  // ...genresMap(genresMap 안에 있는 요소들 전부)를 키와 값 쌍으로 배열로 반환해준다.
  return (
    [...genresMap.entries()]
      // --------------sort
      // total을 기준으로 내림차순 정렬
      .sort((a, b) => b[1].total - a[1].total)
      // --------------flatMap
      // flat() : 플랫 함수는 중첩된 배열 구조를 정해진 깊이만큼 평탄하게 만들 수 있다. (default : 1)
      // flatMap()은 배열을 평탄화하는 flat기능에 각 요소에 접근하여 사용자 정의 로직을 수행할 수 있게 해준다.
      .flatMap((i) => i[1].songs)
      // --------------map
      // song을 인자로 받아 자동으로 for문을 돌아 원하는 요소를 반환한다 (song.index 반환)
      .map((song) => song.index)
  );
}

console.log(
  solution(
    ["classic", "pop", "classic", "classic", "pop"],
    [500, 600, 150, 800, 2500]
  )
);

😅 Wow..

3문장으로 솔루션 함수를 작성할 수 있다니 난 아직 멀었다.
map, forEach, flat, flatMap 등의 여러 함수 동시 사용은 차차 익혀나가야겠다.

[3] 그래프

그래프는 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조입니다.

정점 집합과 간선 집합으로 표현할 수 있습니다.

[3-1] 그래프 특징

• 정점은 여러개의 간선을 가질 수 있습니다.
• 크게 방향 그래프와 무방향 그래프가 있습니다.
• 간선은 가중치를 가질 수 있습니다.
• 사이클이 발생할 수 있습니다.

사이클
사이클이란 그래프의 정점과 간선의 부분 집합에서 순환이 되는 부분을 말합니다.

[3-2] 그래프의 종류

(1) 간선의 방향성에 따른 분류

• 무방향 그래프

간선으로 이어진 정점끼리 양방향으로 이동이 가능한 그래프입니다. (방향이 없습니다.)
따라서 (A, B)와 (B, A)는 같은 간선으로 취급합니다.

• 방향 그래프

간선에 방향성이 존재하는 그래프이며 <A, B>와 <B, A>는 다른 간선으로 취급합니다.

(2) 간선의 연결에 따른 분류

• 연결 그래프

모든 정점이 서로 이동 가능한 상태인 그래프입니다.

• 비연결 그래프

특정 정점 쌍 사이에 간선이 존재하지 않는 그래프입니다.

• 완전 그래프

모든 정점끼리 연결된 상태인 그래프입니다.
따라서 한 정점의 간선 수는 ‘모든 정점의 수 -1’이 됩니다.
또한 모든 간선의 수는 ‘(모든 정점의 수 -1) * 정점의 수’가 되겠죠.

[3-3] 구현 방법

인접 행렬과 인접 리스트 두 가지 방식으로 그래프를 표현할 수 있습니다.

• 인접 행렬

정점의 크기 만큼 2차원 배열을 만들고 연결이 안된 상태로 초기화합니다. 이때 연결이 된 부분만 표시해주면 됩니다.

const graph = Array.from(Array(5), () => Array(5).fill(false));

// 간선
graph[0][1] = true; // 0-> 1
graph[1][3] = true; // 1-> 3

// 가중치가 있을 경우에는 초기값을 null로, 간선의 값을 가중치로 넣어주면 됩니다.

• 인접 리스트

const graph = Array.from(Array(5), () => []);

graph[0].push(1); // 0-> 1
graph[1].push(3); // 1-> 3

---

출처

프로그래머스