백준 - ZOAC

문제 출처:https://www.acmicpc.net/problem/16719

16719번: ZOAC

 

 

기존 문자열에서 하나씩 때어보면서 새로운 문자열을 만들고, 사전 순으로 정렬하는 방식으로 확인해야 한다.

 

ZOAC이라는 기존 문자열이 존재한다. 처음에는 알파벳 순으로 가장 빠른 문자를 뽑는다.

 그다음부터는,

 

1. 아직 사용하지 않은 문자들을 하나씩 붙여보면서(붙여지는 문자열의 무조건 뒤에 붙이는 것이 아니라 왼쪽이면 왼쪽, 오른쪽이면 오른쪽에붙여야 한다.)

 

2. 왼쪽, 오른쪽을 정하기 위해 String을 새로운 문자열로 사용하지 않고, 문자형 배열을 사용하여 기존 문자열의 인덱스를 가져와 String으로 변환시켰다.

 

이 말이 무엇이냐,

 

위의 사진처럼, 기존 문자열에서 새로운 문자열에 붙일 문자, 즉 인덱스를 찾으면, 새로운 문자열에 복사하는 방식이다.

현재 새로운 문자열이 A일 때,

ZO

OA

AC

이렇게 3개의 가능성이 있는 문자열이 있다. 각각을 서로 비교하며 AC가 가장 사전 순으로 앞선다는 것을 알게 되고 C의 인덱스인 3을 사용하여 새로운 문자열에 C를 붙이게 된다.

 

이어서 현재 문자열이 AC일 경우,

ZAC

OAC

이렇게 두 가지 경우가 존재한다. 두 경우를 비교했을 때 OAC가 앞선다는 것을 확인이 가능하므로 O의 인덱스를 가져와 새로운 문자열에 O를 붙이게 된다.

 

아래 코드가 그 과정을 담고 있다.