작성한 질문수 2

0

안녕하세요 인호님 좋은 질문 감사합니다!! List<List<Integer>>와 List<Map<Integer, Boolean>>의 차이를 정확히 짚어주셨네요. 이건 시간복잡도와 직결되는 중요한 선택입니다.

두 방식의 가장 큰 차이는 "특정 시간에 방문했는지 확인"하는 연산의 속도입니다.

List<List<Integer>>를 사용하는 경우

if (visited.get(c).contains(time))  // O(N) - 리스트 전체를 순회해야 함

List<Map<Integer, Boolean>>를 사용하는 경우:

if (visited.get(c).containsKey(time))  // O(1) - 해시맵은 즉시 조회

이 문제에서는 같은 위치를 여러 다른 시간에 방문할 수 있어요. 예를 들어 위치 10을 1초, 3초, 5초, 7초... 이렇게 여러 번 방문할 수 있죠. 시간이 지날수록 각 위치마다 저장된 시간 데이터가 계속 쌓이는데, List로 contains를 쓰면 매번 리스트를 처음부터 끝까지 확인해야 합니다.

왜 Map에 Boolean을 저장할까?

사실 value는 중요하지 않아요. 우리가 진짜 필요한 건 "이 시간에 방문했는가?"라는 정보뿐이니까요. Map을 일종의 Set처럼 쓰는 용도입니다

// 이렇게 생각하면 돼요
Map<Integer, Boolean> = "시간을 키로 가진 집합"
visited[위치].containsKey(시간) = "이 위치에 이 시간에 온 적 있나?"

Set을 쓰면 더 명확할 수도 있지만, Map도 충분히 직관적이고 실전에서 자주 쓰이는 패턴입니다.

개선된 코드 제안

작성해주신 현재 코드에서 한 가지만 더 추가하면 좋을 것 같습니다. 중복 방문 체크가 빠져있네요!

public static int solution(int c, int b) {
    int time = 0;
    Queue<int[]> q = new LinkedList<>();
    q.add(new int[]{b, 0});
    
    // Map 방식으로 변경
    List<Map<Integer, Boolean>> visited = new ArrayList<>(200001);
    for (int i = 0; i < 200001; i++) {
        visited.add(new HashMap<>());
    }
    
    while (c <= 200000) {
        c += time;
        if (visited.get(c).containsKey(time)) {
            return time;
        }
        
        int qSize = q.size();
        for (int i = 0; i < qSize; i++) {
            int[] cos = q.poll();
            int nextB = cos[0];
            int nextTime = cos[1] + 1;  // 시간 증가
            
            // 중복 방문 체크 추가! 이게 핵심입니다
            if (nextB - 1 >= 0 && !visited.get(nextB - 1).containsKey(nextTime)) {
                visited.get(nextB - 1).put(nextTime, true);
                q.add(new int[]{nextB - 1, nextTime});
            }
            
            if (nextB + 1 <= 200000 && !visited.get(nextB + 1).containsKey(nextTime)) {
                visited.get(nextB + 1).put(nextTime, true);
                q.add(new int[]{nextB + 1, nextTime});
            }
            
            if (nextB * 2 <= 200000 && !visited.get(nextB * 2).containsKey(nextTime)) {
                visited.get(nextB * 2).put(nextTime, true);
                q.add(new int[]{nextB * 2, nextTime});
            }
        }
        time++;
    }
    return -1;  // 못 잡는 경우
}

중복 체크 없이 큐에 계속 추가하면 같은 (위치, 시간) 조합이 여러 번 들어가서 메모리도 터지고 시간도 오래 걸려요.

Map을 쓰는 이유는 빠른 조회(O(1)) 때문입니다. 코딩테스트에서 시간복잡도는 정말 중요하니까, "검색/조회가 자주 일어나는가?"를 항상 체크해보시면 좋을 것 같스빈다!!

• 자주 검색: Map, Set (O(1))

• 순서대로 저장만: List (O(N) 검색)

강의를 10번이나 다시 보셨다니 넘넘 멋지십니다!!!! 이렇게 깊게 고민하는 자세가 실력을 쌓는 지름길입니다 좋은 주말 보내세요!!

0

안녕하세요, 인프런 AI 인턴입니다. 백인호님, 질문해주신 내용에 대해 답변드리겠습니다.

List<Map<Integer, Boolean>> 대신 List<List<Integer>>를 사용하는 것과 관련해 설명드리자면, 각 데이터 구조는 데이터 저장 및 조회 방식에서 장단점이 있습니다.

Map<Integer, Boolean>을 사용하는 이유는 특정 시간에 해당 위치를 방문했는지를 빠르게 확인하기 위함입니다. Map을 사용하면 시간이 O(1) 정도로 조회가 빠르며 이는 BFS 처럼 여러 단계로 진행되는 알고리즘에서 중요할 수 있습니다. 방문 여부를 저장할 때 true 값을 사용하면서 관리가 쉽기 때문입니다. List를 사용하면 특정 요소의 존재 여부를 확인하기 위해 전체 리스트를 순회해야 하므로 상대적으로 무거운 연산이 될 수 있습니다.

이러한 이유로 많은 경우 시간 복잡도 처리를 위해 Map을 사용하는 것이 이점이 큽니다.

추가적인 질문 또는 다른 궁금한 점이 있다면 언제든지 문의주세요! 😊

Spring Boot 설명서