-
문제
https://www.acmicpc.net/problem/17609
17609번: 회문
각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.
www.acmicpc.net
문제를 이해했는가?
팰린드롬이면 0, 1개만 바꾸면 팰린드롬이 되면 1, 아예 안되면 2를 출력하라.
구현
1) 팰린드롬이 되려면 "짝수 + 뒤집어도 같아야함"
2) 유사 팰린드롬을 찾으려면 " 홀수 + 하나만 지우면 됨"
3) 아니라면 짝수와 홀 수 일 때 1,2의 조건에 해당 안되면
function solution(word) { word = word.split(""); let reversed = word.slice().reverse(); if (word.length % 2 === 0) { // 뒤집었을 때 같으면 팰린드롬 if (word.join("") === reversed.join("")) { return 0; } else { return 2; } } else { let word_typo = ""; let reversed_typo = ""; for (let i = 0; i < word.length; i++) { // 1개만 달라야 하기 때문에, 찾은 시점에 멈춰야함. if (word[i] !== reversed[i]) { word_typo = word[i]; reversed_typo = reversed[i]; break; } } // 문자가 다른 경우, 어떤 문자를 삭제 해야 하는지 모름 // 그래서 위의 문자를 삭제 하는경우와 const word_typo_of_word = word.indexOf(word_typo); const word_typo_of_reve = reversed.indexOf(word_typo); // 아래 문자를 삭제 하는 경우로 나눠서 const reversed_typo_of_word = word.indexOf(reversed_typo); const reversed_typo_of_reve = reversed.indexOf(reversed_typo); // 두개 중 하나에 해당되면 유사 팰린드롬 if ( word.splice(word_typo_of_word, 1).join("") === reversed.splice(word_typo_of_reve, 1).join("") || word.splice(reversed_typo_of_word, 1).join("") === reversed.splice(reversed_typo_of_reve, 1).join("") ) { return 1; } else { // 아니면 2출력 return 2; } } }
투포인터
function checkSimilar(word, left, right) { while (left < right) { if (word[left] === word[right]) { left += 1; right -= 1; } else { return false; } return true; } } function solution(word) { // 투포인터를 만들어서 좁혀가면서 비교를 한다. let left = 0; let right = word.length - 1; while (left < right) { if (word[left] === word[right]) { left += 1; right -= 1; } else { //3) 다른 값을 만나면, 좌측 포인터를 오른쪽으로 밀었을 때 //또는 오른쪽 포인트를 좌측으로 밀었을 때 하나의 경우라도 True라면 유사 팰린드롬. if ( checkSimilar(word, left + 1, right) || checkSimilar(word, left, right - 1) ) { return 1; } // 모두 해당 안되면 2 출력. return 2; } } // 다른 값이 없다면, 팰린드롬인 0을 출력 return 0; }
'PS > 백준' 카테고리의 다른 글
[백준_14247] 나무 자르기 ( 그리디 - 자바스크립트 ) (0) 2021.06.30 [ 백준_11256 ] 사탕 ( 그리디 - 자바스크립트 ) (0) 2021.06.29 [ 백준 - 19941 ] 햄버거 분배 ( 그리디 - 자바스크립트 ) (0) 2021.06.29 [ 백준_6987 ] 월드컵 ( 구현 - 자바스크립트 ) (0) 2021.06.28 [백준_1268] 임시 반장 정하기 ( 구현 - 자바스크립트 ) (0) 2021.06.28 댓글