baekjoon 9081: 단어 맞추기

https://www.acmicpc.net/problem/9081

9081번: 단어 맞추기

---

1. 초기구현형태.

 

permutatioins라는 내장함수 를 사용하여 모든 경우를 sort한 뒤, 그중 제시어 다음에 나오는 단어를 고르게 하였다.

from itertools import permutations
n = int(input())
for _ in range(n):
    arr = input()
    a = [''.join(p) for p in permutations(arr)] # 문자열을 하나의 글자씩 뜯어서 모든 경우의 단어를 만듬!
    a = set(a)
    a = list(a)
    a.sort()


    for i in range(len(a)):
        if a[i] == arr:
            if i == len(a)-1:
                print(a[i])
                break
            else:
                print(a[i+1])
                break

하지만 단어가 100글자인 경우 경우의 수가 너무 많아서 a라는 list에 삽입과정에 메모리초과가 나버림ㅠㅠ

 

그래서 구현한 방법이 이방법

n = int(input())
for _ in range(n):
    arr = list(input())
    lst = []
    result = []
    cnt = 0

    for i in range(len(arr)-1,0,-1): #뒷글자부터 확인
        if ord(arr[i]) > ord(arr[i-1]): # 이전의 글자가 더 크다면 여기서부터 시작
            cnt+=1 # 단어의 다음 단어가 없을 경우를 위해 count를 넣어줌

            for j in range(0,i-1):
                result.append(arr[j])

            for j in range(i-1,len(arr)):
                lst.append(arr[j])

            lst.sort()
            for j in range(len(lst)):
                if lst[j] > arr[i-1]:
                    result.append(lst[j])
                    lst.remove(lst[j])
                    result= result + lst
                    break
            break
    if cnt ==0: # 현재 단어의 다음단어가 없을시!
        result = arr

    for i in range(len(result)):
        print(result[i],end='')
    print()

코드에 대한 알고리즘은 다른분의 블로그를 보고 구현하였는데 완전 잘 정리해두셔서 이보다 설명 잘 할 수 없음

---

출처:

https://nahwasa.com/entry/%EB%B0%B1%EC%A4%80-9081-%EC%9E%90%EB%B0%94-%EB%8B%A8%EC%96%B4-%EB%A7%9E%EC%B6%94%EA%B8%B0-BOJ-9081-JAVA

백준 9081 자바 - 단어 맞추기 (BOJ 9081 JAVA)