99클럽 코테 스터디 19일차 TIL - Sort 마스터 배지훈의 후계자 (백준 20551 / JavaScript)

 

오늘의 문제 링크

 

⭐ intro : 문제를 생각해나간 방식

 

 문제와 출력값, 입력값들을 골똘히 보면서 어떻게 풀어야할지 풀어나가야할 연결고리를 찾아내어 갔다.

1. 입력값의 첫번째 값은 원소A의 갯수를 나타낸다
2. 입력값의 두번째 값은 질문(조건)M의 갯수를 나타낸다
3. 입출력값이 전부 숫자만 보이므로 number값들로 계산하고 표현해야겠군?
4. 1번의 원소A의 값들을 오름차순으로 한번 정렬할 필요가 있겠군~ 이제 슬슬 각이 보인다
5. 원소A값들을 오름차순으로 정렬해보면 이렇게 나오게 되는군
6. 질문M이랑 대조해서 해당 값이 몇번째 index에 있는지 뽑아내면 되겠군?
7. key, value값 할당이 편안한 Map()으로 만들어서 값들을 key로, 인덱스 값은 value로 지정해서 질문M 갯수만큼 순회해서 console.log로 뱉어내면 답이 나오겠다.

 

생각 의외로 깔끔하게 잘 정리된것 같아서, 이대로 코드를 짜보기로 해보았다.

 

⭐ 풀이과정

일단 input 출력값에 변화를 주었었다. 백준 input값에서 항상 \r값이 출력되길래 해당 값을 지우면서 map으로 새로운 객체를 만들며 이중배열을 만들었었는데 가독성으로도 그렇고 이중삼중으로 해결해야할 조건들이 많아져서, 그냥 \r값은 놔두고(어자피 따로 사용하게 되면 문제는 없어지므로) 양옆 공백값만 없애주는 trim()만 추가하고 이 상태의 input값에서 수정하도록 했다.

// 기존 정리 코드
let input = require("fs")
  .readFileSync("./example.txt")
  .toString()
  .split("\n")
  .map((line) => line.replace("\r", "").split(" "));
  
 // 새롭게 쓴 정리 코드
 let input = require("fs")
  .readFileSync("./example.txt")
  .toString()
  .trim()
  .split("\n");

 

다음으로 조건문을 분할했다. 첫번째 줄의 조건을 원소의 개수 N과 질문 M개의 갯수를 각각 nums, q_nums로 설정하고(대문자 하나만 보면 알아보기 어렵) 나머지 배열을 조건에 맞는 두가지의 배열 arrA, arrM로 만들었다. 조건상으로는 오름차순으로 정렬된 arrB도 만들어야 하지만 arrA를 정렬하면 그게 즉 B배열인지라 해당 배열은 패스. 첫번째 배열의 N,M 값으로 나머지 배열을 splice해서 만들었고 만들어진 값들을 solution함수의 매개변수로 넣어주었다.

const [nums, q_nums] = input[0].split(" ").map(Number);
const arrA = input.slice(1, nums + 1).map(Number);
const arrM = input.slice(nums + 1, nums + q_nums + 1).map(Number);

function solution(nums, q_nums, arrA, arrM) {}

 

다음으로 Map() 객체를 만들어주고 arrA의 값을 오름차순으로 정리해준 뒤 arrA 배열을 전체적으로 순회 하면서 차례대로 해당 value값과 index를 key, value로 넣어주되 중복값이 있을경우를 not연산자를 이용해서 중복값의 첫번째 값만 해당 값에 넣어질 수 있도록 만들었다. 이로서 고유한 값을 찾아서 어떤 값이 '맨 처음으로' 해당 배열에 나타났는지 확인할 수 있다.

function solution(nums, q_nums, arrA, arrM) {
  const map = new Map();
  arrA.sort((a, b) => a - b);

  for (let i = 0; i < arrA.length; i++) {
    if (!map.has(arrA[i])) {
      /*
      만약 [2, 2, 4, 5, 5]값이 들어올 경우...
      2는 0번째에서 처음으로 나오고 4는 2번째, 5는 3번째에서 나오도록
      Map()을 만들었다.
      */
      map.set(arrA[i], i);

	// 이렇게 되면 [2 => 0, 4 => 2, 5 => 3]값을 가지게 되는 Map() 객체가 만들어진다
    }
  }
}

 

마지막으로 제자들의 질문M값이 담겨있는 arrM값을 순회하면서, Map()객체에 해당 값이 몇번째에 존재하는지 순회하고 해당 값이 존재하지 않으면 -1를 내뱉도록 만들면 코드 완성~!

arrM.forEach((value) => {
  console.log(map.has(value) ? map.get(value) : -1);
});

 

⭐ 제출답안

let input = require("fs")
  .readFileSync("./example.txt")
  .toString()
  .trim()
  .split("\n");

const [nums, q_nums] = input[0].split(" ").map(Number);
const arrA = input.slice(1, nums + 1).map(Number);
const arrM = input.slice(nums + 1, nums + q_nums + 1).map(Number);

function solution(nums, q_nums, arrA, arrM) {
  const map = new Map();

  arrA.sort((a, b) => a - b);

  for (let i = 0; i < arrA.length; i++) {
    if (!map.has(arrA[i])) {
      map.set(arrA[i], i);
    }
  }

  arrM.forEach((value) => {
    console.log(map.has(value) ? map.get(value) : -1);
  });
}

solution(nums, q_nums, arrA, arrM);

응...? 메모리랑 시간이 왜저뤱

일단... 맞았다고 나오긴 하는데 시간제한 조건인 4초보다도 높기도 해서 조건문으로 따지면 틀리긴 했는데 맞았다고 하니 맞은걸로...

 

⭐ 공부했던 개념들

전체 탐색을 완전탐색이라고 하던가? O(n)만큼 시간이 걸려서 저렇게 높은 시간이 나왔나보다. 시간을 조금 더 줄일 수 있는 방법은 뭐가 있을지 찾아봐야 할것 같다.