알고리즘 - [백준] 1920번 수 찾기

Seong Hyeon Kim·2022년 9월 13일
0

알고리즘

목록 보기
17/20

문제


풀이과정

// 수 찾기
const fs = require("fs");
const input = fs
    .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
    .toString()
    .trim()
    .split("\n")
    .map((e) => e.replaceAll('\r', '')); /// \r 지운는법
    
    const n = input[0];     // 5
    const a = input[1].split(" ");     // 41523
    const m = input[2];     // 5
    const aEqualNumber = input[3].split(" ");  // 13795
    // console.log(aEqualNumber[1])
    

    for(let i=0; i<n; i++){
        if(a.includes(aEqualNumber[i])===true){
            console.log(1)
        }else{
            console.log(0)
        }
    }

처음에는 문제에 대한 이해를 못해서 푸는데 시간이 좀 걸렸다.

마침 같이 있던 스터디원이 문제에 관해서 설명을 해주었는데,

쉽게말하면 예제입력 1,2 번째 줄이 한묶음이고 3,4 번째 줄이 한묶음이며

4번째 줄의 숫자들중 하나가 2번째 줄에 있다면 1 없으면 0을 출력 시키는 문제였다.


문제에 대한 이해를 하고 나서 코드는 바로바로 나왔다.

그리고 vs 코드에서 실행후 출력값이 잘 나오는것도 확인하였다.

하지만 안타깝게도 백준에서는 시간초과로 통과하지 못했다.

주어진 시간이 2초인데 for 반복문에 반복문 하나랑 똑같은 includes 까지 사용해버려서

아마도 시간초가 부족하다고 나온것 같다.

그래서 다른 래퍼런스를 찾아보니 내가 사용하려는 방법을 리소스를 훨씬 줄이고

사용하는 코드가 있었다.


다른 풀이들

출처 : https://gurtn.tistory.com/93

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

const [N, A, M, B] = input.map(v => v.split(" "));

/// Set 객체에 있는 has 메서드를 사용하는 방법도 있습니다.

///has 메서드는 해당 Set 객체에 값이 존재 여부를 반환합니다.


const array = new Set(A);

const result = B.map(v => array.has(v) ? 1 : 0);

console.log(result.join("\n"));

지금처럼 map 을 사용해서 삼항연산자로 돌리면 같은 구성의 코드라도 더 시간을 아껴서

사용 할 수 있다.

map에 관한 간단한 설명



const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

const [N, A, M, B] = input.map(v => v.split(" ").map(x => Number(x)));

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

// 이분 탐색
const binarySearch = (list, target, left, right, mid) => {
  mid = Math.floor((left + right) / 2);

  if (right < left) {
    return list[mid] == target ? 1 : 0;
  }

  if (list[mid] > target) {
    right = mid - 1;
  } else {
    left = mid + 1;
  }

  return binarySearch(list, target, left, right, mid);
}

const result = B.map(v => binarySearch(A, v, 0, A.length - 1, 0));

console.log(result.join("\n"));

그리고 이러한 방법말고 다른 스터디원들도 비슷하게 풀었는데

재귀를 사용한 2진 탐색으로도 풀 수 있다는 걸 알게 되었다.


느낀점

이번 문제같은 경우 문제에 대해 이해하는게 조금 어려웠을뿐

크게 어려운 문제는 아니였다고 생각이든다

오늘처럼 내가 조금은 쉽게 풀 수 있는 문제를 접해본다면

내 스스로가 좀더 코드를 간결하게 짤 수 없을까 하는 형태로

고민을 해보는게 좋을 것 같다.


새로 알게된 점

  • 늘 사용하는 방식이 아닌 내가 배웠던 것들을 활용해서 풀 수는 없는지 고민해봐야 할 것 같다.

  • map() 메소드는 배열내의 모든 요소에 주어진 함수를 호출한 결과를 모아 새로운 배열로 반환한 것이다.

profile
삽질도 100번 하면 요령이 생긴다. 부족한 건 경험으로 채우는 백엔드 개발자

0개의 댓글