[백준/python] 9081번 단어 맞추기

1. 문제

 

이 문제는 어떤 단어가 주어지고 사전식 정렬을 하였을 때

그 바로 다음에 오는 단어를 찾는 문제이다.

2. 풀이

[접근 1]

처음에는 모든 사전식 배열을 다 늘어놓고

그 중에서 입력값을 찾은 뒤, 그 다음 값을 출력하는 방식을 생각했다.

 

1. 순열 라이브러리를 이용해 단어 조합을 모두 리스트에 넣는다.

2. 처음 입력한 단어의 인덱스를 찾는다.

3. 마지막 단어가 아닐 경우 다음 단어를 출력한다.

 

역시 코드 자체에 문제는 없었으나 결과가 시간 초과가 떠버렸다.

필요 없는 데이터까지 다 구해서일까...

바로 다음 순열을 어떻게 찾을지 긴 시간 고민했다.

 

[접근 2]

고민의 과정을 거쳐 뒤에서부터 숫자 크기를 비교하는 방식을 발견했다.

그 뒤 숫자 위치를 바꾸고 거꾸로 정렬하는 방식으로 문제를 해결할 수 있었다.

뒤의 일부 방법은 next_permutation 알고리즘을 참고하였다.

 

1. 뒤에서부터 숫자 크기를 비교하다가 작아지는 경우에 멈춘다.

2. 작아지기 전의 수를 i로 설정한다.

3. 뒤에서부터 i-1까지 다시 탐색하며 j 값이 더 큰 경우 두 수의 위치를 바꿔준다.

4. i부터 마지막 원소까지 뒤집은 결과를 리턴한다.

5. 문자를 합쳐서 단어 결과를 출력한다.

 

3. 코드

[접근 1]

#접근 1 - 시간초과
#순열 라이브러리
from itertools import permutations

n = int(input()) #반복횟수
for i in range(n):
    word = str(input()) #단어 입력 받기
    char = [i for i in word] #단어 구성 문자 분리
    perm = set(map(''.join, permutations(char))) #순열, 중복제거
    perm = list(perm) #리스트로 바꿔주기
    perm.sort() #사전순 정렬
    idx = perm.index(word) #입력 단어의 인덱스 찾기
    if len(perm) == idx+1: #마지막 단어인 경우 그대로 출력
        print(word)
    else: #입력 단어 다음 단어 출력
        print(perm[idx+1])

 

[접근 2]

#접근 2
def next(w):
    #왼쪽에 있는 수보다 오른쪽에 있는 수가 더 큰 경우 찾음
    for i in range(len(w)-1, 0, -1):
        if w[i-1] < w[i]:
            #오른쪽에서부터 idx 보다 큰 숫자인 경우를 찾음
            for j in range(len(w)-1, i-1, -1):
                #두 수의 위치를 바꿔주고 i부터 마지막까지 원소 뒤집기
                if w[i-1] < w[j]:
                    w[i-1], w[j] = w[j], w[i-1]
                    return (w[:i] + (w[i:][::-1]))
    return w #해당 안 되는 경우 그대로 출력(마지막 순서인 경우)

n = int(input()) #반복횟수
for i in range(n):
    word = list(input().strip()) #단어 입력 받기
    result = ''.join(next(word))
    print(result)

4. 결과

 

처음에 런타임 에러는 list(perm)에다가 바로 .sort()를 붙여서 생겼다.

시간 초과가 나지 않도록 더 적절한 방법을 고민하며 문제를 풀어야겠다.