[boj] 16719 ZOAC

문제

[boj] 16719 ZOAC

---

풀이

예제 3번 STARTLINK를 보면

0	1	2	3	4	5	6	7	8
S	T	A	R	T	L	I	N	K

A → I → K → N → L → R → T → S → T
2 → 6 → 8 → 7 → 5 → 3 → 4 → 0 → 1

• 배열 중 가장 빠른 문자를 선택
• 선택한 문자 이후에서 가장 빠른 문자 선택을 반복
• 끝까지 간 다음에는 가장 빠른 문자열 앞쪽에서 또 선택한다
• 앞쪽에서 선택을 반복

재귀로 해결한다.
어려웠음...

---

코드

javascript

// boj 16719 ZOAC
// recursion

const input = require("fs").readFileSync("./example.txt").toString().split("\n");
// const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const arr = input[0].split("");
let check = Array(arr.length).fill(0);
let result = "";

function recursion(left, right) {
  if (left > right) return;

  let idx = left;
  for (let i = left; i <= right; i++) {
    if (arr[idx] > arr[i]) idx = i;
  }
  check[idx] = 1;

  for (let i = 0; i < arr.length; i++) {
    if (check[i] === 1) result += arr[i];
  }
  result += "\n";

  recursion(idx + 1, right); //오른쪽
  recursion(left, idx - 1); //왼쪽
}
recursion(0, arr.length - 1);
console.log(result);