연속 방문지를 한 번만 남기기
자바스크립트 코딩테스트 문제로 consecutive-dedup 주제를 연습해보세요. 난이도는 easy이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
문제 설명
배송 차량이 지나간 방문지 기록 stops가 배열로 주어집니다.
같은 방문지가 연속해서 여러 번 기록되었다면 하나만 남기고, 방문지가 바뀌는 순간의 기록만 순서대로 모아 반환하는 compressRouteStops 함수를 작성하세요.
예를 들어 ["A", "A", "B", "B", "C"]는 ["A", "B", "C"]가 됩니다. 단, 같은 방문지가 나중에 다시 등장하더라도 바로 앞 방문지와 다르면 새 방문으로 남겨야 합니다.
제한사항
0 <= stops.length <= 100000stops의 각 원소는 길이 1 이상 20 이하의 문자열입니다.- 반환 배열은 연속해서 같은 값이 나오지 않도록 압축한 새 배열입니다.
- 원본
stops배열을 직접 수정하지 않아도 됩니다.
예시
- 입력:
["A", "A", "B", "B", "B", "C", "A"]-> 출력:["A", "B", "C", "A"] - 입력:
["Hub"]-> 출력:["Hub"] - 입력:
[]-> 출력:[] - 입력:
["A", "B", "A", "A", "C"]-> 출력:["A", "B", "A", "C"]
힌트
- 첫 번째 방문지는 비교 대상이 없으므로 그대로 남길 수 있습니다.
- 두 번째 방문지부터는 바로 앞 방문지와 다른지 확인해 보세요.
Set으로 전체 중복을 제거하면 나중에 다시 등장한 방문지까지 사라지므로 이 문제에는 맞지 않습니다.
해설
이 문제는 전체 배열에서 중복을 없애는 문제가 아니라, 연속해서 붙어 있는 같은 값만 압축하는 문제입니다.
따라서 방문지를 왼쪽부터 한 번만 순회하면서, 현재 방문지가 직전 방문지와 다른 경우에만 결과 배열에 넣으면 됩니다.
풀이 순서는 다음과 같습니다.
- 빈 결과 배열
answer를 준비합니다. stops를 앞에서부터 순회합니다.- 현재 인덱스가
0이면 첫 방문지이므로 결과에 추가합니다. - 그 외에는
stops[i] !== stops[i - 1]인 경우에만 결과에 추가합니다. - 순회가 끝나면
answer를 반환합니다.
예를 들어 ["A", "B", "A"]는 세 값이 모두 결과에 남습니다. 첫 번째 "A"와 세 번째 "A"는 같은 값이지만 서로 연속해 있지 않기 때문입니다.
배열을 한 번만 순회하므로 시간 복잡도는 O(n)이고, 결과 배열을 제외한 추가 공간은 O(1)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
JavaScript
에디터 로딩 중...
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
아직 실행하지 않았습니다.
실행 결과
아직 실행하지 않았습니다.
예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.