선형탐색(Linear Search)과 Array.prototype.find()

모든 데이터를 찾아 보는 가장 단순하면서도 직관적인 방법이다.

 

//pnpm exec ts-node codeTest.ts

const dictionary = [
	{
		word: 'a',
		mean: '라틴 문자의 첫 번째 글자'
	},
	//...
];

function findMean (keyword, array) {
	for (let i = 0; i < array.length; i++) {
		if (array[i].word === keyword) {
			return array[i].mean;
		}
	}
	return undefined;
}

console.log(findMean("a", dictionary));
// 라틴 문자의 첫 번째 글자

const result = dictionary.find((el) => el.word === 'a');
console.log(result?.mean);
// 라틴 문자의 첫 번째 글자

 

하나의 반복문을 돌면서 주어진 값이 나올 때까지 검색하는 방식이다. 그러므로 선형 탐색의 시간 복잡도는 O(n)이라 할 수 있다.

 

자바스크립트에서는 선형 탐색을 사용해 배열에서 원하는 값을 반환받는 메서드가 존재한다.

 

Array.prototype.find() 이다. 이 메서드는 선형탐색을 사용하므로 동일하게 O(n)의 시간복잡도를 가진다. 따라서 일반적으로 선형탐색을 구현할 때 이 메서드를 사용한다.

 

예제1)

//pnpm exec ts-node codeTest.ts

/*
	1. 범인은 밀크티를 훔쳐 강당의 10번째 줄로 들어갔다.
	2. 범인은 파란색 신발을 신고 있었다.
	3. 범ㅣㄴ의 이름표를 정확히 보진 못했지만 마지막 이름은 '수'로 끝난다.
*/

const students = [
	//[], 1~9줄 정보 ...
	[	{name: '철수', shoes: 'red'}, 
		{name: '영희', shoes: 'blue'},
		{name: '민수', shoes: 'blue'},
		{name: '지민', shoes: 'black'},
		{name: '태현', shoes: 'blue'},
		{name: '승우', shoes: 'green'},
	],
		//[], 11번째 줄 정보 ...
];

const culprit = students
	.find((line, index) => index === 0)	// truthy 이므로 해당 원소(여기서는 배열)을 반환한다
	.find((individual) => 	// 원소 배열을 다시 순회해서 객체를 찾는다
		individual.name.endsWith('수') && individual.shoes === 'blue'
	);

	// if(index === 9) 이게 맞지만 여기서는 다른 줄을 생략했으므로 0으로 써야한다.

	// find() 메서드는 콜백 함수가 truthy로 평가되는 조건을 만났을 때해당 요소 자체를 반환한다
	// 따라서 아래 구문은 민수를 반환하는 것이 아니라 배열 자체를 반환하는 것이다.
	
	// if(index === 0) {
	// 	return line.find((student) => student.name.endsWith('수') && student.shoes === 'blue');
	// }

console.log(culprit);

// { name: '민수', shoes: 'blue' }



/*

// Truthy values 예시
true
1, -1    // 0이 아닌 모든 숫자
"hello"  // 비어있지 않은 문자열
{}       // 빈 객체
[]       // 빈 배열
function(){} // 함수

// Falsy values 예시
false
0
""       // 빈 문자열
null
undefined
NaN
*/

 

아래처럼도 풀어봤다.

const students = [
	//[], 1~9줄 정보 ...
	[	{name: '철수', shoes: 'red'}, 
		{name: '민수', shoes: 'blue'},
		{name: '지민', shoes: 'black'},
		{name: '태현', shoes: 'blue'},
		{name: '승우', shoes: 'green'},
	],
		//[], 11번째 줄 정보 ...
];

const suspectInfo = {
    students: [],
    row: 0,
    shoes: '',
    nameHint: () => {}
}


function findSuspect(suspectInfo) {
    const suspects = students[suspectInfo.row];
    for(let i = 0; i < suspects.length; i++) {
        if (suspects[i].shoes === suspectInfo.shoes && suspectInfo.nameHint(suspects[i].name)) {
            return suspects[i];
        }
    }
    return null;
}

console.log(findSuspect({
    students: students,
    row: 0,
    shoes: 'blue',
    nameHint: (name) => name.endsWith('수')
}));

// { name: '민수', shoes: 'blue' }

 

 

+ 추가 : 직접 조건을 넣을 수 있도록 함수를 만들어 보았다.

 

const students = [
	//[], 1~9줄 정보 ...
	[	{name: '철수', shoes: 'red'}, 
		{name: '민수', shoes: 'blue'},
		{name: '지민', shoes: 'black'},
		{name: '태현', shoes: 'blue'},
		{name: '승우', shoes: 'green'},
	],
		//[], 11번째 줄 정보 ...
];

const suspectInfo = {
    students: [],
    row: 0,
    shoes: '',
    nameHint: () => {}
}


function findSuspect(suspectInfo) {

    const {students, row, shoes, nameHint} = suspectInfo;
    if(students.length <= 0 || !Array.isArray(students)) {
        // throw new Error('학생이 존재하지 않습니다.');
        return '학생이 존재하지 않습니다.';
    }

    if(row < 0 || row > students.length - 1) {
        return '행이 존재하지 않습니다.';
    }
    
    const suspects = students[row];

    const suspect = suspects.find((student) => {
        // 아와 같이 하면 스트링 값이 항상 truthy 값이 되어 실제 조건과 무관하게 첫 번째 요소를 반환하게 된다.
        // return student.shoes === shoes && nameHint(student.name) || '찾을 수 없습니다.';
        
        // 따라서 아래와 같이 해주고 결과를 리턴해주는 부분에서  || 조건을 사용해 주거나
        // return student.shoes === shoes && nameHint(student.name);

        // 아래와 같이 조건을 더욱 명확하게 해주는 것이 좋다.
        const matchShoes = student.shoes === shoes;
        const matchName = nameHint(student.name);
        return matchShoes && matchName;
    });

    // 중요한 것은 or 조건을 결과를 반환하는 부분에서 사용해야 한다는 것이다.
    return suspect || '범인을 찾을 수 없습니다.';

}

console.log(findSuspect({
    // students: [], // 학생이 존재하지 않습니다.
    // students: 1, // 학생이 존재하지 않습니다.
    students: students,
    row: 0, // 사실 문제 조건대로라면 9가 되어야 한다.
    shoes: 'blue',
    nameHint: (name) => name.endsWith('수')
}));

// { name: '민수', shoes: 'blue' }
// 만족하는 값을 찾지 못한 경우, '범인을 찾을 수 없습니다.'

/*
조건식과 fallback 처리를 분리하는 것은 "관심사의 분리" 원칙과도 관련이 있다:

1. find 함수는 오직 "찾기"만 담당
2. 결과 처리(fallback 등)는 별도로 처리
3. 각 부분의 책임이 명확해짐

이런 패턴은 다른 상황에서도 적용할 수 있다.

// 데이터 검색과 에러 처리 분리의 예
    const getData = async () => {
        const data = await fetchData();  // 순수 데이터 검색
        return data || defaultValue;     // 결과 처리는 별도로
    }


명시적 조건문은 오류를 방지하고 관심사를 분리하는 것 외에도 아래와 같은 장점이 있다.

가독성
- 각 조건이 무엇을 검사하는지 명확함
- 변수 이름이 코드의 의도를 설명해줌
- 다른 개발자가 봐도 이해하기 쉬움


디버깅
- 각 조건을 개별적으로 검사하기 쉬움
- breakpoint 설정이 용이함
console.log로 각 조건의 결과를 쉽게 확인 가능


유지보수
- 조건 수정이 필요할 때 해당 부분만 찾아서 수정 가능
- 새로운 조건 추가가 쉬움
- 코드 리뷰가 수월함


실제로 약간의 메모리와 코드 길이는 이러한 이점들에 비하면 매우 작은 트레이드오프라고 볼 수 있다.
*/

 

예제2)

 

/*
    테러 집단의 비밀 코드를 해독해야 한다.
    이 코드는 숫자로 이뤄져 있고 해당 숫자들이 약속된 패턴의 배열로 전달된다면 특정한 의미를 뜻한다.

    '작전실행'을 의미하는 코드는 07285라는 숫자 배열이다.

    테러 집단의 암호 메시지에서 이 숫자가 존재하는지 확인해야 한다. 없으면 '코드없음'을 반환해야 한다.
    - 순서에 상관 없이 해당 원소들이 존재하는지만 확인하면 된다.

*/

let secretCodes = [0, 29, 5, 1, 3, 6, 92, 208, 39, 5, 6, 9, 29, 58, 22, 110, 92, 95, 91, 2 , 7, 0,7,2,8,5] 

let targetCode = [0, 7, 2, 8, 5];

const seekCode = (secretCodes, targetCode) => {

    let result = [];

    for(let i = 0; i < targetCode.length; i++) {
        let foundIndexes = [];
        for(let j = 0; j < secretCodes.length; j++) {
            if(targetCode[i] === secretCodes[j]) {
                foundIndexes.push(j);
            }
        }
        result.push(foundIndexes);
    }

    return result;
}

const checkCode = (secretCodes, targetCode) => {

    let result = [];

    targetCode.forEach((eachTargetNo, targetIndex) => {
        let foundIndexes = [];
        secretCodes.forEach((secretCode, secretIndex) => {
            if(eachTargetNo === secretCode) {
                foundIndexes.push(secretIndex);
            }
        })
        result.push(foundIndexes);
    })

    return result
}

