[BOJ] 16139번 | 인간-컴퓨터 상호작용 (C++)

🔗문제 보러가기

16139번: 인간-컴퓨터 상호작용

 

🧑‍💻풀이 과정

---

나의 멍청한 실수

이전 문제에서 누적 합을 잘 구해놓고, 여기에서는 왜 적용을 못했나 싶습니다..

처음에는 DP[26][S.length()] 배열을 선언하여, 각 알파벳마다 등장한 횟수를 누적하여 저장하는 방식으로 접근하였습니다.

const int ALPHABET_COUNT = 26;
const int LOWER_A_ASCII = 97;
string S;

vector<vector<int>> DP(ALPHABET_COUNT, vector<int>(S.length()));
for (int i = 0; i < S.length(); i++)
{
    // i-1번 열의 누적 개수들 그대로 가져오기
    for (int j = 0; (i != 0) and (j < ALPHABET_COUNT); j++)
        if (DP[j][i-1] != 0)
        	DP[j][i] = DP[j][i-1];
    
    // S[i]에 해당하는 알파벳 개수 추가
    int index = S[i] - LOWER_A_ASCII;
    DP[index][i]++;
}

 

이렇게 잘 구해놓고, 왜 질문에서 DP[alphabet][r] - DP[alphabet][l - 1]을 생각 못 했나 싶네요...

아무튼, 위 식을 생각 못하는 바람에 이진 탐색(Binary Search)로 풀이 방향을 바꾸었습니다..

 

이진 탐색 방식 접근

1. 주어진 S 문자열에서, 각각의 알파벳들이 등장하는 인덱스 위치들을 배열로 담았습니다.
   • for 문으로 순차 탐색한 거라, 자동으로 오름차순 정렬이 되어 있습니다.
2. 문제에서 주어진 l, r에 대하여, l에는 lower_bound(), r에는 upper_bound()를 적용합니다.
   • lower_bound()와 upper_bound() 결과 각각에 vector.begin()을 빼면 인덱스 번호가 나옵니다.
3. 2번에서 구한 인덱스 번호 차이가 정답입니다.

 

✏️소스 코드 및 결과

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
const int ALPHABET_COUNT = 26;
const int LOWER_A_ASCII = 97;

int main()
{
	ios::sync_with_stdio(false);
	cout.tie(NULL); cin.tie(NULL);

	int quesitionCount;
	string sequence;
	cin >> sequence >> quesitionCount;

	// 1. 각 알파벳마다, 나오는 위치들을 저장
	vector<vector<int>> alphabetPositions(ALPHABET_COUNT);
	for (int i = 0; i < sequence.length(); i++)
	{
		int index = sequence[i] - LOWER_A_ASCII;
		alphabetPositions[index].emplace_back(i);
	}

	// 2. 이진 탐색을 이용하여, 인덱스 차이를 계산 후 출력
	for (int i = 0; i < quesitionCount; i++)
	{
		char find;
		int l, r;
		cin >> find >> l >> r;

		int index = find - LOWER_A_ASCII;
		int start = lower_bound(alphabetPositions[index].begin(), alphabetPositions[index].end(), l) - alphabetPositions[index].begin();
		int last = upper_bound(alphabetPositions[index].begin(), alphabetPositions[index].end(), r) - alphabetPositions[index].begin();

		cout << last - start << "\n";
	}

	return 0;
}