문제 설명
주어진 학생들의 키 정보가 있습니다. 이들 중에서 단 하나의 학생을 지정하여
해당 학생이 가장 앞에 서도록 줄을 세워야 합니다.
이 때, 한 학생의 키보다 작은 학생은 그 뒤에 서야 하며,
같은 키를 가진 학생이 여러 명이라도 순서는 변하지 않아야 합니다.
이러한 조건을 만족하도록 줄을 세우는 알고리즘을 작성하세요.
입력 형식
학생들의 키를 담고 있는 배열 (예: [160, 170, 165, 180, 175])
지정할 학생의 키 (예: 170)
출력 형식
줄 세운 학생들의 키 배열 (예: [170, 160, 165, 180, 175])
문제 해결 과정
1단계: 문제 이해하기
문제의 핵심은 주어진 배열에서 지정한 키를 가진 학생을 가장 앞에 배치하고, 나머지 학생들은 키에 따라 정렬하되
원래의 순서를 유지하는 것이다. 이 문제는 주로 안정 정렬을 활용하여 해결할 수 있다.
우리가 구현할 알고리즘은 다음과 같은 작업을 포함한다.
2단계: 간단한 예제 분석
[160, 170, 165, 180, 175]와 170이 주어진다면,줄 세운 결과는
[170, 160, 165, 180, 175]가 되어야 한다. 이때 주의할 점은같은 키를 가진 학생이 여러 명일 때, 그 순서를 유지하는 것이다.
3단계: 해결 전략 구상
해결 방법은 다음과 같다.
- 주어진 배열에서 주어진 키와 같은 학생을 찾아 그 학생을 결과 배열의 첫 번째 요소로 추가한다.
- 나머지 학생들은 같은 키를 가진 학생을 제외한 채로 원래 순서를 유지하면서 결과 배열에 추가한다.
- 최종적으로 수정된 배열을 반환한다.
4단계: 자바스크립트 코드 구현
위의 전략을 바탕으로 자바스크립트 함수를 작성해보겠다. 이 함수는 두 개의 매개변수를 받아,
지정된 키를 가진 학생을 가장 앞으로 보내는 역할을 한다.
function lineUpStudents(students, targetHeight) {
// 결과를 저장할 배열을 선언
let result = [];
// targetHeight에 해당하는 학생을 먼저 추가
const targetStudents = students.filter(height => height === targetHeight);
result.push(...targetStudents);
// 나머지 학생들을 추가 (원래 순서 유지)
const otherStudents = students.filter(height => height !== targetHeight);
result.push(...otherStudents);
return result;
}
5단계: 코드 테스트 및 검증
작성한 함수가 잘 작동하는지 확인하기 위해 몇 가지 테스트 케이스를 실행해 보겠다.
console.log(lineUpStudents([160, 170, 165, 180, 175], 170)); // [170, 160, 165, 180, 175]
console.log(lineUpStudents([160, 160, 165, 170, 180], 160)); // [160, 160, 165, 170, 180]
console.log(lineUpStudents([180, 170, 160, 150], 160)); // [160, 180, 170, 150]
6단계: 복잡도 분석
이 알고리즘의 시간 복잡도는 O(n)이다. 주어진 배열을 한 번씩 모두 돌기 때문이다.
공간 복잡도 또한 O(n)으로, 결과 배열을 따로 생성하기 때문이다.
결론
이 강좌에서는 주어진 학생들의 키 정보를 기반으로 한 줄 세우기 알고리즘을
자바스크립트를 이용해 해결하는 방법을 알아보았다.
학생의 키를 기준으로 안정적인 정렬을 유지하는 것이 이 문제의 핵심이었다.
이와 같은 문제들은 실제 코딩 테스트에 자주 출제된다는 점에서 매우 중요하다.
다양한 변형 문제를 풀어보면서 알고리즘적 사고를 키워나가는 것도 좋은 공부가 될 것이다.