map을 사용시 시간초과가 되는데 이유가 뭘까요...?
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
http://boj.kr/d466b4cc3d3048f990700e44cfc1de54
처음엔 위 링크와 같이 map으로 풀었는데 계속 시간 초과가 나더라구요... 예시 코드와 어느 부분에서 시간 차이가 나는 걸까요?
답변 2
0
안녕하세요 ㅎㅎ
map을 사용해서 그런데요.
map자체는 기본적으로 어떤 요소를 넣었을 때 키를 기반으로 자동으로 정렬하는 비용이 발생합니다.
그것 때문에 그런 거 같은데요 ㅎㅎ
한번 코드를 이렇게 고쳐보시겠어요?
vector<int> ma[10004];
int visited[10004];
int ar[10004];
감사합니다.
0
안녕하세요, 인프런 AI 인턴이에요.
map을 사용하여 시간 초과가 발생하는 원인을 판단하기 위해서는 코드를 확인해야 합니다. 하지만 제가 유사한 질문을 검색하여 찾아낸 링크나 코드를 토대로 원인을 추측해보겠습니다.
map 함수는 원래 리스트나 다른 iterable 객체의 각 요소에 대해 함수를 적용하여 새로운 리스트를 생성하는 함수입니다. 따라서 시간 초과가 발생한다면, 해당 함수의 동작이 너무 오래 걸리거나 메모리 부족으로 인해 문제가 발생했을 가능성이 있습니다.
즉, 처리해야 할 데이터의 규모가 매우 크거나 계산이 많아서 일시적인 시간 초과가 발생한 것일 수 있습니다. 이런 경우에는 다른 알고리즘을 고려해보거나 입력 데이터를 줄여서 테스트해보는 것이 도움이 될 수 있습니다.
또한, map 함수를 사용하여 새로운 리스트를 생성하게 되면 기존의 데이터를 복사하고 추가하는 연산이 필요하기 때문에 메모리 부담이 생길 수도 있습니다. 이 때문에 입력 데이터가 큰 경우에는 시간과 공간 복잡도 면에서 이점이 있는 다른 방법을 고려해 볼 수도 있습니다.
더 정확한 분석을 위해서는 실제 코드를 확인해야 하지만, 일단 이정도로 원인을 예상해 볼 수 있습니다. 추가적인 정보나 코드를 제공해주시면 더 정확한 답변을 드릴 수 있을 것 같아요. 감사합니다.
4 - A
0
22
2
코딩살구클럽 입장이 안됩니다
0
55
2
4-F 경우의 수 질문입니다.
0
32
2
코딩살구클럽 가입이 안됩니다.
0
67
2
살구 클럽에 대한 질문있습ㄴ디ㅏ
0
54
1
교안 158페이지 문의드립니다
0
44
2
코딩살구클럽 관련 건의사항
0
110
1
코살에 19942 다이어트 문제에 N의 범위가 빠져있슴니다
0
44
1
진행 방법 질문드립니다!
0
79
2
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
63
2
2주차 개념#12 트리 순회
0
32
2
백준사이트가 종료된다고 합니다.
0
313
2
백준 서비스 종료
9
945
1
sk 하이닉스 코테 대비
0
384
2
3-G 최댓값 질문
0
54
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
84
2
3-I 코드 질문드립니다.
0
63
2
3-N 질문 있습니다.
0
68
2
학습방법
0
105
2
4-H 질문 있습니다 (코드 리뷰)
0
69
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
182
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
71
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
65
2
1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.
0
53
2