글 읽기 - 시간초과

windowline1206 5년 전 0

예를들어 1400번줄의 J라면

"1400J" 이런식으로 키를 만들어서 맵을 구성하고 있는데...

시간 초과가 발생합니다 맵을 만드는 과정에서 숫자를 스트링으로 바꾸는 비용이 커서 그런 것일까요????

//
//  main.cpp
//  10541
//

#include <iostream>
#include <string.h>
#include <unordered_map>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

void createSearchMap(string word, unsigned long long height,
                     unordered_map<string, unsigned long long>& searchMap)
{
    int curWordOffset = 0;
    int wordLen = (int)word.length();
    
    for(unsigned long long h=1; h<=height; h++) {
        unsigned long long wordCntPerHeight = h;
        for(int i=1; i<=wordCntPerHeight; i++) {
            char c = word[ (curWordOffset + i - 1) % wordLen ];
            string key = string(to_string(h));
            key.push_back(c);
            if(searchMap.find(key)==searchMap.end()) {
                searchMap.insert(pair<string, unsigned long long>(key, 1));
            } else {
                searchMap[key]++;
            }
        }
        curWordOffset = (curWordOffset + h) % wordLen;
    }
}


int main(int argc, const char * argv[])
{
    unsigned long long N, K;
    string word;
    cin >> N;
    cin >> word;
    unordered_map<string, unsigned long long> searchMap;
    createSearchMap(word, N, searchMap);
    cin >> K;
    int h;
    char c;
    while(K-->0) {
        scanf("%d %c", &h, &c);
        string key = string(to_string(h));
        key.push_back(c);
        unsigned long long answer = searchMap[key];
        printf("%llu\n", answer);
    }
    
    return 0;
}

jh05013 5년 전 0

입력 범위를 보세요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과

windowline1206 5년 전 0

jh05013 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말