재하의 금고1 (문자열, 환형시프트)

문제는 아래 링크를 참고하세요

https://algospot.com/judge/problem/read/JAEHASAFE

문제를 최초에 잘못이해해서 거의 두시간은 낭비한것 같습니다.

돌리는 방향의 순서가 정해져있는데

혼자서 왼쪽 오른쪽 모든경우의 수를 생각하며 동적계획법까지 고려해서 짯는데 아니더군요 ㅜㅜ 

문제를 잘 푸는데 한가지 방법은 문제를 정확하게 이해하는것도 중요함을 다시금....

이번 글의 알고리즘은 효율적인 알고리즘이 되지 못합니다.

더 좋은 방법이 존재하는데 이는 다음 글을 확인하세요

---

문제에 따라 주어진 순서대로의 금고 상태를 

왼쪽 오른쪽으로 순서있게 돌리며 최소 몇번만에 마지막 상태에 도달 할 수 있는지에 대한 문제입니다.

별거 아닌것 같지만 문자열을 비교해야 한단것 자체가 알고리즘 상에선 부담이 됩니다.

또한 금고를 돌리는건 어떻게 처리할 것인가에 대한 고민도 필요합니다 (문자열을 돌린다는 의미)

우선 환형시프트를 만드는것을 고민해야 합니다.

1. char문자열을 일일이 복사해서 새로운 상태를 만들수도 있지만

이렇게 하면 매번 문자열길이 N만큼의 반복이 필요해서 낭비가 심합니니다.

2. deque(queue+stack)를 이용한다면 시프트에 대한 고민은 쉽게 해결합니다

pop,back을 앞뒤에서 처리할 수 있기 때문입니다.

하지만 문제는 남아있습니다.

deque에 들어있는 char값들을 다시 char 문자열이나 string을 바꾸어야만

다른 문자열과 비교가 가능해집니다.

결국 비교를 시도할 때 마다 또 복사가 이루어져야 하므로 1.과 시간복잡도는 크게 달라지지 않을것 같습니다.

하지만 구현은 상대적으로 간단해집니다.

3. 다른 한가지 방법은 head를 두어 shift를 할 때마다 현재 head인 인덱스값만 저장하고 있다가

비교할 때 만 head인덱스를 이용하여 문자열을 비교하는 것 입니다.

별로 어려운 구현은 아니라 봅니다.

---

다음은 문자열의 비교가 필요합니다

금고를 돌린다음 현재 목표 상태와 일치하는지 확인해야 하기 때문입니다.

strcmp를 이용할 수도 있지만 이전의 게시글인 kmp알고리즘을 역시 그대로 이용합니다.

문제 조건에 문자열길이는 10000이하가 조건이므로 문자열이 길다면

문자열비교에 많은 시간의 낭비가 생길 수 있습니다.

금고를 돌리며 head가 계속 이동하였으므로 별도로 문자열을 잘라서 다시 붙여야하는 작업을 필요로 합니다.

compareQ에서 그러한 작업을 하게됩니다.

헤더의 인덱스가 현재 i이며 len(str)=N이라면

newString  = str[i...(N-1)] + str[0...(i+1)]

로 새로 문자열을 조립해야합니다.

이를 위해서 memcpy를 이용하게 됩니다.

strncpy을 이용해도 사실 무방할것 같습니다.

구글링을 해본 결과는 memcpy나 strcpy의 속도차이는

플랫폼 환경, 에디터의 설정에 따라서도 달라질 수 있는 모양인가 봅니다.

(strcpy는 NULL(0)을 만날때까지 복사가 이루어지지만 strncpy는 정해진 갯수만큼 복사를 하게 됩니다.

memcpy는 좀더 범용으로 쓸 수 있는것이죠 하지만 다른 변수로의 메모리침범이 이루어져 원하는 복사가

이루어지지 않을 수 있으므로 memcpy_s를 이용하면 조금 더 안전하게 쓸 수 있습니다.)

어쨋든 head인덱스를 기준으로 잘라붙여서 

문자열을 새로 조립한 뒤 kmp알고리즘을 이용해서 비교해 동일여부의 결과를 얻어낼 수 있습니다.

해서 완성된 코드는 다음과 같습니다.

lokcer함수에서 순서대로 돌려가며 비교를 하는 작업을 하고있습니다.