튜기's blogggg

Non-repetitive String

by St1tch






★내가 푼 방식

우선 어떤식으로 Output이 정해지는지 일일이 계산을 해보았다.

일단 처음에 1이써지고 그다음수(A)는 이전의 수와 다른 숫자중에 가장작은수로 가정한다.

그다음 이전에 써진 수들과 비교를 한다. 만약 지금 구하고있는 수가 k번째이면 

비교방식은 바로앞의수와 1개씩(k와 k-1),2개씩(k,k-1와 k-3,k-2) .... 지금까지의 문자열의 길이 / 2개 만큼 비교를한다. 

만약에 같은 문자열이 존재하면 가정했던수를 +1 시키고(A+1), 존재하지 않으면 다음문자(k+1번째)를 위와 같은 방법으로 구한다.

같은 문자열이 계속해서 존재해서 A가 K보다 커지면 K-1번째수를 +1시키고 K-1번째부터 다시 조사한다.

BackTracking느낌으로 A가 K보다 커지면 다시 뒤에수를 구하다가 처음까지 갔는데 A가 K보다크면 

조건을 만족하는 문자열이 없다는 소리이므로 -1을 반환한다.



abcdefghi

1. i와 h비교 

2. fg와 hi비교

3. def와 ghi비교

4.bcde와 fghi비교

이런식으로 비교하며 같은것을 확인하며 문제를 풀었다.

예외를 잘 처리해야한다. A가 K보다 커질때 뒤로 돌아오는 것이 이 풀이방법에서 중요했던거같다.


★풀이 코드★








[출처] Non-repetitive String|작성자 튜기


블로그의 정보

튜기's blogg(st1tch)

St1tch

활동하기