console.log(seekCode(secretCodes, targetCode));
console.log(checkCode(secretCodes, targetCode));
// 타켓 코드의 각 원소가 나타난 인덱스를 배열로 반환. 5가 나타난 인덱스는 2,9, 25
// [ [ 0, 21 ], [ 20, 22 ], [ 19, 23 ], [ 24 ], [ 2, 9, 25 ] ]

 

for( of )와 forEach의 사용을 아래와 같은 사항을 참고해서 고려해도 된다.

// 배열 순회 방법: for...of vs forEach

// 1. 기본 문법
// for...of: 단순 순회
for(let number of targetCode) {
   console.log(number);
}

// forEach: 콜백 함수를 실행
targetCode.forEach(number => {
   console.log(number);
})

// 2. break/continue 사용 차이
// for...of: break, continue 사용 가능
for(let number of targetCode) {
   if(number === 7) break;    // 가능
   if(number === 5) continue; // 가능
   console.log(number);
}

// forEach: break, continue 사용 불가 - 에러 발생
targetCode.forEach(number => {
   if(number === 7) break;    // 에러 발생!
   if(number === 5) continue; // 에러 발생!
   console.log(number);
})

// 3. 비동기 처리의 차이
// for...of: async/await 사용 가능
async function processWithForOf() {
   for(let number of targetCode) {
       await someAsyncOperation(number); // 각 반복마다 기다림
   }
}

// forEach: 비동기 처리가 의도대로 작동하지 않음
async function processWithForEach() {
   targetCode.forEach(async number => {
       await someAsyncOperation(number); // 기다리지 않고 계속 진행
   })
}

// 4. 인덱스와 배열 접근의 차이
// for...of: 값만 접근 가능
for(let number of targetCode) {
   console.log(number); // 값만 사용 가능
}

// forEach: 값, 인덱스, 배열 모두 접근 가능
targetCode.forEach((number, index, array) => {
   console.log(number);    // 현재 값
   console.log(index);     // 현재 인덱스
   console.log(array);     // 전체 배열
})

// 5. 성능 비교
// for...of가 일반적으로 더 빠름 (콜백 함수 호출 오버헤드 없음)
// 하지만 대부분의 경우 성능 차이는 미미함

// 6. 권장 사용 상황
// for...of 사용: 
// - 단순 순회
// - break/continue 필요
// - 비동기 처리 필요
// - 성능이 중요한 경우

// forEach 사용:
// - 인덱스나 원본 배열 참조 필요
// - 콜백 함수를 통한 복잡한 처리 필요
// - 코드 가독성이 더 중요한 경우

 

 

예제3)

 

/*
    M * M 크의 지형에서 N개의 지뢰를 찾아야 한다.
    지형은 2차원 배열로 표현되며, 지뢰가 있는 칸은 1, 지뢰가 없는 칸은 0으로 표현된다.
    지뢰 탐지 로봇은 [0][0] 위치부터 시작하여 하나씩 칸을 탐색하고 탐색 결과에 따라
    다음 칸에서 지뢰가 발견될 확률을 계산해야 한다.
    만약 지뢰가 모두 찾아진 상태라면 더이상 수색을 하지 않고 'clear' 메시지를 전달한다.
    
    지뢰의 개수가 5개라고 전달 받았을 때의 코드를 작성
    */

    let mineField = [
        [0, 0, 0, 1, 0],
        [1, 0, 0, 0, 0],
        [0, 1, 0, 0, 0],
        [0, 0, 0, 0, 1],
        [0, 0, 1, 0, 0],
    ]

    const findMines = (mineField, totalMines) => {
        let foundMines = 0;
        let totalCells = mineField.length * mineField[0].length;

        for(let i =0; i <mineField.length; i++) {
            for(let j = 0; j < mineField[i].length; j++) {
                if(mineField[i][j] === 1) {
                    foundMines++;
                    // (totalCells - (i * mineField[i].length + j))는 남은 칸의 개수이다. 전체 칸에서 탐색한 칸을 뺀 값
                    console.log(`지뢰위치: [${i}][${j}], 남은 지뢰 확률: ${ ((totalMines - foundMines) /(totalCells - (i * mineField[i].length + j))).toFixed(2)}`);
                }

                if(foundMines === totalMines) {
                    console.log('clear');
                    // 리턴 문 사용으로 모든 순회를 중단하고 함수를 종료한다.
                    return;
                }
            }
        }
    }

    findMines(mineField, 5);

 

위처럼 해결할 수도 있지만  DFS를 사용해서 더욱 효율적으로 해결할 수 있다.