Keep Going

링크드리스트 (Linked List)

이후에 다루게 되는 트리, 그래프 같은 자료 구조의 밑바탕이 되는 자료구조이다. 

배열처럼 여러 개의 값을 순서대로 지정하기 위한 자료 구조이다. 

배열에서는 데이터가 정적 공간의 메모리에 순서대로 응집되어 저장된다면, 링크드 리스트는 데이터가 메모리에 흩어져서 저장된다. 

선형 데이터 구조는 삽입, 삭제 연산이 엄청나게 많을 경우, 원소들의 이동작업도 그에 따라 비례한다. 이는 성능상의 문제를 일으킬 수 있기 때문에 배열이 갖고있는 메모리 사용의 비효율성 문제를 그대로 갖고있다. 

특징

data의 입력과 삭제가 자유롭다. 새로운 데이터를 입력할 때, 세로운 데이터는 들어가고자하는  위치에 해당하는 앞 node의 tail에 자신의 data를 연결하고, 자신의 tail을 후위 node와 연결한다. 

1. 요소의 삽입 삭제시에 용이하다.

2. 특정 요소 검색에 비효율적이다.

그러나 Linked List에서는 중간에 삽입하더라도 바로 옆 공간에 넣을 필요가 없다. 아무데나 데이터를 넣은 다음 이전 요소가 새로운 요소를 가리키도록, 그리고 새로운 요소가 다음 요소를 가리키도록 링크의 연결만 조정해주면 쉽게 요소를 중간에 끼워넣을 수 있다. 그러므로 배열에서 요소를 중간에 삽입하는 것은 O(n)의 시간이 소요되고 Linked List에서는 O(1)이 소요된다.

링크드리스트 구현하려면?

자바스크립트에서 링크드리스트는 객체를 통해 구현할 수 있다. 

예시로 두 개의 객체를 next로 연결하여 링크드리스트의 기본 구조를 만들 수 있다. 

링크드리스트의 연산

링크드리스트에서 추가, 삭제, 삽입 연산을 하기 위해서는 탐색 과정이 필요하다. 출발 지점과 끝 지점이 있어야하고, head 변수를 만들고 이 변수를 기준으로 탐색을 한다. 

const linkedList =  () => {
	this.head = null; // 처음에 노드가 없으므로 null로 초기화
    this.length = 0; // 링크드리스트의 길이
}

링크드리스트에서 데이터의 삽입, 삭제는 2가지의 과정을 거친다.

1. 탐색

2. 연산

링크드리스트에 A → B → C 순서대로 데이터가 들어있고, 우리는 D라는 데이터를 B와 C 사이에 삽입하려고 한다. 

B와 D 가 필요하다. B를 가리키는 참조값(link)가 D가 들어있는 새 노드를 가리켜야하기 때문이다. 동시에 D가 다음으로 가리키는 참조값(link)를 C를 가리키게끔 해야한다. 

1) 데이터 추가

'head가 null 일 때 / head가 null이 아닐 때'를 나누어서 넣어준다. 

linkedList.add = (data) => {
	const newNode = new Node(data);
    if(this.head === null) {
    	this.head = newNode;
        this.length++;
    } else {
    	let currentNode = this.head;
        while(currentNode.link !== null) {
        	currentNode = currentNode.link;
        }
        currentNode.link = newNode;
        this.length++;
    }
}

1-1) 데이터 추가 (중간노드자리)

LinkedList.prototype.insertMiddleNode = (pre, data) => {
	const newNode = new Node(data);
    let currentNode = this.head;
    
    while(currentNode.data !== pre){
    	currentNode = currentNode.link;
    }
    
    let temp = currentNode.link;
    newNode.link = temp;
    currentNode.link = newNode;
    this.length++;
}

2-1) 데이터 제거 (마지막 노드)

LinkedList.prototype.remove = () => {
	let currentNode = this.head;
    while(currentNode.link.link !== null) {
    	currentNode = currentNode.link;
    }
    currentNode.link = null;
    thiks.length--;
}

2-2) 데이터 제거 (중간 노드)

if(currentNode.data !== data) {
	while(currentNode.link.data !== data) {
    	currentNode =  currentNode.link;
    }
    temp = currentNode.link.link;
    currentNode.link.link = null;
    currentNode.link = temp;
} else {
	temp = currentNode.link;
    currentNode.link = null;
    this.head = temp;
}
this.length--;

