인프런 커뮤니티 질문&답변
작성한 질문수
JAVA 질문입니다. 5-2.LINE 인턴 채용 코딩 테스트 에서 List에 Map<Integer, boolean>을 사용한 이유가 궁금합니다.
해결된 질문
작성
·
23
0
일단 자바질문이라 죄송합니다. ㅎㅎㅎ
1. 현재 학습 진도
몇 챕터/몇 강을 수강 중이신가요? 5-2.LINE 인턴 채용 코딩 테스트 입니다.
어떤 알고리즘을 학습하고 계신가요? BFS 내용입니다.
여기까지 이해하신 내용은 무엇인가요?
time단위로 체크하기위해 visited list와 for문을 사용하는것을 이해했습니다.
2. 어려움을 겪는 부분
어느 부분에서 막히셨나요? visited에서 Map에 true를 받는 이유가 궁금합니다.
코드의 어떤 로직이 이해가 안 되시나요? visited에서 Map에 true를 받는 이유가 궁금합니다.
어떤 개념이 헷갈리시나요?
List<List<Integer>>를 사용 할 수 있을꺼 같은데 map을 사용한 이유가 궁금합니다.
3. 시도해보신 내용
문제 해결을 위해 어떤 시도를 해보셨나요? 강의를 10번정도 다시본거같습니다.
에러가 발생했다면 어떤 에러인가요? 초반에 while문 탈출조건을 잘못설정하여 무한루프가 돌았습니다.
현재 작성하신 코드를 공유해주세요
public static int solution(int c, int b) { int time = 0; Queue<int[]> q = new LinkedList<>(); q.add(new int[]{b, 0}); List<List<Integer>> visited = new ArrayList<>(200001); // [{},{} .... 20만개] for (int i = 0; i < 200001; i++) { visited.add(new ArrayList<>()); } while (c <= 200000) { c += time; if (visited.get(c).contains(time)) { return time; } time++; int qSize = q.size(); for (int i = 0; i < qSize; i++) { int[] cos = q.poll(); int nextB = cos[0]; if (nextB - 1 >= 0) { visited.get(nextB - 1).add(time); q.add(new int []{nextB - 1, time}); } if (nextB + 1 <= 200000) { visited.get(nextB + 1).add(time); q.add(new int[]{nextB + 1, time}); } if (nextB 2 <= 200000) { visited.get(nextB 2).add(time); q.add(new int[]{nextB * 2, time}); } } } return 0; }
이렇게 구체적으로 알려주시면, 더 정확하고 도움이 되는 답변을 드릴 수 있습니다! 😊
답변 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을 사용하는 것이 이점이 큽니다.
추가적인 질문 또는 다른 궁금한 점이 있다면 언제든지 문의주세요! 😊