문제 풀이
분할 정복
fold(s, length) = 접힌 흔적이 문자열 s로 주어졌을 때 length 길이만큼 확인해 반으로 접기만 해서 낼 수 있는 흔적인지 검사하는 함수
idx = 현재 검사하는 뒤집히지 않은 접힌 자국의 인덱스
oppositeIdx = 현재 검사하는 접힌 자국과 맞닿는 반대쪽 접힌 자국의 인덱스
canFold = 현재 반으로 접으면 뒤집히는 접힌 자국이 정확히 포개지는지 여부
종이를 반으로 접기만 하므로 반으로 접혔을 때 맞닿는 접힌 흔적이 포개어져야 반으로 접기만 해서 만들 수 있는 흔적임
더이상 접힌 자국이 남지 않도록 접을 수 있어야 반으로 접기만 해서 접을 수 있는 것이므로 분할 정복을 적용한 재귀 함수로 검사해야 함
현재 접힌 자국이 문자열 s로 들어온다면 정 가운데의 접힌 자국에 따라 종이를 접어야 하므로 이 인덱스를 기준으로 앞 뒤가 접혔을 때 포개어지는지 확인하기 위해서 확인할 인덱스를 idx로 정의함
idx를 0부터 현재 길이의 절반까지 반복하면 접힌 자국의 앞쪽 절반까지 확인할 수 있고 현재 접으면 포개어지는 인덱스가 length - idx - 1이 되므로 이를 oppositeIdx로 초기화함
그 이후에 각 인덱스의 문자가 서로 같다면 정확히 포개어지지 않는 것이므로 canFold에 false를 대입하고 반복문을 탈출함
만약 모든 인덱스를 확인했을 때 canFold가 true라면 현재 단계에서 반으로 접었을 때 접힌 자국이 정확히 포개어지는 것이므로 다시 반으로 접었을때도 포개어지는지 확인하기 위해 fold(s, length / 2)를 재귀 호출한 것을 반환함
false라면 이미 반으로 접는 것으로는 접힌 자국대로 접을 수 없다는 것이 밝혀졌으므로 false를 반환하면 됨
fold(s, length)를 이렇게 구현했으면 이 함수를 이용해서 입력으로 들어오는 접힌 자국이 반으로 접을 수 있는지 판단해 true를 반환하면 YES, false를 반환하면 NO를 출력하면 정답
풀이 설명
종이를 접었다가 핀 종이를 보고 반으로 접기만 해서 그대로 접을 수 있는지를 찾는 문제이다.
종이를 접은 흔적이 이미 있기 때문에 그 흔적을 따라 종이를 반으로 접는다고 생각해보면 반으로 접었을 때 맞닿는 접은 흔적이 정확하게 포개어져야 그 다음도 방향에 맞게 종이를 접을 수 있을 것이다.
반으로 접으면 뒤쪽 절반이 안쪽으로 접히든 바깥쪽으로 접히든 똑같히 뒤집히기 때문에 뒤쪽 절반을 뒤집어서 앞쪽 절반과 비교해야 한다. 뒤쪽 절반을 따로 뒤집어서 만들어 비교하는 것 보다 인덱스를 이용해 앞에서부터 하나씩과 뒤에서부터 하나씩을 비교하는 것이 더 효율적이다.
그리고 절반을 접을 때마다 접힌 자국이 절반으로 나뉘고 이를 더 이상 접힌 자국이 남지 않도록 접어야 하므로 분할 정복을 적용한 재귀 함수를 이용해 풀면 된다.
이때 재귀 함수의 인수로 접힌 자국이 저장된 문자열 s와, 현재 접힌 자국을 검사해야 하는 범위 length가 필요하다. length를 인수로 주는 이유는 반으로 접은 이후에 남은 접힌 자국의 범위를 넘겨야 하기 때문이다.
그러므로 문자열 s에서 현재 검사해야 하는 length까지 중앙의 인덱스 length / 2를 중심으로 대칭되는 인덱스마다 문자가 서로 다른지 검사하고 재귀적으로 더 이상 접힌 자국이 남지 않을때까지 검사하는 재귀 함수 fold(s, length)를 정의한다.
이렇게 정의된 재귀 함수를 이용해 입력받는 접힌 자국에 따라 함수가 true를 반환하면 반으로 접어서 접힌 자국대로 종이를 접을 수 있는 것이므로 YES를 출력, false를 반환하면 반으로 접어서 접힌 자국대로 종이를 접을 수 없는 것이므로 NO를 출력하면 정답이 된다.
소스 코드
fun main() = System.`in`.bufferedReader().run {
val T = readLine().toInt()
fun fold(s: String, length: Int): Boolean{
if(length == 1){
return true
}
var idx = 0
var canFold = true
while(idx < length / 2 && canFold){
val oppositeIdx = length - idx - 1
if(s[idx] == '0' && s[oppositeIdx] == '0'){
canFold = false
}
if(s[idx] == '1' && s[oppositeIdx] == '1'){
canFold = false
}
idx++
}
if(canFold){
return fold(s, length / 2)
} else {
return false
}
}
val sb = StringBuilder()
repeat(T){
val s = readLine()
sb.append(if(fold(s, s.length)) "YES" else "NO").append("\n")
}
print(sb)
}