참고

1. https://velog.io/@raram2/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8%EC%9D%98-%EA%B0%9C%EB%85%90%EA%B3%BC-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8%EB%A5%BC-%ED%86%B5%ED%95%9C-%EA%B5%AC%ED%98%84-Linked-List

2. https://taesung1993.tistory.com/10

스택 (stack)

Last In Firtst Out 먼저 들어간 자료가 나중에 나오는 후입선출 자료구조

자바스크립트에서 stack은 배열에서 데이터를 입력하는 push() 와 데이터를 제거하는 pop() 의 사용으로 구현할 수 있다. 

스택의 시간복잡도

탐색을 할 때 n개 요소를 돌아야하기 때문에 시간복잡도는 O(n)이다. n번째 요소에 접근할 때 pop()을 n번 수행하면 n번째 요소에 접근할 수 있다. pop()의 시간복잡도는 O(1) 이므로 n번째 요소에 접근하는 시간복잡도는 O(n)이다.

예시 문제 1

괄호의 짝이 맞으면 "YES"를 리턴하고, 맞지 않으면 "NO"를 리턴해라

const solution = (str) => {
  // 배열을 for문으로 돌면서 (이면 push )이면 pop해서 하나도 안남아있으면 yes 리턴, 하나라도 남아있으면 no 리턴
  let answer = "YES";
  let newArr = [];

  for (let x of str) {
    if (x === '(') newArr.push(x);
    else {
      if (newArr.length === 0) {
        return "No";
      }
      newArr.pop(x);
    }
  }

  if (newArr.length === 0) {
    return answer;
  } else {
    return "NO";
  }
}

const str = "()()"
console.log(solution(str));

예시 문제 2

쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. 쇠막대기를 다른 쇠막대기 위헤 놓는 경우 완전히 포함되도록 놓고, 끝점은 겹치지 않는다.

레이저는 괄호의 쌍으로 표현된다 =>  '( )'

쇠막대기의 왼쪽 끝은 여는 괄호 '( ' 이고 오른쪽 끝은 닫힌 괄호 ')'로 표현된다.

쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려진다. 

쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구해라. 

입력예제

()(((()())(())()))(())

출력예제

17

const solution = (str) => {
  let answer = 0;
  let stack = [];

  // 여는 괄호를 만나면 막대기의 시작점 또는 레이저의 시작점이다. -> stack에 푸시
  // 닫는 괄호를 만나면 막대기의 닫는점인지 레이저의 닫는점인지 확인해야한다 -> 바로 앞을 살펴본다

  for (let i = 0; i < str.length; i++) {
    if (str[i] === '(') { // str[i]가 여는 괄호일 경우
      stack.push(str[i]);
    } else { // str[i]가 닫는 괄호일 경우
      stack.pop();
      if (str[i - 1] === '(') { // 레이저인 경우
        // 막대기가 몇 개가 잘리는 지 answer에 카운팅 -> stack의 length 누적
        answer += stack.length;
      } else { // 막대기의 끝인 경우
        // 닫는 괄호를 만나면 무조건 하나는 pop해야한다.
        answer++;
      }
    }
  }
  return answer;
}

const str = "()(((()())(())()))(())";
console.log(solution(str));

1. 문제

단 한명의 선수를 제외하고는 모든 선수가 마라톤을 완주했다. 

참여 선수의 이름이 담긴 배열 participant

완주한 선수의 이름이 담긴 배열 completion

참가자 중에는 동명이인이 있을 수도 있다. 

입력예제 | participant ["leo", "kiki", "eden"], completion ["eden", "kiki"]

출력예제 | "leo"

2. 해시 알고리즘 생각하지 않고 풀었던 코드

const solution = (participant, completion) => {
    participant.sort();
    completion.sort();
    for (let i = 0; i < participant.length; i++) {
        if (participant[i] !== completion[i])
            return participant[i];
    }
}

const participant = ["mislav", "stanko", "mislav", "ana"];
const completion = ["stanko", "ana", "mislav"];
console.log(solution(participant, completion));

3. 해시 알고리즘으로 푼 코드

