[백준] 16719 ZOAC JavaScript

혅·2025년 3월 14일

JavaScript

백준, 프로그래머스 -JavaScript-

목록 보기

208/215

문제

2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다.

앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로운 규칙을 고안해냈다!

규칙은 이러하다. 아직 보여주지 않은 문자 중 추가했을 때의 문자열이 사전 순으로 가장 앞에 오도록 하는 문자를 보여주는 것이다.

예를 들어 ZOAC를 보여주고 싶다면, A → AC → OAC → ZOAC 순으로 보여주면 된다.

바쁜 성우를 위하여 이 규칙대로 출력해주는 프로그램을 작성하시오.

입력

첫 번째 줄에 알파벳 대문자로 구성된 문자열이 주어진다. 문자열의 길이는 최대 100자이다.

출력

규칙에 맞게 순서대로 문자열을 출력한다.

예제 입력

ZOAC

예제 출력

A
AC
OAC
ZOAC

내가 했던 풀이 방법

이 문제에서는 3가지 정도의 케이스를 생각해야 한다.

한 번 만든 result에 뒤에 붙는 게 아니라 원래 문자열의 위치를 기준으로 한다. 하지만, 그 문자들이 연속적으로 올 필요는 없다. 예를 들어, ZOAC에서 A다음 OA나 AC가 올 수도 있지만, ZA가 와도 무관하다는거다. (물론 사전순으로 해도 올 수 없는 경우지만)

중간에 A와 같이 사전순으로 빠른 문자열이 온다면, 그 다음으로 빠른 문자열은 *A가 아니라 A*일 것이다. 즉, A의 위치의 오른쪽에서 사전순으로 빠른 문자열을 찾아야 한다. 그게 없다면, 이제 왼쪽을 체크해야 한다. 당연한게 A의 왼쪽과 오른쪽에 둘 다 B가 있다면 BA보다 AB가 빠르기 때문이다.

예제에는 없었지만 같은 문자가 n번 이상 나올 수 있음을 체크해야 한다. 즉, A~Z까지 순차적으로 찾는 건 무의미하다는 것.

used 배열을 str 길이만큼으로 초기화하고 false로 채워준다.
DFS를 0부터 str 길이만큼 호출한다. 이는 str 전체를 체크하겠다는 의미가 된다. 즉, 시작지점부터 끝지점을 DFS에 전달한다.
left와 right가 같으면 진행할 필요가 없으므로 return 한다.
left와 right 길이만큼 slice를 하고 사전순으로 정렬한다음 가장 빠른 문자열을 minStr에 저장한다. 이후 잘라낸 문자열에서 minStr의 위치를 찾는다. 이때, 해당 indx는 잘린 문자열이므로 실제 위치는 left를 더해주어야 한다.
찾아낸 위치를 사용처리 (used를 true) 해준다.
빈 문자열을 선언하고 문자열을 돌면서 used가 true인 문자들을 더해준다음 answer에 push 해준다. 이를 통해 answer에는 문제에서 요구하는 바가 저장되게 된다.
다음으로 빠른 문자열은 minIdx의 오른쪽에서 찾아야 한다. 즉, minIdx+1부터 right까지를 진행한 뒤에, 해당 DFS가 끝나면 left부터 minIdx를 진행하면 된다.
모든 DFS가 끝난 뒤에 answer를 출력한다.

코드

var fs = require('fs');
let str = fs.readFileSync(0, 'utf-8').toString().trim();

str = str.split('');
let used = Array.from({ length: str.length }, () => false);
let answer = [];

function DFS(left, right) {
  if (left === right) return;

  let minStr = str.slice(left, right).sort()[0];
  let minIdx = str.slice(left, right).indexOf(minStr) + left;
  used[minIdx] = true;

  let result = '';
  for (let i = 0; i < str.length; i++) {
    if (used[i]) result += str[i];
  }
  answer.push(result);

  DFS(minIdx + 1, right);
  DFS(left, minIdx);
}

DFS(0, str.length);

console.log(answer.join('\n'));