글 읽기 - 틀린 이유를 모르겠습니다. 실마리 주시는 분 치킨쏴드리겠습니다ᅲᅲ

(追記) (追記ここまで)

틀린 이유를 모르겠습니다. 실마리 주시는 분 치킨쏴드리겠습니다ᅲᅲ

1893번 - 시저 암호

loy15091 4년 전 0

안녕하세요, 분명 맞게 짠 것 같은데 채점 50%에서 자꾸 틀립니다.

본문과 제가 만든 여러 테스트 케이스에 대해서 돌렸을 때는 의도한 결과가 나오는데,

어떤 반례가 있어서 틀리는지 모르겠습니다. (ACPC 2012 공개 된 테스트케이스를 찾아봐도 현 문제에 대한 테스트 데이터를 찾지 못했습니다.)

반례 찾는 것 좀 도와주시면 감사하겠습니다.

다음은 제 코드의 프로세스입니다.

1. 테스트 케이스 개수 입력 받기

2. a,w,s 입력받기

3. 0 to a-1 범위에 대한 쉬프트 문자열 구하기 (쉬프트 문자열을 구하기 위해 a 문자열에 대한 indexMap 생성) -> getShiftString()

3. shift 한 문자열에 대해서 KMP 알고리즘으로 암호문s에 쉬프트 문자열이 1번만 포함되는지 확인 -> containOnce()

4. 포함횟수에 따른 결과 출력 -> printResult()

package str.unsol
import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
private val br = BufferedReader(InputStreamReader(System.`in`))
private val bw = BufferedWriter(OutputStreamWriter(System.out))
fun main() {
 val n = br.readLine().toInt()
 for (i in 1..n)
 solve()
 flush()
}
private fun solve() {
 val sb = StringBuilder()
 var cnt = 0
 val a = br.readLine()!!
 val w = br.readLine()!!
 val s = br.readLine()!!
 if (w.length > s.length) {
 printResult(sb, 0)
 return
 }
 // 원본 문자열의 각 문자에 대한 인덱스 정보를 맵으로 관리하여, 쉬프트 시 활용
 val aIndexMap = HashMap<Char, Int>()
 for (i in a.indices) {
 aIndexMap[a[i]] = i
 }
 // 0~A-1 까지 쉬프트를 진행하고, 그 결과가 암호문에 1번 포함되는지 확인
 for (shift in a.indices) {
 val shiftedPattern = getShiftString(a, aIndexMap, w, shift)
// println("|| a=$a, w=$w, shift=$shift, pt=$shiftedPattern, s=$s")
 if (containOnce(s, shiftedPattern)) {
 if (cnt > 0) sb.append(" ")
 sb.append("$shift")
 cnt++
 }
 }
 // 결과 출력
 printResult(sb, cnt)
}
// 쉬프트 된 문자열을 반환
private fun getShiftString(a: String, aIndexMap: HashMap<Char, Int>, w: String, shift: Int): String {
 val sb = StringBuilder()
 for (ch in w) {
 val idx = (aIndexMap[ch]!! + shift) % a.length
 sb.append(a[idx])
 }
 return sb.toString()
}
// KMP 알고리즘을 사용, 암호문에서 쉬프트 된 패턴이 한번만 나타난다면 True 반환
// 0번 또는 2번 이상 나타난다면 False 반환
private fun containOnce(src: String, pattern: String): Boolean {
 //KMP 알고리즘을 위한 접두사, 접미사 인덱스 테이블 생성
 fun getKmpTable(): IntArray {
 val len = pattern.length
 val table = IntArray(len) { 0 }
 var pidx = 0
 for (idx in 1 until len) {
 while (pidx > 0 && pattern[idx] != pattern[pidx])
 pidx = table[pidx - 1]
 if (pattern[idx] == pattern[pidx])
 table[idx] = ++pidx
 }
 return table
 }
 // 실제 KMP 로직 수행
 val table = getKmpTable()
 var findCount = 0
 var pidx = 0
 for (idx in src.indices) {
 while (pidx > 0 && src[idx] != pattern[pidx])
 pidx = table[pidx - 1]
// println("** pattern diff : idx=$idx, pidx=$pidx, src[idx]=${src[idx]}, pattern[pidx]=${pattern[pidx]}")
 if (src[idx] == pattern[pidx]) {
 if (pidx == pattern.length - 1) {
 findCount++
 pidx = 0
// println("** pattern found : ${idx-pattern.length+1} .. $idx")
 if (findCount > 1) return false
 } else pidx++
 }
 }
// println("kmp find count=$findCount")
 return findCount == 1
}
private fun printResult(sb: StringBuilder, cnt: Int) {
 when (cnt) {
 0 -> bw.write("no solution\n")
 1 -> bw.write("unique: $sb\n")
 else -> bw.write("ambiguous: $sb\n")
 }
}
private fun flush() {
 br.close()
 bw.flush()
 bw.close()
}

loy15091 4년 전 1

치킨은 제가 먹겠습니다.

pidx를 0으로 돌리는부분 때문에 접미사와 접두사가 같은 패턴 탐색이 제대로 되지 않았습니다.

table사용해서 값할당하도록 바꿔 통과했습니다

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC