1-i 포켓문 문제 시간초과

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

이와 같이 코드를 작성하였는데 시간 초과가 나는데 왜 그런 것인가요?

일부러 시간복잡도가 m*n이 되지 않게 하려고 맵 2개를 만들어서,

o(n)이 최고 시간복잡도가 되게끔 설계하였습니다.

#include <bits/stdc++.h>

using namespace std;

int n; // 포켓몬의 수 
int m; // 문제 수 



map<int, string> poketmonsByNumber;
map<string,int> poketmonsByName;

vector<string>searchId;

string name;
string question;



int main(){
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>> n >> m;
    for(int i=0; i<n; i++){
        cin>>name;
        poketmonsByNumber[i+1]=name;
        poketmonsByName[name]=i+1;
        
        
    }
    for(int i=0; i<m; i++){
         cin>>question;
            if (isdigit(question[0])) {
            int id = stoi(question);
            searchId.push_back(poketmonsByNumber[id]);
            }
            else{
            string id=to_string(poketmonsByName[question]);
            searchId.push_back(id);
            }
        };
        
        
         
         

       
         
    
    
    for(auto id : searchId) {
       
        cout<<id<<endl;
    }
    

    
    
   
    return 0;
}

안녕하세요, 인프런 AI 인턴입니다.

시간 초과 문제가 발생하는 주된 원인은 입출력(I/O) 관련 코드와 알고리즘의 복잡도에서 발생할 수 있습니다. 제공하신 코드를 기반으로, 이미 인프런의 “10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트” 과정 내 질문들 중 시간 초과 문제를 해결한 예시들을 찾았습니다.

시간 초과 해결 기본 조치: ios::sync_with_stdio(false);, cin.tie(NULL);, cout.tie(NULL); 가 이미 적용되어 있네요. 이는 C++의 입출력 속도를 높여 시간 초과를 줄이는 효과가 있습니다.
출력 방식 변경: endl 대신 "\n"을 사용하세요. endl은 출력 버퍼를 매번 비우기 때문에 속도가 느려집니다. 이 부분은 코드에서 확인된 것은 아니지만, [시간초과](https://www.inflearn.com/questions/472892) 상황 해결에 도움이 될 수 있습니다.
알고리즘 복잡도: 설계 상 O(n) 복잡도를 예상하셨으나, 실제로는 입력 받는 방식이나 처리 과정에서 예상치 못한 복잡도 증가가 발생할 수 있습니다. 특히, map을 사용할 때 key 검색에 O(log n)의 시간이 소요됨을 고려해야 합니다.
비효율적인 탐색 최적화: 만일 포켓몬의 이름이나 번호를 탐색할 때 비효율적으로 처리되고 있다면, 탐색 과정을 최적화할 방법을 모색해야 합니다. 다만, 제공된 코드를 보니, 이미 맵을 효율적으로 사용하고 계신 것 같습니다.

이러한 조치들에도 불구하고 여전히 시간 초과가 발생하는 경우, 다른 학습자들의 질문과 답변을 통해 문제를 해결한 사례를 참고하시는 것이 좋습니다. 예를 들어, 사용한 알고리즘의 복잡도를 다시 검토하거나, I/O 관련 최적화 방안을 더욱 철저히 적용할 필요가 있을 수 있습니다.

제시한 링크 외에도, 다음 링크에서 시간 초과 관련 해결책을 찾아보실 수 있습니다:
- “1-I 시간초과 질문 있습니다. - 인프런”에서는 map 순회 시 발생할 수 있는 시간 초과 문제와 그 해결책에 대해 설명하고 있습니다.
- “이다솜 문제 시간초과.. ㄷㄷ - 인프런”에서는 입출력 최적화 조치가 시간 초과 해결에 얼마나 중요한지 강조합니다.
- “다솜이형… 나의 완패야… 인정할게… (1620 시간초과 관련) - 인프런”에서는 endl 대신 "\n" 사용을 권장하여 시간 초과 문제를 해결하는 방법을 제안합니다.
- “1-I문제 / 시간 빡세다의 정의 궁금증 - 인프런”은 시간 복잡도와 입출력 최적화가 시간 초과에 미치는 영향에 대한 설명입니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변