Algorithm/백준

백준 - 17609 swift

yanni13 2024. 5. 26. 01:00

 

 

 

 

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

 

 

 

 

문제는 위와 같다. 

비슷한 회문만 구하는 문제가 브론즈3이였나 그래서 비슷한데 골드 5? 금방 풀겠지 했는데 

음... 아니였다

 

회문 구하는 건 쉬운데, 유사회문 구하는게 엄청 어렵다!!!!!

아이디어 조차 어떻게 접근해야할 지 아예 모르겠음

 

접근 시도

입력된 문자열이랑, 뒤집은 문자열을 비교하면서 다른 숫자가 있는 걸 찾아낸다. -> 어떻게 비교할껀데...

예시가 xabba 일 경우 뒤집었을 때 abbax 인데 순서대로 비교한다 해도 각 자리수 비교 문자열이 다르기 때문에 안됨

 

x a b b a
a b b a x

 

c o m w w t m o c
c o m t w w m o c

 

 

그래서 표로 만들어보고 확인했을때, 입력받은 문자열이랑, 뒤집은 문자열이랑 가운데 문자열이 동일한걸 발견했다!

그래서 가운데를 기준으로 제일 왼쪽부터 , 제일 오른쪽부터 동시에 시작해서 가운데까지 갔을 때 다른 문자열을 뽑아내고, 그 다른 문자열이 같다면 유사회문이라고 판단하기!

 

예를 들어 comwwtmoc로 예시를 들 때, 표에서 첫번째 칸  c - c 비교 시작을 하면서 동시에 맨 마지막 칸인 c - c를 비교한다.

가운데인 w까지 이 과정을 반복했을 경우 네번째 칸인 w-t와 여섯번째 칸인 t-w가 다르다!

근데 문자열을 뒤집어서 보면 얘네는 동일함

그럼 w와 t 중에 문자를 가운데 문자와 동일하지 않는거를 삭제시킨다. -> 즉 t를 삭제

 

라고 생각을 하긴 했었는데 

xabba 는 뒤집은 문자열이랑 다 달라서; 삭제 시킬 후보 x,a,b 중 가운데 문자열 b를 제외하면 총 삭제 후보가 x랑 a 가되는데 이걸 어떻게 판단하지 라는 생각이 들었다.. ... ... 

 

설명이 너무 어려운거 같긴한데 흠 ..

 

 

처음에 작성한 코드

let testCase = Int(readLine()!)!

for _ in 0..<testCase {
    let input = readLine()!
    let reverseWord = String(input.reversed())
    if input == reverseWord { //회문
        print(0)
    } else if { //유사회문
    
    } else {
        print(2)
    }

}

 

아무튼 아이디어는 생각했어도 생각한 바 구현을 못하겠어서 회문만 구현했었던 초기 코드다.

 

 

 정답 코드

import Foundation

func isPalindrome(_ s: String) -> Bool {
    let chars = Array(s)
    var left = 0
    var right = chars.count - 1

    while left < right {
        if chars[left] != chars[right] {
            return false
        }
        left += 1
        right -= 1
    }
    return true
}

func isPseudoPalindrome(_ s: String) -> Bool {
    let chars = Array(s)
    var left = 0
    var right = chars.count - 1

    while left < right {
        if chars[left] != chars[right] {
            return isPalindrome(String(chars[left+1...right])) || isPalindrome(String(chars[left...right-1]))
        }
        left += 1
        right -= 1
    }
    return true
}

let n = Int(readLine()!)!
for _ in 0..<n {
    let s = readLine()!

    if isPalindrome(s) {
        print(0)
    } else if isPseudoPalindrome(s) {
        print(1)
    } else {
        print(2)
    }
}

 

회문  : 입력 받은 문자열을 배열로 바꾸고, 왼쪽/오른쪽 각각 포인터로 배열안에 문자가 같은지 확인한다. 같으면 true 틀리면 false 값을 주고 1씩 증가시켜 각 자리수의 문자열을 같은지 판단하고 bool 값으로 반환한다.

 

유사 회문 : left랑 right 변수를 두어, 서로 만나거나 교차하기 전까지 문자를 계속 비교한다. 비교한 문자열이 같지 않다면, left를 오른쪽으로 한칸 이동하여 right 위치까지 부분 문자열이 회문인지 검사한다. right도 마찬가지로 왼쪽으로 진행한다. left, right 둘 중 하나라도 회문이면 유사회문이라 판단한다.

 

 

 

 

 

 

코테 너~~무 어렵다 ㅠ...........ㅠ.....ㅠ.....

저작자표시