const solution = (participant, completion) => {
    let answer = '';

    let map1 = new Map();
    let map2 = new Map();

    for (let x of participant) {
        if (map1.has(x)) { map1.set(x, map1.get(x) + 1) }
        else { map1.set(x, 1) }
    };

    for (let x of completion) {
        if (map2.has(x)) { map2.set(x, map2.get(x) + 1) }
        else { map2.set(x, 1) }
    };

    for (let [key, value] of map1) {
        if (!map2.has(key) || map2.get(key) !== value) {
            answer = key;
        }
    }
    return answer;
}

const participant = ["mislav", "stanko", "mislav", "ana"];
const completion = ["stanko", "ana", "mislav"];
console.log(solution(participant, completion));

해시 알고리즘으로 푸는 게 효율성이 더 좋다. 

해시, 투포인터, 슬라이딩 윈도우 알고리즘을 이용해서 풀어보는 문제

1. 문제

주어지는 문자열에서 아나그램이 되는 부분 문자열의 개수 구하기.

부분문자열은 연속된 문자열이다. 

입력예제 | 문자열 bacaAacba, 부분 문자열 abc

출력예제 | 3 

2. 접근방법

주어진 부분문자열과 문자열의 일부(부분문자열의 length-1)를 객체로 바꾼다.

포인터 지점을 찍어놓고 for문으로 한칸씩 이동하면서 부분문자열의 length만큼의 자리를 비교한다.

아나그램이 아닐 경우 포인터를 다음 인덱스로 이동시키고,

아나그램일 경우 answer를 카운팅하고 다음인덱스로 이동시킨다. 

3. 풀이방법

1) answer에 개수를 카운팅 해주기위해서 0으로 세팅한다. 

let answer = 0;

2) 찾아야하는 아나그램이 되는 연속된 부분문자열이기 때문에 주어진 부분문자열의 알파벳과 값을 객체형태로 가지고 있어야한다. map 객체를 사용한다. 

let map1 = new Map();
let map2 = new Map();

for (let x of t) {
	if (map2.has(x)) {
    	map2.set(x, map2.get(x) + 1);
    } else {
    	map2.set(x, 1);
    }
}

3) 부분문자열의 크기만큼 슬라이딩 윈도우 기본 세팅을 해준다. 

let len = t.length -1;

주어진 문자열 중에서 가장 앞에 2개의 문자만 객체로 세팅한다.

length를 부문분자열의 크기만큼 하지않고 -1을 해주는 이유는

부분문자열의 크기가 3일때, 2는 고정으로 계속 두고 한자리만 바꾸면서 비교를 진행해야하기 때문이다. 

for (let i = 0; i < len; i++) {
	if (map1.has(s[i])) {
    	map1.set(s[i], map1.get(s[i] + 1);
    } else {
    	map1.set(s[i], 1);
    }
}

4) for문으로 슬라이딩 윈도우로 한칸씩 이동하면서

1개 추가해서 3개씩 비교하고(부분문자열의 length) 아나그램이 아닐 경우 빼주고 반복한다. 

비교 이후에 빼주는 작업을 하기위해서 투 포인터 변수 작성해준다.

let lt = 0;
rt는 for 반복문 안에 선언

for (let rt = len; rt < s.length; rt++) {
    if (map1.has(s[rt])) {
      map1.set(s[rt], map1.get(s[rt]) + 1);
    } else {
      map1.set(s[rt], 1);
    }

	// 비교
    if (compareMaps(map1, map2)) {
      answer++;
    }
    
    // 비교 이후에 왼쪽 포인터 빼주는 작업 
    map1.set(s[lt], map1.get(s[lt]) - 1); // 기존 값보다 1작게 가져와서 다시 세팅
    if (map1.get(s[lt]) === 0) {
      map1.delete(s[lt]);
    }
    lt++;
}

5) 비교하는 함수 작성

부분문자열의 개수가 같은지 확인

key값이 같은지, value 값이 같은지 확인

const compareMaps = (map1, map2) => {
	if (map1.size !== map2.size) {
    	return false;
    }
    for (let [key, value] of map1) {
    	if (!map2.has(key) || map2.get(key) !== value) {
        	return false;
        }
    }
    retrun true; // 모두 아니면 같은 것으므로 true 반환
}

4. 코드

