algospot 재하의 금고 (문제 ID: JAEHASAFE) c++

알고스팟 문제 링크: https://www.algospot.com/judge/problem/read/JAEHASAFE

algospot.com :: JAEHASAFE

문자열을 시계 방향, 반시계 방향 번갈아가면서 시프트하여 목표하는 문자열과 일치하려 했을때 필요한 최소 시프트 횟수를 구하는 문제이다.

 

문자열의 일치는 kmp알고리즘(유명하고 많이 쓰이는 알고리즘이지만 이해하기 다소 어렵다,,,)을 이용하여 풀 수 있다.

현재 문자열을 시계 방향으로(오른쪽으로) 시프트 해서 다음 문자열과 일치할때의 최소 시프트 횟수를 알고 싶다면,

다음 문자열을 두개 이어붙인 문자열과 현재 문자열을 kmp알고리즘으로 비교하면 된다.

이때 kmp알고리즘에서 나오는 벡터의 첫번째 요소가 최소 시프트 횟수가 된다.

반시계 방향으로(왼쪽으로) 시프트 해서 다음 문자열과 일치하는것은

현재 문자열을 두개 이어붙이것을 다음 문자열이 오른쪽으로 시프트하는것을 비교하여 일치할때의 시프트 횟수를 찾으면 된다.

즉, 반시계 방향일때는 shifts 함수의 매개변수 순서만 바꿔주면 된다.

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/20.%20string/JAEHASAFE.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2