[백준] 613 문자열 생성 (Javascript)

문제

BOJ6137_문자열 생성

풀이

문자열 S와 빈 문자열 T가 주어졌을 때, S의 맨 앞의 문자를 T문자열 뒤에 추가하거나, S의 맨 뒤 문자를 T문자열에 추가해서 사전 순으로 가장 빨리 오는 문자열 T를 만들어야 한다.

문자열 T를 사전 순으로 가장 빨리 오도록 만들려면, S의 맨 앞의 문자와 맨 뒷 문자를 비교하여 둘 중 사전 순으로 빠른 문자를 T문자열 뒤에 추가해주면 된다.

문자열 S의 맨 앞 문자(front)와 맨 뒷 문자(rear)를 비교할 때의 경우의 수는 3가지가 있다.

1. front 가 사전 순으로 더 빠른 경우
2. rear 가 사전 순으로 더 빠른 경우
3. front 와 rear 가 동일한 문자일 경우

여기서 핵심은 3번의 경우다.

예를 들어 S="BACB"일 경우 B(front)와 B(rear)가 같다. 이때는 그 다음 문자들(front+1, rear-1)끼리 비교가 필요하다. A(front-1) 와 C(rear-1) 중에서는 A가 사전 순으로 더 빠르다. 그러므로 A쪽 B(front) 를 T에 추가해주어야 한다. 그럼 아래와 같은 순서로 T가 만들어 진다.

1. S="BACB" / T=""
2. S="ACB" / T="B"
3. S="CB" / T="BA"
4. S="C" / T="BAB"
5. S="" / T="BABC"

만약 반대로 rear 쪽 B를 골랐다면 아래와 같이 바뀌어 올바른 답이 나오지 않았을 것이다.

1. S="BACB" / T=""
2. S="BAC" / T="B"
3. S="AC" / T="BB"
4. S="C" / T="BBA"
5. S="" / T="BBAC"

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const N = +input[0];
const string = input.slice(1);
let t = '';
let front = 0;
let rear = N - 1;
for (let i = 0; i < N; i++) {
    // 80번째마다 개행 문자 추가
    if (i % 80 === 0) t += '\n';
    if (string[front] < string[rear]) t += string[front++];
    else if (string[front] > string[rear]) t += string[rear--];
    // 두 문자가 같을 경우 안쪽 front+1, rear-1 문자 비교
    else {
        let innerFront = front + 1;
        let innerRear = rear - 1;
        let isChanged = false;
        while (innerFront <= innerRear) {
            if (string[innerFront] < string[innerRear]) {
                t += string[front++];
                isChanged = true;
                break;
            } else if (string[innerFront] > string[innerRear]) {
                t += string[rear--];
                isChanged = true;
                break;
            } else {
                innerFront++;
                innerRear--;
            }
        }
        // 대칭이라면 어느 문자를 넣어주던 상관 없음
        if (!isChanged) t += string[front++];
    }
}
console.log(t.trimStart());