알고리즘 문제 풀기

백준 1213: 팰린드롬 만들기 - javascript(구현)

Fo_rdang 2024. 2. 12. 21:45
반응형

문제 출처 

https://www.acmicpc.net/problem/1213

 

1213번: 팰린드롬 만들기

첫째 줄에 문제의 정답을 출력한다. 만약 불가능할 때는 "I'm Sorry Hansoo"를 출력한다. 정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력한다.

www.acmicpc.net

문제

임한수와 임문빈은 서로 사랑하는 사이이다.

임한수는 세상에서 팰린드롬인 문자열을 너무 좋아하기 때문에, 둘의 백일을 기념해서 임문빈은 팰린드롬을 선물해주려고 한다.

임문빈은 임한수의 영어 이름으로 팰린드롬을 만들려고 하는데, 임한수의 영어 이름의 알파벳 순서를 적절히 바꿔서 팰린드롬을 만들려고 한다.

임문빈을 도와 임한수의 영어 이름을 팰린드롬으로 바꾸는 프로그램을 작성하시오.

입력

첫째 줄에 임한수의 영어 이름이 있다. 알파벳 대문자로만 된 최대 50글자이다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 불가능할 때는 "I'm Sorry Hansoo"를 출력한다. 정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력한다.

예제 입력 1 복사

AABB

예제 출력 1 복사

ABBA

예제 입력 2 복사

AAABB

예제 출력 2 복사

ABABA

예제 입력 3 복사

ABACABA

예제 출력 3 복사

AABCBAA

예제 입력 4 복사

ABCD

예제 출력 4 복사

I'm Sorry Hansoo
 

문제 풀이 힌트 

  • 팰린드롬(palindrome) 또는 회문은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열 등을 말한다.
  • 먼저 정답이 여러개일 경우, 사전순으로 출력해야 하니까 주어진 문자열을 배열로 만든 후 , sort() 로 정렬해준다. //['A','A','A','B','B']
  • ['A','A','A','B','B'] 를 'ABABA' 로 출력해야 한다. 'ABABA' 를 머리, 몸통, 꼬리로 나눠서 보자. 
  • 머리는 'A,B' 몸통은 'A', 꼬리는 'BA'가 된다. 
  • 즉, 머리를 이용해서 reverse()를 하면 꼬리를 구할 수 있다. 
  • 즉, 몸통이 만약 2개 이상이 된다면 팰린드롬으로 만드는 것이 불가능하다 ! (ABCD 인경우 몸통은 4가 된다. 몸통이라는건 짝이 없다는 뜻이고, 짝이 없는건 하나이어야만 한다 !!!!)

문제 풀이 코드 

const input= require('fs').readFileSync('/dev/stdin').toString().trim(); 
const arr = input.split('').sort(); //주어진 문자열을 비열로 만든 후, 사전순으로 정렬한다. 
const [head, body] = [[],[]]; 
while(arr.length){ //arr에 모든 요소가 없어지기 전까지 
      let letter = arr.shift(); //맨 앞 부분 요소 빼기 
      let letterIdx = arr.indexOf(letter); //letter가 짝이 있는지 확인한다. 
    if(letterIdx === -1) body.push(letter); //letter가 짝이 없다면? 몸통이 된다. 
    else{ //짝이 있다면?
        head.push(letter); //head에 해당 요소를 넣어준다. 
        arr.splice(letterIdx, 1); //arr에서 나머지 짝을 제거해준다. 
    }
   }
const tail = [...head].reverse().join(''); //head를 복사한후(그래야 밑에서 head를 이용할 수 있음) 거꾸로 순서를 바꾸고, 문자열로 바꾼다. 
if(body.length >1) console.log("I'm Sorry Hansoo"); //몸통이 여러개가 되면 불가능 ! 
else console.log(head.join('') + body.join('') + tail);//head와 body, tail을 합친다.

Only 문제 풀이 

const input= require('fs').readFileSync('/dev/stdin').toString().trim(); 
const arr = input.split('').sort(); 
const [head, body] = [[],[]]; 
while(arr.length){
      let letter = arr.shift(); 
      let letterIdx = arr.indexOf(letter); 
    if(letterIdx === -1) body.push(letter); 
    else{
        head.push(letter);
        arr.splice(letterIdx, 1); 
    }
   }
const tail = [...head].reverse().join(''); 
if(body.length >1) console.log("I'm Sorry Hansoo"); 
else console.log(head.join('') + body.join('') + tail);
반응형