문제점

팀 프로젝트를 하는 중 두가지 리스트를 순회하면서 값을 변경해야 하는 상황이 생겼는데
초기 코드에서 급한 상황 + 뇌정지로 인한 O(MN)복잡도가 만들어졌었다.

시간 복잡도를 해결하기 위해 여러 방법이 있지만 이번에는 HashMap을 이용해서 시간복잡도를 해결해 보았다.

왼쪽이 초기 작성한 두 번의 For문이 사용된 O(MN) 복잡도이며, 오른쪽이 맵을 사용해서 O(M+N)까지 선형 탐색을 줄인 코드이다.

코드 분석

HashMap 초기화

일단 코드를 보면 statusMap을 초기화 하는 과정을 보면

Map<Long, Status> statusMap = statusList.stream()
        .collect(Collectors.toMap(Status::getId, status -> status));

같이 사용되었다. 여기서 Status::getId는 Status 객체의 Id를 호출하여 Map의 Key로 사용한다.

status -> status는 status 객체 자체를 값으로 사용한다.

결과를 조금 더 명시적으로 보자면

// statusList
[
    { statusId: 1, sequence: 1 },
    { statusId: 2, sequence: 2 },
    { statusId: 3, sequence: 3 },
    { statusId: 4, sequence: 4 }
]

statusList는 뭐 더 다른값이 있긴 하지만 이번에 사용하는 값은 저 두 가지의 값을 가지고 생각하자
저기서 Status::getId 이걸 사용하여서 key로 사용한다 했고 따라서 전체적인 Map의 구조는

// statusMap
[
    1: { statusId: 1, sequence: 1 },
    2: { statusId: 2, sequence: 2 },
    3: { statusId: 3, sequence: 3 },
    4: { statusId: 4, sequence: 4 }
]

id값이 Key로 달린 Map이 완성된다.

반복을 통한 업데이트

이제 currentStatusSequence 리스트 순회 과정을 볼텐데

반복문 전체 코드를 보면 다음과 같다.

for (StatusUpdateRequestDto requestDto : currentStatusSequence) {
    Status status = statusMap.get(requestDto.getStatusId());
    if (status != null) {
        status.setSequence(requestDto.getSequence());
    }
}

일단 한 줄씩 분석을 해보자면 첫 줄은 간단하게 반복문 순회이니 넘어가도록 하고,

2번째 줄을 보면 requestDto.getStatusId() 를 사용하여 해당하는 값의 Status 객체를 statusMap에서 가져온다.

다시 Json을 곁들여 설명해본다면

// statusMap
[
    1: { statusId: 1, sequence: 1 },
    2: { statusId: 2, sequence: 2 },
    3: { statusId: 3, sequence: 3 },
    4: { statusId: 4, sequence: 4 }
]

// currentStatusSequence
[
    { statusId: 1, sequence: 1 },
    { statusId: 4, sequence: 2 },
    { statusId: 2, sequence: 3 },
    { statusId: 3, sequence: 4 }
]

값이 이렇게 주어졌을 때 처음 순회를 하는 과정은 currentStatusSequence 의 statusId 가 1 이므로 statusMap에서 가져오는 데이터는 Key가 1인 { statusId: 1, sequence: 1 } 이 될 것이다.

그 다음줄을 보면

if (status != null) {
    status.setSequence(requestDto.getSequence());
}

requestDto.getSequence()의 값이 1이고 1을 status의 sequence에 넣어주는데 이미 동일한 값을 가지고 있기 때문에 값이 변경되지 않는다.

그럼 만약에 currentStatusSequence 의 순서대로 할 때 두번째 statusId 가 4라면
statusMap에서 가져오는 데이터는 Key가 4인 { statusId: 4, sequence: 4 }를 가져오고,

다시 값을 변경하는 라인으로 들어가서 currentStatusSequence의 두 번째 { statusId: 4, sequence: 2 } 에서 sequence를 넘겨주기 때문에 stauts는 { statusId: 4, sequence: 2 }는 이렇게 변경된다.

사실 구조가 조금 다를 수 있지만 뭐가 다르냐고 할 때 처음에 DB에서 받아온 List를 통해서 보면 변경점이 보인다.

// statusList
[
    { statusId: 1, sequence: 1 },
    { statusId: 2, sequence: 2 },
    { statusId: 3, sequence: 3 },
    { statusId: 4, sequence: 2 }
]

이러한 과정으로 쭉 순회하며 값을 변경하다 보면 다음과 같이 변경된다

[
    { statusId: 1, sequence: 1 },
    { statusId: 2, sequence: 3 },
    { statusId: 3, sequence: 4 },
    { statusId: 4, sequence: 2 }
]

그리고 값을 저장하는 과정 외에 불러오는 과정은 모두 sequence를 기준으로 orderBy하기 때문에 걱정이 없다.
List<Status> statusList = statusRepository.findByBoardIdOrderBySequence(board.getId());