코드 최적화 설명

특정 문자가 문자열에 나타나는 횟수를 출력하는 C++ 코드가 있는데, 코드가 비효율적이라는 말을 들었습니다.

맵을 사용해서 코드를 효율적으로 만들어 줄 수 있나요?

#include <iostream>
#include <string>

using namespace std;

int main() {
  string input;
  cout << "Enter a string: ";
  getline(cin, input);

  for (int i = 0; i < input.length(); ++i) {
    char current_character = input[i];
    int count = 0;
    for (int j = 0; j < input.length(); ++j) {
      for (int k = 0; k < input.length(); ++k) {
        if (input[j] == current_character && j == k) {
          ++count;
        }
      }
    }

    bool already_printed = false;
    for (int k = 0; k < i; ++k) {
      if (input[k] == current_character) {
        already_printed = true;
        break;
      }
    }

    if (!already_printed) {
      cout << current_character << ": " << count << endl;
    }
  }

  return 0;
}

원래 코드는 O(n³)의 시간 복잡성을 갖습니다. 여기에서 n은 입력 문자열의 길이입니다. 이 문제는 중첩된 루프 때문에 발생합니다. 외부 루프는 각 문자를 통과하고, 두 번째 루프는 모든 문자에 대해 전체 문자열을 확인하고, 세 번째 루프는 불필요해 보일 수 있지만 최악의 경우에도 전체 문자열 길이를 통과합니다. already_printed를 확인하는 추가 루프는 프로그램 실행 시간을 O(n)배로 늘리지만, 이는 중첩된 루프만큼 중요하지 않습니다.

다음 최적화된 코드는 std::map을 사용해서 런타임을 O(n 로그 n)로 줄입니다. log n 팩터는 일반적으로 균형 잡힌 바이너리 검색 트리를 사용하여 구현되는 맵의 삽입 및 조회 작업에서 비롯됩니다.

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {
  string input;
  cout << "Enter a string: ";
  getline(cin, input);

  map<char, int> char_counts;
  for (char c : input) {
    char_counts[c]++;
  }

  for (auto const& [key, val] : char_counts) {
    cout << key << ": " << val << endl;
  }

  return 0;
}

개선 사항 설명:

1. std::map 사용: 원본 코드는 각 문자의 등장 횟수를 여러 번 계산하여 비효율적이었습니다. std::map(또는 std::unordered_map은 대부분의 경우 잠재적으로 더 빠른 성능을 제공하지만 최악의 경우 약간 느림)은 각 문자와 표시 횟수를 하나의 값으로 저장합니다. 이렇게 하면 문자 수를 두 번 이상 셀 필요가 없습니다.

2. 한 번 반복: 최적화된 코드는 입력 문자열을 한 번만 통과하여 char_counts 맵을 채웁니다. 이렇게 하면 중첩 루프를 사용했던 원래 코드에 비해 연산 횟수가 크게 줄어듭니다.

3. 효율적인 문자 수 계산: char_counts[c]++; 줄은 각 문자의 개수를 효율적으로 증가시킵니다. 문자가 아직 맵에 없으면 카운트가 1로 추가되고, 그렇지 않으면 기존 카운트가 증가합니다.

4. 중복 검사 제거: 원래 코드에서는 비효율적인 계산 방법으로 인해 already_printed 검사가 필요했습니다. 이 문제는 기본적으로 std::map에서 처리됩니다. 각 문자를 한 번만 계산하고 최종 루프가 맵을 통과하여 각 문자가 카운트와 함께 출력됩니다.

결론적으로 최적화된 코드는 시간 복잡성을 O(n³)에서 O(n 로그 n)로 낮추어 효율성을 크게 향상시킵니다. 입력 문자가 클수록 이러한 차이가 극적으로 커집니다. std::unordered_map을 사용하면 평균 성능이 O(n)으로 향상될 수 있지만 최악의 경우 성능이 약간 더 나빠질 수 있습니다. 선택은 특정 애플리케이션 및 최악의 사례에서의 성능이 중요한지 여부에 따라 달라집니다.