검색과 정렬
65분 안팎
학습 목표
필터·정렬·이진 탐색 경계를 작은 입력으로 검증합니다.
개념
검색 결과에는 순서 계약이 필요합니다
담당자는 제목에 Java가 포함된 도서를 찾아 ID 순서로 보고 싶어 합니다. 등록 순서가 다르다고 결과가 달라지면 화면 확인과 테스트가 불안정해집니다. 검색 조건과 결과 순서를 별도 계약으로 정합니다. 이번 입력은 첫 줄 도서 수 n, 다음 n줄 ID와 제목을 탭으로 구분한 행, 마지막 줄 검색어입니다. ID는 고유한 양수 정수이며 JavaScript가 정확히 표현하는 안전 정수 범위입니다. 제목은 비어 있지 않고 탭과 줄바꿈을 포함하지 않습니다. 잘못된 입력 검증은 이번 브라우저 문제의 범위 밖이며 입력 계약을 지킨 사례로 검색을 평가합니다.
문자열을 행과 필드로 나눕니다
표준 입력을 fs.readFileSync(0, "utf8")로 읽습니다. 줄 끝의 CRLF는 LF로 정규화하고 행 단위로 나눕니다. split(/\s+/)로 입력 전체를 나누면 제목의 공백이 사라지고 여러 단어가 다른 도서로 해석될 수 있습니다. 첫 탭 위치를 indexOf로 찾고 앞부분을 ID, 뒷부분 전체를 제목으로 사용합니다. Number로 변환한 ID만 숫자로 정렬하며 제목은 원래 문자열 그대로 유지합니다. 제목 양끝 공백도 자료의 일부이므로 입력 전체에 trim을 적용하지 않습니다.
검색어가 빈 문자열이면 전체 도서를 반환하기로 정합니다. 마지막 검색어 행이 비어 있는 입력과 파일 끝 개행을 구분하려면 n으로 검색어의 위치를 계산합니다. lines[n + 1]을 사용하면 빈 검색어도 보존됩니다. 마지막 원소를 검색어라고 가정하면 끝 개행이 빈 검색어로 오인될 수 있습니다. 도서가 0권인 경우에도 검색어는 두 번째 행에 위치합니다. 파서를 짤 때 정상 예시 하나가 아니라 0권·빈 검색어·마지막 개행 입력을 손으로 써 봅니다.
필터는 조건을 만족한 행만 남깁니다
Array.filter는 조건을 만족한 원소를 새 배열에 담습니다. book.title.includes(query)는 대소문자를 구분하는 부분 문자열 검사입니다. 이번 계약에서는 Java와 java가 다른 검색어이고 한글도 같은 방식으로 비교합니다. 자동 소문자 변환이나 공백 제거를 넣으면 사용자가 정한 계약이 달라집니다. 빈 검색어는 모든 문자열에 포함되므로 전체 조회가 됩니다. 검색 결과가 없으면 NONE 한 줄을 출력합니다. 빈 목록과 검색 실패를 같은 출력으로 표시하지만 내부에서는 입력 도서 수와 결과 수를 따로 볼 수 있습니다.
검색어가 제목의 시작에만 있는지 검사하는 startsWith와 제목 어디에나 있는지 검사하는 includes는 다릅니다. SQL 노트 Java라는 제목도 Java 검색에 나와야 합니다. 제목의 일부를 정규식으로 해석하지 않고 문자열 그대로 검사하므로 검색어 .은 임의의 한 글자가 아니라 실제 점입니다. 결과에는 ID와 제목을 탭으로 이어 출력하며 제목 공백은 유지합니다. 출력에 디버그 로그를 더하면 채점 결과와 섞이므로 관찰 로그는 제거한 뒤 제출합니다.
숫자 비교 함수를 명시합니다
Array.sort는 기본적으로 문자열 기준 정렬을 사용합니다. ID 10과 2를 문자열로 비교하면 10이 2보다 먼저 나올 수 있습니다. sort((a, b) => a.id - b.id)를 사용하면 숫자 오름차순으로 정렬합니다. 비교 함수는 앞이 작으면 음수, 같으면 0, 크면 양수를 반환합니다. true나 false만 반환하는 비교 함수는 앞이 작은 경우와 같은 경우를 적절히 표현하지 못해 잘못된 순서를 만들 수 있습니다. 이번 입력은 고유 ID라 동점 제목 정렬 규칙은 필요하지 않습니다.
sort는 호출한 배열 자체를 바꿉니다. filter의 반환 배열을 정렬하면 원본 도서 배열의 순서는 유지됩니다. 원본을 바로 정렬한 다음 다른 기능에서 등록 순서를 기대하면 서로 영향을 줍니다. 원본을 보존하는지 여부는 sort가 빠르냐보다 먼저 확인할 의미 문제입니다. 제목 검색은 도서 수만큼 제목을 검사하고 결과 k개 정렬은 별도 작업입니다. 작은 입력에서는 전처리 비용도 있으므로 이진 탐색이라는 이름만으로 전체 검색이 빨라졌다고 단정하지 않습니다.
이진 탐색은 정렬 기준이 맞을 때 적용합니다
제목 부분 문자열 검색은 ID 순서와 관계가 없습니다. ID로 정렬한 배열의 가운데 제목이 검색어와 다르다는 이유로 한쪽 절반을 버릴 수 없습니다. 이진 탐색은 정렬된 ID에서 특정 ID의 위치를 찾는 별도 작업에 사용합니다. 이번 따라하기에서는 lowerBound 함수로 원하는 ID 이상이 처음 나타나는 위치를 찾습니다. 탐색 구간은 왼쪽 포함·오른쪽 제외인 [lo, hi)로 두고 처음 lo=0, hi=배열 길이를 사용합니다. 빈 배열도 같은 규칙으로 처리합니다.
중간값 mid는 Math.floor((lo + hi) / 2)로 계산합니다. ids[mid]가 target보다 작으면 lo를 mid+1로 옮기고 그 외에는 hi를 mid로 옮깁니다. lo와 hi가 같아질 때 탐색을 마치며 반환 위치가 배열 길이일 수도 있습니다. 그 위치에 target이 실제 있는지는 idx가 길이보다 작은지와 값이 같은지를 추가 확인합니다. 삽입 위치와 존재 확인은 다른 결과입니다. 마지막 원소보다 큰 target, 첫 원소보다 작은 target, 원소 사이에 없는 target이 경계 오류를 드러냅니다.
오류를 작은 반례로 읽습니다
2와 10이 뒤집히면 숫자 비교 함수가 빠졌는지 봅니다. 제목 Java 입문이 Java만 출력되면 필드 분리가 공백을 잘랐는지 봅니다. 빈 검색어에서 오류가 나면 trim으로 마지막 행을 지웠는지, query가 undefined인지 확인합니다. Cannot read properties of undefined라는 메시지는 해당 위치에 기대한 행이나 객체가 없다는 뜻이며 includes 자체가 없는 기능이라는 의미는 아닙니다. n과 실제 행 개수의 관계를 확인하고 예외를 빈 결과로 바꾸어 감추지 않습니다.
이진 탐색이 끝나지 않으면 lo=mid처럼 경계가 그대로 남는 갱신을 찾습니다. 한 원소 구간에서 같은 mid가 반복되는지 추적합니다. 존재하지 않는 값을 마지막 원소라고 보고하면 삽입 위치를 곧 존재 위치로 오해했는지 봅니다. 이 레슨의 lowerBound는 독립 관찰 예제이며 브라우저 실습에는 제목 필터와 ID 정렬만 구현합니다. 필요한 연산을 분리하면 불필요한 탐색 알고리즘을 업무 검색에 끼워 넣는 실수를 줄일 수 있습니다.
검증과 다음 단계 연결
브라우저 실습은 7개의 입력·기대 출력으로 정상 검색, 숫자 정렬, 검색 실패, 빈 검색어, 빈 도서 목록, 대소문자, CRLF를 확인합니다. 같은 코드로 모든 테스트를 실행하고 특정 입력의 답을 하드코딩하지 않습니다. 정렬되지 않은 입력을 최소 하나 포함해야 정렬 구현을 평가할 수 있습니다. 실습 완료 후 필터 결과 배열과 원본 배열의 역할을 설명하고 다음 Java 파일 저장 레슨으로 넘어갑니다. Java에서도 목록 출력 순서는 저장된 순서와 별도로 정해야 하며 ID 조회와 제목 검색은 다른 책임입니다.
따라하기
숫자 정렬 반례 만들기
각 코드 블록은 독립 실행합니다. 브라우저에서 Node 실행을 선택하거나 본인 환경에서 파일로 저장해 node 파일명.js로 실행합니다. 기본 정렬과 숫자 정렬을 비교합니다.
const ids = [10, 2, 1];
console.log([...ids].sort().join(","));
console.log([...ids].sort((a,b) => a-b).join(","));실행 결과
1,10,2 1,2,10
제목 검색과 원본 순서 비교
검색 배열만 정렬합니다. 원본 ID 순서가 바뀌지 않는지도 출력합니다.
const books = [{id:10,title:"Java 노트"},{id:2,title:"SQL Java 책"}];
const found = books.filter(b => b.title.includes("Java")).sort((a,b) => a.id-b.id);
console.log(found.map(b => b.id).join(","));
console.log(books.map(b => b.id).join(","));실행 결과
2,10 10,2
이진 탐색의 경계 확인
아래 함수는 ID 이상이 처음 나오는 위치입니다. 빈 목록, 처음, 사이, 끝 바깥을 확인하고 존재 확인과 구별합니다.
function lowerBound(ids, target) {
let lo = 0, hi = ids.length;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (ids[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
console.log(lowerBound([], 1));
for (const target of [0, 1, 2, 3, 9]) console.log(target, lowerBound([1,3],target));실행 결과
0 0 0 1 0 2 1 3 1 9 2
표준 입력으로 전체 계약 실행
아래 프로그램을 solution.js로 저장하면 node solution.js로 실행하고 입력을 붙여 넣을 수 있습니다. macOS/Linux에서는 입력 종료에 Ctrl-D를 사용합니다. 채점 입력은 3줄 도서와 검색어 Java이며 입력 필드 구분은 탭입니다. 화면의 실습 tests 첫 입력을 그대로 사용합니다.
const fs = require('fs');
const lines = fs.readFileSync(0, 'utf8').replace(/\r\n/g, '\n').split('\n');
const n = Number(lines[0]);
const books = [];
for (let i = 1; i <= n; i++) {
const tab = lines[i].indexOf('\t');
books.push({id: Number(lines[i].slice(0, tab)), title: lines[i].slice(tab + 1)});
}
const query = lines[n + 1] ?? '';
const found = books.filter(b => b.title.includes(query)).sort((a,b) => a.id - b.id);
console.log(found.length ? found.map(b => `${b.id}\t${b.title}`).join('\n') : 'NONE');
실행 결과
2 SQL Java 노트 10 Java 입문
확인 문제
실습
첫 줄 n, 다음 n줄 ID와 제목(탭 구분), 마지막 줄 검색어를 읽습니다. 제목은 탭·줄바꿈이 없는 비어 있지 않은 문자열이며 공백을 보존합니다. ID는 고유한 양수 안전 정수입니다. 대소문자를 구분하는 부분 문자열 검색 후 ID 숫자 오름차순으로 ID와 제목을 탭으로 출력합니다. 빈 검색어는 전체 조회, 결과가 없으면 NONE 한 줄입니다. 입력 계약 위반 처리는 범위 밖입니다.
모범 답안
const fs = require('fs');
const lines = fs.readFileSync(0, 'utf8').replace(/\r\n/g, '\n').split('\n');
const n = Number(lines[0]);
const books = [];
for (let i = 1; i <= n; i++) {
const tab = lines[i].indexOf('\t');
books.push({id: Number(lines[i].slice(0, tab)), title: lines[i].slice(tab + 1)});
}
const query = lines[n + 1] ?? '';
const found = books.filter(b => b.title.includes(query)).sort((a,b) => a.id - b.id);
console.log(found.length ? found.map(b => `${b.id}\t${b.title}`).join('\n') : 'NONE');
더 읽기
면접 질문
- 리스트와 맵을 선택한 기준을 설명합니다.