문제 내용
어떤 단어를 뒤에서부터 읽어도 똑같다면 그 단어를 팰린드롬이라고 한다. 'radar', 'sees'는 팰린드롬이다.
수도 팰린드롬으로 취급할 수 있다. 수의 숫자들을 뒤에서부터 읽어도 같다면 그 수는 팰린드롬 수다. 121, 12421 등은 팰린드롬수다. 123, 1231은 뒤에서부터 읽으면 다르므로 팰린드롬수가 아니다. 또한 10도 팰린드롬수가 아닌데, 앞에 무의미한 0이 올 수 있다면 010이 되어 팰린드롬 수로 취급할 수도 있지만, 특별히 이번 문제에서는 무의미한 0이 앞에 올 수 없다고 하자.
입출력
1. 입력
입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다.
2. 출력
각 줄마다 주어진 수가 팰린드롬 수면 'yes', 아니면 'no'를 출력한다.
예제
- 입력 - - 출력 -
121 yes
1231 no
12421 yes
0
풀이
제일 처음에 생각했던 풀이는 스택을 사용하는 것이었다.
길이를 절반으로 나눠서 절반 이전을 스택에 저장하고 비교하는 방식을 구현했다.
TODO 팰린 드롬수를 구분하자
- 입력받은 문자열의 길이를 절반으로 나누어 스택에 저장
- 스택에서 팝 했을 때 다를 경우 false로 루프를 탈출
- 문자열의 길이가 홀수일 경우 정 가운데수는 뛰어넘고 짝수일 경우 그냥 진행
- 결과가 true 일경우 YES, false일 경우 NO를 출력
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
char[] palin = {}; //팰린드롬수 저장할 캐릭터 배열
Stack<Character> palinStack = new Stack<>(); //비교할 수를 저장할 스택
Boolean result;
String resultText = "";
while (true) {
result=true;
palin = buf.readLine().toCharArray(); //펠린드롬수 입력
if(palin[0] == '0') //0이 입력될 경우 중단
break;
for (int i = 0; i < palin.length; i++) {
//절반 이전일 시
if (i < palin.length / 2) {
palinStack.push(palin[i]); //push
}
//길이가 홀수일경우
if (palin.length % 2 != 0) {
if (i > palin.length / 2) { //절반 +1부터 비교
if (palinStack.pop() != palin[i]) { //팰린드롬수 비교
result = false;
}
}
}
//길이가 짝수일경우
else if (palin.length % 2 == 0) {
//절반 이후일 시
if (i >= (palin.length / 2)) { //절반 이후부터 비교
if (palinStack.pop() != palin[i]) {
result = false;
}
}
}
}
if(result)
resultText="yes";
else
resultText="no";
System.out.println(resultText);
}
buf.close();
}
}
... 슬프게도 오답
다시 생각하고 겸사겸사 코드 길이도 줄여볼 겸 StringBuffer클래스의 reverse메서드를 이용해서 구현해봤다.
TODO 팰린 드롬수를 구분하자 출력방식을
- 입력받아서 StringBuffer에
- reverse후 원본과 비교
- 같으면 YES 다르면 NO
코드도 훨씬 간략해지고 보기 편해서 좋았는데 오답?... 왜? 카페인에 찌들어서 잘 굴러가지 않는 머리를 굴려봤는데
아무리 생각해도 알고리즘은 문제가 없단 말이지...
한참 생각을 해본 결과
예제에 문제가 있구나 -> 입력 예제의 0 뒤에 개행 문자가 없어! -> BufferedReader나 Scanner의 nextLine() 메서드는 개행 문자를 기준으로 문자를 읽어오는데 못 읽으니까 오답이네
라는 결과가 도출됐다.
당연하지만 이 결과는 틀렸답니다😂
그래서 공백 기준으로 읽는 Scanner클래스의 next() 메서드를 썼고 마침내!!!! 또 틀렸다.
이유는 '문제의 출력'과 내가 써놓은 todo의 '출력'을 보면 알 수 있는데 문제의 출력은 소문자이고 내가 적어놓은 출력은 대문자다
비흡연자지만 이 순간만큼은 담배가 생각났습니다🚑
출력 부분 수정하니까 위 알고리즘과 아래 알고리즘 모두 통과됐다.
import java.io.IOException;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String palin, reversePalin;
while (true) {
/*입력값 0에 공백문자가 포함되어있지 않기 때문에 BufferedReader()와 nextLine()을 쓰면
입력대기상대로 진행되지 않기 때문에 공백문자 기준으로 읽는 next()메서드를 사용*/
palin = scan.next();
if (palin.equals("0")) //0일경우 정지
break;
StringBuffer strBuf = new StringBuffer(); //스트링 버퍼 생성
strBuf.append(palin); //버퍼에 저장
strBuf.reverse(); //역순으로 재정렬
reversePalin = strBuf.toString(); //재정렬된 문자열 출력
if(palin.equals(reversePalin)) //역순과 비교
System.out.println("yes");
else
System.out.println("no");
}
scan.close();
}
}
개선할 점
어떤 출력을 해야 되는지 처음부터 제대로 읽을걸....
코드 간결성은 StringBuffer가 더 좋았지만 메모리 사용에 있어선 스택이 더 좋았다. 메모리와 속도를 잡고 싶으면 스택이나 다른 자료구조를 쓰는 것이 아닌 입력된 문자열 절반(소수점 이하 반올림)까지 비교하는 반복문 안에서 charAt로 처음과 마지막 문자를 비교, 다르면 'no'를 출력시키고 맞으면 마지막에 yes를 출력시키는 알고리즘이 더 나았을 거라 생각한다.
kotlin code
- 스택
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() {
val buf = BufferedReader(InputStreamReader(System.`in`))
var palin: CharArray //팰린드롬수 저장할 캐릭터 배열
val palinStack = Stack<Char>() //비교할 수를 저장할 스택
var result: Boolean
var resultText: String
while (true) {
result = true
palin = buf.readLine().toCharArray() //펠린드롬수 입력
if (palin[0] == '0') //0이 입력될 경우 중단
break
for (i in palin.indices) {
//절반 이전일 시
if (i < palin.size / 2) {
palinStack.push(palin[i]) //push
}
//길이가 홀수일경우
if (palin.size % 2 != 0) {
if (i > palin.size / 2) { //절반 +1부터 비교
if (palinStack.pop() != palin[i]) { //팰린드롬수 비교
result = false
}
}
} else if (palin.size % 2 == 0) {
//절반 이후일 시
if (i >= palin.size / 2) { //절반 이후부터 비교
if (palinStack.pop() != palin[i]) {
result = false
}
}
}
}
resultText = if (result) "yes" else "no"
println(resultText)
}
buf.close()
}
2. StringBuffer
import java.util.*
fun main() {
val scan = Scanner(System.`in`)
var palin: String
var reversePalin: String
while (true) {
/*입력값 0에 공백문자가 포함되어있지 않기 때문에 BufferedReader()와 nextLine()을 쓰면
입력대기상대로 진행되지 않기 때문에 공백문자 기준으로 읽는 next()메서드를 사용*/
palin = scan.next()
if (palin == "0") //0일경우 정지
break
val strBuf = StringBuffer() //스트링 버퍼 생성
strBuf.append(palin) //버퍼에 저장
strBuf.reverse() //역순으로 재정렬
reversePalin = strBuf.toString() //재정렬된 문자열 출력
if (palin == reversePalin) //역순과 비교
println("yes") else println("no")
}
scan.close()
}
3. 개선한 알고리즘
import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.floor
fun main() {
val buf = BufferedReader(InputStreamReader(System.`in`))
val sb = StringBuilder()
var inputText: String
while (true){
inputText = buf.readLine()
if (inputText == "0")
break
//절반까지 반복
for (i in 0..floor(inputText.length/2.0).toInt()){
//양끝이 다르면
if (inputText[i] != inputText[inputText.length-1-i]){
//no
sb.append("no\n")
break
}
//무사히 끝나면
if(i== floor(inputText.length/2.0).toInt())
//yes
sb.append("yes\n")
}
}
print(sb)
buf.close()
}
'코딩테스트 > 백준' 카테고리의 다른 글
1236 / 성지키기 (0) | 2022.06.13 |
---|---|
1193 / 분수찾기 (0) | 2022.06.13 |
1157번 / 단어공부 (0) | 2022.06.13 |
1145번 / 적어도 대부분의 배수 (0) | 2022.06.13 |
1032번 / 명령프롬포트 (0) | 2022.06.13 |