const solution = (s, t) => {
  // 아나그램이 되는 연속된 부분문자열 개수
  let answer = 0;

  let map1 = new Map(); // 문자열을 map 객체로
  let map2 = new Map(); // 부분문자열을 map 객체로

  // 찾아야하는 연속된 부분문자열을 map객체로 만듬
  for (let x of t) {
    if (map2.has(x)) {
      map2.set(x, map2.get(x) + 1);
    } else {
      map2.set(x, 1);
    }
  }

  // 슬라이딩 윈도우 할 때 길이가 3이면 2개를 먼저 세팅해 놓는 것
  let len = t.length - 1;

  for (let i = 0; i < len; i++) {
    if (map1.has(s[i])) {
      map1.set(s[i], map1.get(s[i]) + 1);
    } else {
      map1.set(s[i], 1);
    }
  }

  let lt = 0;

  // 슬라이딩 윈도우이기 때문에 rt는 len길이를 시작점으로 세팅
  // 추가해서 3개로 맞춰주고
  for (let rt = len; rt < s.length; rt++) {
    if (map1.has(s[rt])) {
      map1.set(s[rt], map1.get(s[rt]) + 1);
    } else {
      map1.set(s[rt], 1);
    }

    // 3개이니까 이제 비교가능
    if (compareMaps(map1, map2)) {
      answer++;
    }

    // 비교 이후에 왼쪽 포인터 빼주는 작업 
    map1.set(s[lt], map1.get(s[lt]) - 1); // 기존 값보다 1작게 가져와서 다시 세팅
    if (map1.get(s[lt]) === 0) {
      map1.delete(s[lt]);
    }
    lt++;
  }
  return answer;
}

const compareMaps = (map1, map2) => {
  if (map1.size !== map2.size) { // 1. 개수가 같은지 확인
    return false;
  }
  for (let [key, value] of map1) { // 2. key 값이 같은지 확인
    if (!map2.has(key) || map2.get(key) !== value) { // 3. value 값이 같은지 확인
      return false;
    }
  }
  return true;
}

const str1 = "bacaAacba";
const str2 = "abc";
console.log(solution(str1, str2));

해시(Hash)

임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것

특정한 배열의 인덱스나 위치를 입력하고자하는 데이터의 값을 이요해 저장하거나 찾을 수 있다. 

해쉬를 이용하면 즉시 저장하거나 찾고자하는 위치를 참조할 수 있으므로 빠른 속도로 처리할 수 있다. 

저장된 데이터에 바로 접근해서 값을 가져올 수 있다. 찾고자하는 값과 테이블의 인덱스가 동일하므로 값이 저장된 공간에 바로 접근해서 값을 가져올 수 있으므로 시간복잡도는 O(1)이다. 

테이블에 있는 값을 삽입, 수정, 삭제 하는 행위도 값이 어디있는지만 알고있으면 모두 한 방에 해결할 수 있다. 

해시테이블

해시함수라는 것에 한 번 통과시켜서 사용한다. 

해시 함수는 임의의 길이를 가지는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 

어떤 값이 들어오든 간에 다 뭉개서 내가 원하는 길이의 값으로 만든다. 

key와 value로 이루어진 Map이라는 객체를 사용해서 해시테이블을 만들어서 사용한다. 

자바스크립트의 Map은 시간복잡도를 줄이는데 결정적인 역할을 한다.

Map 객체 사용하기

Map 객체 생성

const map = new Map();

 Map의 메소드인 set함수 사용해서 객체에 요소 추가

map.set('B', 1)

기존 값에다가 증가시키기

map.get('B', 1)

예제문제 | 학급회장

문제

학급회장을 뽑는데 후보로 기호 A,B,C,D,E 후보가 등록을 했다. 투표 용지에는 반 학생들이 쓴 후보의 기호가 쓰여있으며, 선생님은 그 기호를 발표하고 있다. 발표가 끝난 후 어떤 기호의 후보가 학급 회장이 되었는지 출력해라. 

입력예제 | BACBACCACCBDEDE

출력예제 | C

코드

const solution = (str) => {
  let answer;
  let student = new Map();

  for (let x of str) {
    if (student.has(x)) {
      student.set(x, student.get(x) + 1);
    } else {
      student.set(x, 1);
    }
  }

  // 가장 작은 정수를 비교군으로 설정
  let max = Number.MIN_SAFE_INTEGER;

  for (let [key, value] of student) {
    if (value > max) {
      max = value;
      answer = key;
    }
  }
  return answer;
}

const str = "BACBACCACCBDEDE";
console.log(solution(str));

예제문제 | 아나그램

문제

