[C++]백준 - 6503번 문제

6503번: 망가진 키보드 (acmicpc.net)

6503번: 망가진 키보드

 

 

6503번 : 망가진 키보드

---

상근이의 키보드가 망가졌다. 키보드의 일부 키는 작동을 해서 아직 입력을 할 수 있다. 상근이는 키보드의 레이아웃을 바꿔서 단어를 입력하려고 한다. 지금 키보드에서 작동하는 키의 개수는 m개이다.

상근이가 입력하려고 하는 문장이 주어졌을 때, 키보드의 레이아웃을 바꾸지 않고 입력할 수 있는 연속하는 문자의 최댓값을 구하는 프로그램을 작성하시오. 키보드의 한 키는 문자 하나에 매핑되고, 다른 키와 조합을 이용해서 문자를 입력할 수는 없다. 즉, 최대 m개의 서로 다른 문자로 이루어진 가장 긴 부분 문자열을 찾으면 된다.

입력

---

입력은 여러 개의 테스트 케이스로 이루어져 있고, 각 테스트 케이스는 두 줄로 이루어져 있다. 테스트 케이스의 첫째 줄에는 m이 주어진다. (1 ≤ m ≤ 128) 둘째 줄에는 상근이가 입력하려고 하는 문장이 주어진다. 이 문장은 백만글자를 넘지 않으며, 공백을 포함할 수 있다. 공백도 문자로 생각하고 문제를 풀어야 한다.

입력의 마지막 줄에는 0이 하나 주어진다.

 

 

출력

---

각 테스트 케이스에 대해서 최대 m개의 서로 다른 문자로 이루어진 가장 긴 부분 문자열의 길이를 출력한다.

 

 

 

---

 

생각해 볼 점

---

투포인터로 푸는 문제입니다.

 

1. 문자열을 입력받습니다.

2. 문자열을 한글자씩 탐색합니다.

3. 사용된 글자가 몇회 사용되었는지를 담는 int is_used[128] 배열을 설정합니다.

4. 총 사용된 글자가 몇개인지 확인하기 위해 used_count = 0으로 설정합니다.

4. 투포인터이므로 Left, Right 인덱스를 설정한 후, 다음을 반복합니다.

 

>> 탐색한 글자가 이미 사용된 글자인가?

 

* 사용된 글자라면 -> Right++, is_used의 값 ++

* 사용한 적 없는 글자라면 ->> 키 배열이 꽉 찼는가? (used_count == m인가?)

 

* 꽉 찼을 경우 -> Left가 가리키는 글자의 is_used값--,

 

이때, is_used가 0이 되었다면 used_count-- Left++

 

* 여유가 있을경우 -> Right가 가리키는 글자의 is_used값++,

 

used_count++,  Right++

 

5. Right - Left의 값 중 가장 큰 값이 정답

 

 

위와 같은 과정을 반복하여.. Right가 문자열의 끝에 다다랐다면,

 

위의 과정을 종료하고 Right - Left의 최대값을 출력합니다.

 

 

코드

---

#include <iostream>
#include <string>
using namespace std;

int main()
{
	ios::sync_with_stdio(NULL);
	cin.tie(NULL);
	int m;
	cin >> m;

	int is_used[128];
	while (m)
	{
		string input;
		cin.ignore();
		getline(cin, input);
		fill_n(is_used, 128, 0);

		int ans = 0;
		int used_count = 0;
		int length = input.size();
		int left = 0, right = 0;
		while (right < length && left <= right)
		{
			char c = input[right];
			//이미 사용한 키일 경우
			if (is_used[c])
			{
				right++;
				is_used[c]++;
			}
			//사용한 적 없는 키일 경우
			else
			{
				//키 레이아웃이 모두 찬 경우
				if (used_count == m)
				{
					if(!--is_used[input[left]]) used_count--;
					left++;
				}
				//키 레이아웃이 비어있을 경우
				else
				{
					used_count++;
					is_used[c]++;
					right++;
				}
			}
			if (ans < right - left) ans = right - left;
		}
		cout << ans << "\n";
		cin >> m;
	}
	

	return 0;
}

 

그 외

---