BOJ 1464 - 뒤집기 3

문제

BOJ 1464 - 뒤집기 3

문자열이 주어질 때, 원하는 만큼 접두사 뒤집기 연산을 수행하여 사전순으로 가장 작은 문자열을 만들어라.

입력

첫째 줄에 알파벳 소문자로 이루어진 문자열이 주어진다 (길이 1 이상 1000 이하).

출력

만들 수 있는 사전순 가장 작은 문자열을 출력한다.

예제

풀이

문자를 하나씩 추가하면서, 새 문자가 현재 결과의 마지막 문자보다 크면 앞에 붙이고, 아니면 뒤에 붙인다. 최종적으로 전체를 뒤집으면 사전순 최소가 된다.

1. 결과 문자열 s1을 첫 번째 문자로 초기화한다
2. 다음 문자가 s1의 마지막 문자보다 크면 앞에 붙이고, 작거나 같으면 뒤에 붙인다
3. 모든 문자를 처리한 후 전체 문자열을 뒤집어 반환한다

핵심 아이디어: 접두사 뒤집기는 결과적으로 각 문자를 앞 또는 뒤에 배치하는 것과 동일하며, 그리디하게 비교하여 배치하면 사전순 최소를 만들 수 있다.

코드

const solution = (input) => {
  let s = input[0].split("");
  let s1 = s[0];
  for (i = 1; i < s.length; i++) {
    if (s1[i - 1] < s[i]) { s1 = s[i] + s1; continue; }
    s1 = s1 + s[i];
  }
  return s1.split("").reverse().join("");
};
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
console.log(solution(input));

복잡도

• 시간: O(N)
• 공간: O(N)