buildPalindrome

Given a string, find the shortest possible string which can be achieved by adding characters to the end of initial string to make it a palindrome.


Example

For st = "abcdc", the output should be
solution(st) = "abcdcba".


Input/Output

[execution time limit] 4 seconds (py3)

[input] string st

A string consisting of lowercase English letters.

Guaranteed constraints:
3 ≤ st.length ≤ 10.

[output] string


문자열이 주어지면, 그 문자열을 Palindrome (회문) 으로 만들어 return 하는 문제이다.

도대체 어떻게?? 코드를 짜야 할지 모르겠었다.

  • 문자열의 가운데부터 시작해 최소의 palindrome 을 찾아내고, 양 쪽을 같게 만들어줘야 하나?? X 가운데에서 회문이 시작한다고 장담하지 못함X

  • (+) palindrome 인지 검사해 맞다면 그대로 RETURN, 아니라면 본문 시작...

많이 헤메고 스스로 생각해보았지만 오랜 시간이 걸려서 구글링, 솔루션을 보고 내 것으로 만들어야 겠다고 생각했다.


Solution

def solution(st):
    string_list = list(st)
    i = 0
    while string_list != string_list[::-1]:
        string_list.insert(len(st),st[i])
        i += 1
    return "".join(string_list)

list 형으로 변환해, list 가 reverse_list 와 같아질 때 까지 list의 끝에 st[i]를 넣는다.

예)
st = "abcdc"

string_list = ['a', 'b', 'c', 'd', 'c']

['a','b','c','d','c'] != ['c','d','c','b','a'] 이므로 동작,

len(st) = 5 이므로 ['a', 'b', 'c', 'd', 'c', 'a']

반대로 한 것이 또 다르므로,

['a','b','c','d','c','b','a']

예제가 해결되어 string 형으로 return 해준다.


밑의 코드는 palindrome의 범위를 지정해 같아지는 범위를 찾아 return 해준다.

def solution(st):
    for i in range(0,len(st)):
        if(st[i:len(st)] == st[i:len(st)][::-1]):
            return st[0:i] + st[i:len(st)] + st[0:i][::-1]

내가 고민하고, 또 고민하는 것들이 이렇게 간결하고 쉬운 코드로 바뀌려면 어떤 노력을 해야할 지 ... 지금 이대로 알고리즘 문제를 꾸준히 풀고, 모르는 것은 내 것으로 만들기 위해 노력하고. 책을 읽으면서 '꾸준히' 앞으로 나아가야겠다.

좋은 웹페이지 즐겨찾기