인프런 커뮤니티 질문&답변
작성한 질문수
map을 사용시 시간초과가 되는데 이유가 뭘까요...?
해결된 질문
작성
·
210
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 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 함수를 사용하여 새로운 리스트를 생성하게 되면 기존의 데이터를 복사하고 추가하는 연산이 필요하기 때문에 메모리 부담이 생길 수도 있습니다. 이 때문에 입력 데이터가 큰 경우에는 시간과 공간 복잡도 면에서 이점이 있는 다른 방법을 고려해 볼 수도 있습니다.
더 정확한 분석을 위해서는 실제 코드를 확인해야 하지만, 일단 이정도로 원인을 예상해 볼 수 있습니다. 추가적인 정보나 코드를 제공해주시면 더 정확한 답변을 드릴 수 있을 것 같아요. 감사합니다.