팀 사진을 위해 모여 앉는 최소 이동 수
자바스크립트 코딩테스트 문제로 median-greedy 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
가로로 놓인 좌석에서 흩어져 앉은 팀원들을 인접한 자리 이동만으로 한 덩어리로 모을 때 필요한 최소 이동 수를 구하는 문제입니다.
문제 설명
0과 1로 이루어진 배열 seats가 주어집니다.
0은 빈 좌석1은 팀원이 앉아 있는 좌석
한 번의 이동에서는 팀원 1명을 바로 옆 칸으로만 옮길 수 있습니다. 즉, 한 칸 이동할 때마다 비용이 1 늘어납니다.
모든 팀원이 최종적으로 연속한 구간에 모여 앉도록 만들 때, 필요한 최소 총 이동 수를 반환하는 minimumAdjacentMovesForTeamPhoto 함수를 작성하세요.
제한사항
1 <= seats.length <= 100,000seats[i]는0또는1입니다.- 배열 안의 팀원 수는 0명 이상입니다.
- 팀원이 0명 또는 1명이면 이동 수는
0입니다. - 반환값은 필요한 최소 총 이동 수입니다.
예시
- 입력:
seats = [1, 0, 0, 1, 0, 1]→ 출력:3 - 입력:
seats = [1, 0, 1, 0, 1]→ 출력:2 - 입력:
seats = [0, 0, 0, 1, 1]→ 출력:0 - 입력:
seats = [1, 0, 1, 1, 0, 1, 0, 0, 1]→ 출력:6
힌트
- 실제로 사람을 한 칸씩 옮기는 과정을 모두 시뮬레이션하면 비효율적입니다.
- 팀원이 앉아 있는 위치의 인덱스만 따로 모아 보세요.
- 최종 좌석이 연속해야 한다면, 가운데 사람을 기준으로 맞추는 전략이 최소 이동 수를 만듭니다.
해설
핵심은 빈 좌석 전체를 볼 필요 없이, 현재 팀원이 앉아 있는 위치만 보면 된다는 점입니다.
예를 들어 seats = [1, 0, 0, 1, 0, 1]이면 팀원의 현재 위치는 [0, 3, 5]입니다.
이 3명을 연속한 3칸에 앉혀야 하므로, 최종 위치는 어떤 형태로든 [x, x + 1, x + 2]가 됩니다.
이때 각 사람을 순서대로 대응시키면 이동 비용은 다음과 같습니다.
- 첫 번째 사람:
|0 - x| - 두 번째 사람:
|3 - (x + 1)| - 세 번째 사람:
|5 - (x + 2)|
이를 다시 쓰면:
|0 - x||(3 - 1) - x||(5 - 2) - x|
즉, 각 위치에서 자신의 순번을 뺀 값들의 집합을 만들고, 그 값들을 어떤 하나의 x에 맞추는 문제가 됩니다.
절댓값 합을 최소로 만드는 기준점은 중앙값(median) 이므로, 이 보정값들의 중앙값을 기준으로 잡으면 총 이동 수가 최소가 됩니다.
정리하면 풀이 순서는 이렇습니다.
seats를 순회하면서1이 있는 인덱스만positions배열에 담습니다.positions[i] - i값을 생각합니다.- 이 값들의 중앙값을 기준점으로 잡습니다.
- 각 값과 중앙값의 차이의 절댓값을 모두 더합니다.
예시 [1, 0, 1, 0, 1]의 경우:
- 위치:
[0, 2, 4] - 보정값:
[0, 1, 2] - 중앙값:
1 - 비용:
|0 - 1| + |1 - 1| + |2 - 1| = 2
따라서 정답은 2입니다.
이 방법은 배열을 한 번 훑고 팀원 위치만 처리하면 되므로 시간 복잡도는 O(n), 추가 공간 복잡도는 O(k)입니다. 여기서 k는 팀원 수입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.