[js] 2개의 정수 배열에서 중복된 수 찾기

사실, 이 포스트는 철저히 자기 반성입니다.

문제

무작위 정수가 들어있는 무작위 크기의 배열이 2개가 있다고 할 때,
두 배열간에 동일한 정수를 추출하는 방법을 기술 하시오.

처음 풀었던 방법

회한

설명

첫번째 방법은
첫번째 for 문의 반복수 만큼 두번째 for 문을 반복하게 되어있어서 반복 총 횟수는 62번이 되고,

두번째 방법은
첫번째 배열의 크기 + 두번째 배열의 크기인 23번입니다.
만일 배열의 크기가 매우 크다고 하면 그 차이는 기하급수적으로 늘어날 것입니다.

반성

이제와 생각해보니 많이 아쉽다는 마음과 알고리즘, 자료구조 공부를 해야할 것 같다는 생각이 들었습니다.
사실 Frontend 개발자에게 알고리즘은 크게 의미 없다고 생각했었는데 전혀 아니네요..

6 comments on “[js] 2개의 정수 배열에서 중복된 수 찾기”:

  1. 어얼 천재님!!!
    저 문제 보자마자 무슨 라이브러리의 함수 몇개 가져다 쓰면 되겠군 하고 생각을 해버렸네요 ㄷ ㄷ ㄷ
    저도 기초가 많이 부족해서 어후….

    ps. 요새 채널에 안오시남요!!! 채널이 죽어가고 있어요~~

  2. 안녕하세요?
    아이폰에서 ‘서울교통정보’ 라는 어플을 사용하던 중 실수로 삭제되어 버렸습니다. 새로 나온 어플들도 많지만 지금까지 사용해본 서울교통정보 어플중엔 최고라고 생각하고 사용해왔는데 그만… 부랴부랴 복구를 해 봤지만 역시나 현재는 지원이 안되는 어플로 나와서 인터넷을 찾다보니 귀하가 어플 개발자(?)라는 것을 알게 되었습니다. (안드로이드용도 개발했던 것으로 알고 있습니다)
    그래서 부탁드립니다. 아이폰용 서울교통정보 어플을 다시 사용할 수 있게 도움을 청합니다.
    IT쪽에 전문 지식이 없어서 메일 대신 전화번호를 남깁니다. 문자 주시면 전화 드리겠습니다.
    010-***
    안녕히 계십시오.

  3. 지나가는 사람입니다 ㅎㅎ
    사실 두번째 방법 역시 메모리를 추가로 소모하기 때문에 크게 좋은 방법이 아닙니다.
    예를 들어 배열 안의 값(인덱스)가 10억같은 값이면 메모리를 너무 많이 소모하게 되어버리죠.

    배열 두개가 무작위로 되어있기 때문에
    arr1.sort()
    arr2.sort()

    이런식으로 소팅을 해준 다음
    i=0, j=0
    while(1):
    if(arr1[i]==arr2[j]): result.append(arr1[i])
    elif(arr1[i]<arr2[j]): i++
    else: j++
    if(i==len(arr1) || j==len(arr2)): break

    이 방법을 이용하면 총 time complexity는
    nlogn+mlogm+m+n 입니다.

    만약 배열을 하나만 소팅을 하게 된다면
    길이가 짧은 배열로 소팅을 한 후, 긴 배열에 있는 값을 짧은 배열에서 이진검색을 할 수도 있는데요, 이 경우 시간복잡도는
    (M+N)logN 이 됩니다.

Leave a Reply

Your email address will not be published. Required fields are marked *