[JS][백준]6137_문자열 생성

문제 번호

6137번: 문자열 생성

 

 

 

알고리즘 분류

• 문자열
• 그리디 알고리즘
• 두 포인터

 

문제 풀이

 투 포인터와 그리디 알고리즘을 사용한다. 주어진 문자열 S의 양끝에 포인터를 둔다. 

head는 문자열의 시작 부분, tail은 문자열의 끝부분으로 지정한다.

  let head = 0;
  let tail = s.length - 1;

 

 이제 head와 tail을 인덱스로 사용하여 S[head]와 S[tail]중 사전 순으로 봤을 때, 먼저 오는 문자를 T에 추가한다. 만약 head와 tail이 가리키는 문자가 동일하다면 head와 tail을 중앙 쪽으로 이동시킨다. 그래서 사전 순으로 더 먼저 오는 문자가 발견되는 쪽의 문자를 사용한다.

 ACBCCA 라고 한다면 처음에 head와 tail모두 'A'를 가리키므로 사전 순으로 동일하다. 그럼 head와  tail을 모두 중앙 쪽으로 옮긴다. 그럼 head와 tail은 모두 'C'를 가리키게 된다. 그래서 다시 한번 head와 tail을 중앙 쪽으로 이동한다. 그럼 head는 'B'를 가리키게 되고 tail은 'C'를 가리키게 된다. head 쪽의 문자가 사전 순으로 더 앞서 있으므로 head가 가리키는 문자인 젤 앞의'A'를 T에 추가한다.

// 두개의 문자가 같다면.
    while (s[head] === s[tail]) {
      head++;
      tail--;
      if(head >= tail) 
        break;
    }

    // 사전순으로 빠른 문자부터 push 한다.
    if (s[head] < s[tail]) {
      T.push(s.shift());
    } else {
      T.push(s.pop());
    }
    head = 0;
    tail = s.length - 1;

 이때 head가 tail을 넘어가는 경우를 주의하자. => CCC // CCCC 같은 문자열이 주어지는 경우를 생각해보자.

 

마지막으로 주어진 문자열 S에서 1개를 제외하고 모든 문자를 T에 추가했을때의 경우를 생각해준다.

    if (head === tail) { // 마지막 1개의 문자가 남았을때.
      T.push(s[head]);
      break;
    }

 

 문제에서 80개의 문자마다 새줄문자를 출력하라 했으니 조건에 맞추어서 출력해주면 된다.

  // 정답 출력.
  for (let i = 0; i < T.length; i++) {
    if (i % 80 === 0) {
      answer += '\n';
    }
    answer += T[i];
  }

 

전체 코드

const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');

function sol(s) {
  let answer = '';

  let T = [];

  let head = 0;
  let tail = s.length - 1;

  // 최대 2000 글자. 2000 * 2000. 4 10^6.
  while (head <= tail) {

    // 두개의 문자가 같다면.
    while (s[head] === s[tail]) {
      head++;
      tail--;
      if(head >= tail) 
        break;
    }

    // 사전순으로 빠른 문자부터 push 한다.
    if (s[head] < s[tail]) {
      T.push(s.shift());
    } else {
      T.push(s.pop());
    }
    head = 0;
    tail = s.length - 1;

    if (head === tail) { // 마지막 1개의 문자가 남았을때.
      T.push(s[head]);
      break;
    }
  }

  // 정답 출력.
  for (let i = 0; i < T.length; i++) {
    if (i % 80 === 0) {
      answer += '\n';
    }
    answer += T[i];
  }

  console.log(answer.trim());
}
function main() {
  let s = input.slice(1).map(_ => _.trim());
  sol(s);
}
main();

특이사항

 shift()를 여러 번 수행해서 시간 초과가 날 수 도 있다고 생각하였으나 입력의 크기를 고려했을때 시간초과가 나지 않을 것이라고 판단했다. 

 첫 시도 때 head가 tail을 넘어가는 경우를 고려하지 않아서 메모리 초과가 났었다.