아나그램이란 두 문자열이 알파벳의 나열 순서는 다르지만 그 구성이 일치하면 두 단어는 아나그램이라고 한다. 주어지는 두 단어가 아나그램이면 YES를 출력하고, 아니면 NO를 출력해라.

입력예제 | AbaAeCe, baeeACA

출력예제 | YES

코드

const solution = (word1, word2) => {
  // 아나그램 : 알파벳 나열 순서는 다르지만 그 구성(알파벳과 그 개수)이 일치
  // 길이가 다른 두 개의 단어가 주어지면, 그 두 단어가 아나그램인지 판별
  // 대소문자 구별

  let answer = "Yes";

  // map1 을 기준 객체로 만들어 놓고 
  // map1 과 word2를 비교해서 key가 존재하는지 보고, 있으면 value 비교
  let map1 = new Map();

  for (let x of word1) {
    if (map1.has(x)) {
      map1.set(x, map1.get(x) + 1);
    } else {
      map1.set(x, 1);
    }
  }

  for (let x of word2) {
    if (!map1.has(x) || map1.get(x) === 0) {
      return "No";
    }
    map1.set(x, map1.get(x) - 1);
  }

  return answer;
}

const word1 = "abaCC";
const word2 = "Caaab";
console.log(solution(word1, word2));

문제

5명의 학생이 주어질 때 각 학생이 받은 점수의 평균을 구하여 기준에 따라 학점을 부여

조건 : 자기자신을 평가한 점수가 유일한 최고점 또는 유일한 최저점이라면, 그 점수는 제외하고 평균을 구한다. 

풀이

평균을 먼저 구하고, 학점을 구한다. 각 행에 평균을 구해야 할 점수가 들어있다. 

통과하지못한 코드

const solution = (scores) => {
  let sum = 0;

  let sumArr = [];
  let scoreArr = [];
  let studentScoreArr = [];
  let len;

  let answer = '';

  // 배열 가공
  for (let i = 0; i < scores.length; i++) {
    studentScoreArr = [];
    for (let j = 0; j < scores.length; j++) {
      studentScoreArr.push(scores[j][i]);
    }
    scoreArr.push(studentScoreArr);
  }

  // 점수 가공
  for (let i = 0; i < scores.length; i++) {
    sum = 0;
    len = scoreArr[i].length;
    for (let j = 0; j < scores.length; j++) {
      let findIdx = scoreArr.indexOf(scoreArr[i]);
      let findCurrentIdx = scoreArr[i].indexOf(scoreArr[i][j]);

      if (findIdx === findCurrentIdx) {

        const myScore = scoreArr[i][j];
        const dubCheck = isDuplicate(scoreArr[i]);

        if (dubCheck) {
          if (Math.max(...scoreArr[i]) === myScore || Math.min(...scoreArr[i]) === myScore) {
            let myIdx = scoreArr[i].indexOf(myScore);
            console.log(myIdx);
            scoreArr[i].splice(myIdx, 1, 0);
            len--;
          } else {
            sum += scoreArr[i][j];
          }
        } else if (Math.max(...scoreArr[i]) === myScore || Math.min(...scoreArr[i]) === myScore) {
          let myIdx = scoreArr[i].indexOf(myScore);
          scoreArr[i].splice(myIdx, 1, 0);
          len--;
        } else {
          sum += scoreArr[i][j]
        }
      } else {
        sum += scoreArr[i][j];
      }
    }
    console.log(len);
    sumArr.push(sum / len);
  }

  // 학점 계산
  for (let i = 0; i < sumArr.length; i++) {
    if (sumArr[i] >= 90) {
      answer += 'A';
    } else if (90 > sumArr[i] && sumArr[i] >= 80) {
      answer += 'B';
    } else if (80 > sumArr[i] && sumArr[i] >= 70) {
      answer += 'C';
    } else if (70 > sumArr[i] && sumArr[i] >= 50) {
      answer += 'D';
    } else {
      answer += 'F';
    }
  }
  return answer;
}

const isDuplicate = (arr) => {
  const isDup = arr.some(function (x) {
    return arr.indexOf(x) !== arr.lastIndexOf(x);
  });
  return isDup;
}

기본 테스트는 통과했는데 테스트 케이스 3개를 통과하지 못했다. 

통과한 코드

