[자바] 문자열리스트안에 특정 문자열 제거 후 맨 마지막으로 이동시키기

업무를 하던 중 코드를 개선하기 위해 고민을 했던 로직이 있어서 공유차 글을 남깁니다~

 

상황

• A라는 리스트 안에서 "특정문자" 라는 문자열을 찾는다.
• 현재 위치에서 가장 마지막으로 위치를 변경하고 싶다.

 

가장 먼저 직관적으로 떠오로는 코드를 적어보겠습니다.

ArrayList<String> list = new ArrayList<>(Arrays.asList("value1", "value2", "value3"));

if (list.contains("value2")) {
    list.remove("value2");
    list.add("value2");
}

위의 코드를 설명드리면

- 리스트를 할당합니다.

- value2가 리스트에 있는지 체크합니다

- value2를 제거합니다.

- value2를 리스트에 넣습니다.

 

저의 생각에는 절대 틀린 코드는 아니라고 생각합니다!!

다만, 시간복잡도 관점에서 불필요한 시간이 추가된 것 같은 느낌을 받았고 수정할 수 없을지 고민했습니다.

 

이번에는 수정한 코드입니다.

ArrayList<String> list = new ArrayList<>(Arrays.asList("value1", "value2", "value3"));

int index = list.indexOf("value2");
if (index >= 0) {
	list.add(list.remove(index));
}

위의 코드를 설명드리겠습니다.

- 리스트를 할당합니다.

- value2의 index를 찾습니다. 여기서 존재하지 않는다면 -1이 나오게 됩니다.

- value2가 리스트에 존재하면 삭제후 추가합니다.

 

이제는 두 코드의 시간복잡도에 대해서 분석해보겠습니다.

 

우선, 첫번째 코드입니다.

list.contains("value2")에서 시간 복잡도 O(n)만큼 사용이됩니다.

list.remove("value2")에서 시간 복잡도 O(n)만큼 사용됩니다. (삭제하기 위해서 데이터를 찾아야 하기 때문)

list.add("value2")에서는 시간복잡도 O(1)만큼 사용됩니다.

 

총 2O(n) + 1의 시간 복잡도를 갖습니다.

 

두번째 코드입니다.

list.indexOf("value2")에서 시간복잡도 O(n)을 갖습니다.

list.add(list.remove(index) -> 여기에서 제거하는데 O(1), 추가하는데 O(1)의 시간복잡도를 갖습니다.

총 O(n) + O(2)의 시간복잡도를 갖습니다.

 

물론, 두 시간복잡도를 무한대로 뒀을 때 둘다 O(n)이기 때문에 큰 차이는 없지만

일단은... 시간 복잡도가 줄어들었음을 확인해봤습니다... (처음 글을 작성할 때는 더 엄청난 차이가 있을줄 알았...는...데 ㅠㅠ)

 

 

추가로... 더 좋은 코드를 발견해서 코드만 공유드리겠습니다..

ArrayList<String> list = new ArrayList<>(Arrays.asList("value1", "value2", "value3"));

if(list.remove("value2")){ // 시간복잡도 O(n)
	list.add("value2"); // 시간복잡도 O(1)
}
// 전체 O(n) + O(1)