04.15_CodeSignal(문자열을 뒤집어도 같은 같게 만드는 조건)

문제

'abcdc'를 뒤집어도 똑같은 문자열이 나오는 최소조건을 만드는 문제이다.

최소조건이란 최대한 적은 문자를 사용하라는 말이다.

 

풀이

처음에 문자열을 맨앞과 맨뒤를 비교하면서 같으면 넘어가고 다를 경우 기존 문자열에 추가하면 될거라고

생각했지만 하나의 문자열의 같은 문자가 반복되는 경우가 있기 때문에 정답이 될 수 없었다. 

다른 자료구조가 필요했다.

 

int pos : 문자열의 역순으로 들어갈 인덱스번호(pos번째까지)

int Length = st.Length;  :  문자열의 길이

 

예로 'abcdc'를 입력한다고 하자

if(st[iif (st[i] != st[j]) : 

{

 i = ++pos;
 j = Length - 1;

}

문자열의 맨앞과 맨뒤를 비교해서

다를 경우 맨앞의 문자열의 인덱스( pos증가 )를 한 칸 이동한다.

계속 해서 i를 증가시켜 맨 뒤 문자와 비교하다가 같은 문자가 나오면

맨 뒤를 가리키는 인덱스도 앞으로 이동해준다.

앞 뒤 문자가 같다는 말은 뒤집었을때 최소조건이 될 수도 있다는 말이다.

 

여기서 for문 조건을 통해 i가 h를 넘었다면 반복문을 종료한다.

하지만 종료조건이 아니라면 계속해서 내가 처음 생각했던 구조처럼

같은 문자가 반복되는 경우가 있기 때문에 계속 비교를 이어나가면 된다.

 

입력받은 문자열에 앞에서 부터 pos번째까지가 뒤집었을때 최소조건을 충족하는 문자들이 된다.