알고리즘 스터디 - HackerRank : Bigger is Greater

문제 해석

• 이번 문제는 문자열이 주어졌을 때 이를 다시 재배치해서 주어진 문자열보다 큰 문자열 중 가장 작은 문자열을 구하는 것이다.
• 예를 들어, abcd가 주어졌을 때, abdc, acbd, acdb, ... 등 더 큰 문자열 중 가장 작은 문자열을 구하는 것으로 볼 수 있다.
• 만약 더 큰 문자열이 존재하지 않으면 "no answer"을 출력한다.

어떻게 구현해야 할까?

ab -> [a, b] -> ba
hefg -> [e, f, g, h] -> he(gf)
dkhc -> [c, d, h, k] -> dk(ch) False -> d(khc) False -> h(cdk)

원리 1 : 조합 생성 후 비교

from itertools import permutations

str_list = [''.join(p) for p in permutations('string')]

• 이 경우 문자열의 길이가 100이고 너무 많은 숫자의 문자열이라 시간초과가 발생하게 된다.

원리 2 : 그 다음으로 작은 문자열 찾기

• 우리가 문자를 찾을 때 뒤에서 부터 비교하는 것처럼 뒤에서 시작한다.
• 그리고 찾은 문자를 기준으로 뒤에 있는 문자는 다시 정렬하게 된다.

def biggerIsGreater(w):
	# 문자를 문자 리스트로 변환
    str_list = list(w)
    
    # 뒤에서부터 비교하는데 뒤에 있는 문자가 앞에 있는 문자보다 작은 경우를 찾음 
    length = len(str_list) - 1
    while length > 0 and str_list[length-1] >= str_list[length]:
    	length -= 1
    
    # 만약 length가 0이하면 더이상 작은 것도 없다는 것을 의미함
    if length <= 0:
    	return "no answer"
    
    # 바꿔야 하는 문자열을 찾음
    second_len = len(str_list) - 1
    while str_list[second_len] <= str_list[length-1]:
    	second_len -= 1
    
    # 바꿔줌
    str_list[length-1], str_list[second_len] = str_list[second_len], str_list[length-1]
    
    # 그 뒤에있는 것들을 오름차순으로 새롭게 정렬함
    second_len = len(str_list) - 1
    while length < second_len:
    	str_list[length], str_list[second_len] = str_list[second_len], str_list[length]
        length += 1
        second_len -= 1
        
	return "".join(str_list)