백준 - 회문(Swift)

백준 - 회문(Swift)

 

 

 문제 설명

 

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

17609번: 회문

 

 

 

 나의 풀이

 

이 풀이로 예제의 테스트케이스를 검사하면 전부 맞다.

하지만 실제로 제출하면 처음부터 실패하는 걸 볼 수 있다..

 

이유는 역시 반례를 생각하지 않았기 때문이다.

이 문제는 양쪽이 같지않을때 왼쪽을 추출해서 진행하는 경우와 오른쪽을 추출해서 진행하는 경우 두 가지를 각각 탐색해줘야하는데,

아래 내 코드는 왼쪽이 추출된다면 왼쪽만 가고 오른쪽의 경우는 탐색하지 않게 된다.(오른쪽을 먼저 추출했어야 유사회문이었을 수도 있는데 말이다)

 

그래서 다른사람이 재귀를 이용한 것을 보고 문제를 해결해였다.

 

import Foundation
let n = Int(readLine()!)!
var results: [Int] = []
func checkRotate(_ array: [Character]) -> Int {
    var start = 0
    var end = array.count-1
    var cnt = 0
    while start < end {
        if cnt > 1 {
            return 2
        }
        if array[start] == array[end] {
            start += 1
            end -= 1
        } else if array[start+1] == array[end] {
            start += 1
            cnt += 1
        } else if array[start] == array[end-1] {
            end -= 1
            cnt += 1
        } else {
            return 2
        }
    }
    if cnt == 1 {
        return 1
    } else {
        return 0
    }
}

for _ in 0..<n {
    let input = Array(readLine()!.lowercased())
    results.append(checkRotate(input))
}

for x in results {
    print(x)
}

 

 

 다른 사람의 풀이

 

이 풀이의 핵심은 각각의 케이스를 if문을 통해 재귀로 돌아가면서 모든 경우를 탐색하는 것이다

 

그런데 "첫번째 if문에서(먼저 왼쪽을 추출했을때) 유사회문을 result에 담았는데 두번째 if문에서 유사회문이 아닌게 담겨질 수 있는 거 아닌가?" 라는 생각이 들 수 있다.

하지만 이는 문제가 한정적이기 때문에 생각을 좀 해보면 쉽게 처리할 수 있다.

 

일단 한번 값을 추출한 상태(왼쪽이든 오른쪽이든)는 유사회문인 상태이다. 그 상태에서 쭉 문제없이 각 문자가 같다면 유사회문인데, 문제가 있을때는 if cnt == 1 에서 걸리고 return이 되기 때문에 첫번째 if문에서의 유사회문을 etc로 바뀌는 경우가 존재하지 않는다.

 

enum PalinType: Int {
    case palin = 0
    case psuedo = 1
    case etc = 2
}

func isPalin(_ arr: [Character], _ s: Int, _ e: Int, _ cnt: Int) {
    if (s < e) {
        if arr[s] == arr[e] {
            isPalin(arr, s+1, e-1, cnt)
        } else {
            // 하나를 추출한 상태에서 또 양쪽이 같지않은 경우는 회문도 유사회문도 아닌 상태이다.
            if cnt == 1 {
                return
            }
            if arr[s+1] == arr[e] {
                isPalin(arr, s+1, e, cnt+1)
            }
            
            if arr[s] == arr[e-1] {
                isPalin(arr, s, e-1, cnt+1)   
            }
            
            if arr[s+1] != arr[e] && arr[s] != arr[e-1] {
                return
            } 
        }
    } else {
        // 실제로 cnt는 0, 1이외의 값이 올 수 없다. 왜냐하면 cnt가 1일떄 종료시켜버리기 떄문이다.
        switch cnt {
            case 0:
            result = .palin
            case 1:
            result = .psuedo
            default:
            result = .etc
        }
    }
}

let n = Int(readLine()!)!
var result: PalinType = .etc
for _ in 0..<n {
    let input = Array(readLine()!)
    isPalin(input, 0, input.count-1, 0)
    print(result.rawValue)
    result = .etc
}

 

 피드백

 

1. enum타입을 원시값을 이용해서 변수와 숫자 사이를 유동적으로 사용하자.

2. 모든 경우의 수를 탐색할 때는 재귀가 좋다.