[SW_Expert_Academy] 4581번 문자열 재구성 프로젝트 (Python)

코딩 1일 1문제 42일차!

SW Expert Academy

이 문제는 주어진 문자열을 가지고 앞과 뒤에서

하나씩 알파벳을 뽑아서 문자열을 만드는데 사전순으로 가장 빠른 문자열을 만드는 것이 목표인 문제입니다.

 

11회차만에.... 장장 12시간에 걸친 고민 끝에 풀었습니다.

처음부터 하나하나 손으로 적어가면서 풀어볼껄 하는 후회가 드는 문제였습니다.

 

Solution

input_num = int(input())

for i in range(input_num):
    input_text = str(input())
    text = list(input_text)
    
    answer = []
    
    front = 0
    end = len(text) - 1
    
    while(True):
        if front == end:
            answer.append(text[front])
            break
        
        if text[front] < text[end]:
            answer.append(text[front])
            front = front + 1
        elif text[front] > text[end]:
            answer.append(text[end])
            end = end - 1
        elif text[front] == text[end]:
            temp_front = front
            temp_end = end
            
            change_index = end
            
            while(True):
                if temp_front == end and temp_end == front:
                    break
                if text[temp_front] < text[temp_end]:
                    change_index = front
                    break
                elif text[temp_front] > text[temp_end]:
                    change_index = end
                    break
                temp_front = temp_front + 1
                temp_end = temp_end - 1
            answer.append(text[change_index])
            
            if change_index == front:
                front = front + 1
            elif change_index == end:
                end = end - 1
    print("#{} {}".format(i+1, "".join(answer)))

Solution 풀이

이문제의 조건은 크게 봤을때는 3가지의 조건을 가지고 있습니다.

앞과 뒤에서 알파벳을 하나씩 가져왔을때

1. 앞의 알파벳이 사전순으로 더 빠를 경우

2. 뒤의 알파벳이 사전순으로 더 빠를 경우

3. 앞과 뒤의 알파벳이 같을 경우

 

1번과 2번의 조건은 그렇게 어렵지 않게 구할수 있으나 

3번의 경우에는 최종적으로 완성된 문장이 만들수 있는 문장중에 사전순으로 가장 빨라야한다는 조건을 만족하기 위해서

3번의 경우가 걸렸을 경우

그 다음의 앞과 뒤 단어를 비교합니다.

그 다음의 앞과 뒤의 단어를 비교했을때

앞의 알파벳이 사전순으로 더 빠르다면 나중에 앞쪽의 알파벳을 떼서 정답에 붙여주고

뒤쪽의 알파벳이 사전순으로 더 빠르다면 나중에 뒤쪽의 알파벳을 떼어내서 정답에 붙여줍니다.

이는 임시로 지정한 temp_front, temp_last의 값이 각각의 end, front 값과 같아지기 전까지 반복합니다.

마지막으로 front 와 end 값이 같아지면 서로 가르키는 값이 같으므로 front위치의 값을 정답에 붙여주고 종료합니다.

 

 

SOMJANG/CODINGTEST_PRACTICE