[회고록] 참조자 활용

알고리즘에서 참조자를 사용해야는 상황

가사 검색 문제를 풀다가 효율성에서 5개 중에 3개가 틀렸다는 결과를 받았다. 그래서 소스코드 리뷰를 하다가 효율성을 잡아먹는 라인이 어디에 있는지 불을 켜고 찾아댔다. 우선 이번 문제는 이진 탐색으로 접근했기 때문에 시간 복잡도는 O(logN) + 알파 가 되서 무리가 없을 거라 생각했다. 그렇다면 공간복잡도가 문제였던게 아닐까 하고 변수들을 흝어 보았다. 그것은 바로 이부분이었다.

// 알파벳순으로 정렬된 strs 문자열들 중에서 from문자열과 to문자열 사이에 있는 문자열들의 갯수를 리턴한다
int countByRange(vector<string> ss, string from, string to){
    vector<string>::iterator right = upper_bound(ss.begin(), ss.end(), to);
    vector<string>::iterator left = lower_bound(ss.begin(), ss.end(), from);
    
    return right - left;
}

이 코딩 문제의 가사 단어는 2 ~ 100,000 이고 각 가사 단어의 길이는 1 ~ 10,000 이기에 특정 길이의 가사 단어들을 가진 vector를 매번 복사 인자로 받기에는 부담이다. 그럼 어떻게 하면 될까? 참조자나 포인터로 기존 벡터를 참조해주면 된다. ss vector변수를 참조자로 선언하였다. 이렇게 해주니 드디어 정답 처리를 받았다.

// 알파벳순으로 정렬된 strs 문자열들 중에서 from문자열과 to문자열 사이에 있는 문자열들의 갯수를 리턴한다
int countByRange(vector<string>& ss, string from, string to){
    vector<string>::iterator right = upper_bound(ss.begin(), ss.end(), to);
    vector<string>::iterator left = lower_bound(ss.begin(), ss.end(), from);
    
    return right - left;
}

ps. ‘&’ 선언이 있고 없고에 정답과 오답 처리가 갈리다니, 코딩의 세계는 혹독하다.