const solution = (scores) => {
  let answer = '';

  for (let i = 0; i < scores.length; i++) {
    let myScore = scores[i][i];
    let count = scores.length;

    let min = 101;
    let max = -1;
    let sum = 0;

    let flag = true;

    for (let j = 0; j < scores.length; j++) {
      let score = scores[j][i];

      if (i !== j && myScore === score) { // 내점수가 아니고 동일한 점수가 아닐 때 
        flag = false;
      }

      min = Math.min(min, score);
      max = Math.max(max, score);
      sum += score;
    }

    if (flag && (min === myScore || max === myScore)) { // 내 점수일 때
      count--;
      sum -= myScore;
    }

    answer += findGrade(sum / count);
  }
  return answer;
}

const findGrade = (score) => {
  if (score >= 90) {
    return 'A';
  } else if (90 > score && score >= 80) {
    return 'B';
  } else if (80 > score && score >= 70) {
    return 'C';
  } else if (70 > score && score >= 50) {
    return 'D';
  } else {
    return 'F';
  }
}

문제

숫자의 일부 자릿수가 영단어로 바뀌어졌거나, 혹은 바뀌지 않고 그대로인 문자열 s가 매개변수로 주어진다. s가 의미하는 원래 숫자를 return 하도록 solution 함수를 완성하라.

입력예제 | "one4seveneight"

출력예제 | 1478

처음 코드(실패)

const solution = (s) => {
  const numStr = ['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine'];
  const num = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'];

  let answer = s;

  for (let i = 0; i < numStr.length; i++) {
    let arr = answer.split(numStr[i]);

    if (arr.length > 1) {
      let idx = numStr.indexOf(numStr[i]);
      arr.splice(1, 0, num[idx]);
      answer = arr.join(i);
    }
  }
  let answer2 = answer.split('');

  let result = answer2.reduce((acc, cur, idx, arr) => {
    if (arr.indexOf(cur) === idx) acc.push(cur);
    return acc;
  }, []);

  return Number(result.join(''));
}

처음에는 이렇게 풀었는데, 테스트케이스만 보고 중복제거를 하면된다고 생각했는데, 하고보니 주어지는 문자열에 중복이 있을 수도 있는데 그것마저 없애는 코드가 되었다. 다시 새로 짜야했다. 

다른풀이

const solution = (s) => {
  let answer = 0;

  s = s.replace(/one/g, '1');
  s = s.replace(/two/g, '2');
  s = s.replace(/three/g, '3');
  s = s.replace(/four/g, '4');
  s = s.replace(/five/g, '5');
  s = s.replace(/six/g, '6');
  s = s.replace(/seven/g, '7');
  s = s.replace(/eight/g, '8');
  s = s.replace(/nine/g, '9');
  s = s.replace(/zero/g, '0');

  console.log(s);
  return Number(s);
}

다른풀이

const solution = (s) => {
  let numbers = ["zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"];

  for (let i = 0; i < numbers.length; i++) {
    let arr = s.split(numbers[i]);
    s = arr.join(i);
  }

  return Number(s);
}

문제

같은 종류의 폰켓몬은 같은 번호를 가지고있다. 

최대한 다양한 종류의 폰켓몬을 가지길 원한다. 

최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려고 한다. 

N마리의 폰켓몬 종류 번호가 담긴 배열 nums가 주어질 때,

N/2마리의 폰켓몬을 선택하는 방법 중

가장 많은 종류의 포켓몬을 선택하는 방법을 찾아

폰켓몬 종류 번호의 개수를 return

자연수

양의 정수, 사물의 개수를 셀 때 쓰이는 수여서 가장 '자연스러운 수' 

코드

const solution = (nums) => {
  const selectNum = nums.length / 2;

  const possibleSelect = nums.reduce((acc, cur, idx, origin) => {
    if (origin.indexOf(cur) === idx) acc.push(cur);
    return acc;
  }, []);

  return possibleSelect.length >= selectNum ? selectNum : possibleSelect.length;
}

중복 제거를 먼저해주고, 개수를 찾아주면 되는 문제였다. 

reduce를 이용해서 중복제거를 해주었는데, 중복된 값을 허용하지 않는 Set 객체를 이용하면 더 간단하게 코드를 작성할 수 있었다. 

다른사람의 풀이

function solution(nums) {
  const max = nums.length / 2;
  const arr = [...new Set(nums)];

  return arr.length > max ? max : arr.length
}