인터뷰 문제로 물어볼법한 내용은 아니다. 하지만 매우 초보적인 실수를 막기 위해 언급한다.
대부분의 코딩 인터뷰는 열거형 데이터를 다루게 된다.
LINQ 등을 활용할 수 있는 현실 코딩과 달리, 제한 시간 동안 구현하는 경우 인덱스를 직접 다루게 될 확률이 높다.
그런데 배열과 달리 리스트는 원소를 삭제하는 순간 자동으로 Trim이 일어난다.
따라서 어떤 리스트에서 2,3,5 번 원소를 삭제할때 다음과 같은 코드를 실행하게 되면 두가지 문제가 생긴다.
for(var i = 0; i < list.Count; i++) {
if(i == 2 || i == 3 || i == 5) {
list.RemoveAt(i);
}
}
또한 이것은 foreach 문을 사용해서 순번 기반이 아닌 값 비교로 원소를 삭제해도 같은 현상을 일으킨다.
결론적으로 문제는 전체 인덱스가 감소하는 것이다.
이 문제를 해결하는 형편없는 방법 중 하나는, 전체 인덱스를 루프전 별개의 변수로 저장하는 것이다.
그런 다음, 원소를 삭제할때 마다 인덱스 shifting을 고려해서 다음 원소를 좀더 앞당겨 삭제하는 것이다.
int count = list.Count;
위 방식은 여전히 삭제한 원소들의 갯수에 대한 기억이 필요하므로 코드가 매우 더러워진다.
전체 리스트를 크기가 변하지 않는 배열로 임시 변환해서 사용한다.
var convertedArray = list.ToArray();
for(var i = 0; i < convertedArray.Length; i++) {
if(i == 2 || i == 3 || i == 5) {
convertedArray[i] = null;
}
}
list = new List(convertedArray);
list.RemoveAll(null);
하지만 위 문제는 불필요한 보일러플레이트 코드와 형편없이 많은 레퍼런스와 값 복제를 일으킨다.
두가지 현상을 이용하면 간결하게 처리할 수 있다.
전체 원소를 지우면 마지막 원소의 인덱스는 변하지만, 첫 원소의 인덱스 0은 변하지 않는다.
인덱스 쉬프팅은 원소를 삭제한 지점에서 오른쪽 원소들에게 일어난다.
예를 들어 3번 원소를 삭제하면, 3번 이후의 원소들이 한칸씩 앞당겨지지만, 반대로 3번 이전의 원소들은 쉬프팅이 되지 않는다.
위 두 현상을 결합하면 다음 결론이 나온다.
마지막 인덱스에서 첫번째 인덱스 방향으로 순회하면서 원소를 삭제한다.
따라서 다음 코드로 원소를 삭제한다.
for(var i = list.Count-1; i >= 0; i--) {
if(i == 2 || i == 3 || i == 5) {
list.RemoveAt(i);
}
}
foreach 문으로 작성하면 다음과 같이 거꾸로 방향으로 순회하여 적용할수 있다.
foreach (var item in list.Reverse()) {
if(IsRemoveTarget(item)) {
list.Remove(item);
}
}
대부분의 경우에 적용할 수 있는 다음과 같은 트릭도 있다.
간결하지만, C#만의 트릭인지는 확인 필요.
list.RemoveAll(item => item.Value == someValue);
foreach (var item in list.ToList()) {
list.Remove(item);
}