[백준 / BOJ] 6503 망가진 키보드

문제

출처 : www.acmicpc.net/problem/6503

6503번: 망가진 키보드

상근이의 키보드가 망가져서, 키보드에서 작동가능한 키가 m개 밖에없다.

상근이가 입력하려는 문자가 주어졌을때,

m개의 키를 눌러서 입력할수있는 최대 부분 문자열의 길이를 구하는 문제다.

 

풀이

예제 출력을보면 This can't be solved by brute force 라고 친절히 적혀있으므로 완전탐색으로는 풀리지않고, 

(문자열의 갯수가 완탐으로는 못풀만큼 입력되는듯) 다른 방법으로 풀어야한다.

 

두 포인터로 풀었는데,

문자열의 최대길이는 백만이다. left와 right값이 중복되지않게 늘려갈것이므로(항상 right >= left), 두포인터로 한 문자열을 탐색하는데 걸리는 반복횟수는 (항상 m을 최대로 사용했을때,) (2 * 문자열의 길이) 번이다.

 

두 포인터로 left ~ right 범위에서 나온 문자의 갯수가 m이하라면 right + 1을 해준다. 아니라면, 나온 문자의 갯수가 m 이하가 될때까지 left + 1을 해준다.

나온 문자열의 갯수는 check배열을 통해서 체크해줬다. check배열을 구현할때 중요한건, 문자가 중복되서 나올수있기때문에, check배열을 true, false로 선언(나왔는지 안나왔는지만 체크)하는게 아닌 check[나온문자] = 문자가 나온 횟수 형태로 저장해줘야한다.

 

예를들어,

3

abcaadddd

일경우,

 

left = 0, right = 4일때, 나온 문자의 갯수는 a,b,c 3개이다.

이때, check배열을 bool형태로 선언해서 나온지 안나왔는지만 체크할경우, left + 1을 하면서 a는 나오지 않은 문자로 처리해버릴수있다. 하지만 idx = 3, idx = 4 에서 a가 나오므로 반례가 생긴다.

따라서, check배열에 문자가 나온 횟수를 저장해서 check[(int)a]-1 을 해주며 check[(int)a] == 0 일때 나온 문자의 갯수를 -1 해줘야한다.

 

아래는 틀렸습니다가 뜨길래 생각한 반례고 이걸 고치니 맞았음

난 출력이 1 이 나왔는데,

c -> a -> b를 탐색하고, bb가 나오는 경우를 봐주지않고있었다.

1

cabb

0

출력 : 2

소스코드

https://github.com/devxb/JJUNalgo/blob/master/6503%20%EB%A7%9D%EA%B0%80%EC%A7%84%20%ED%82%A4%EB%B3%B4%EB%93%9C/main.cpp

devxb/JJUNalgo