[백준 1013] Contact

백준 1013번: Contact - 상세 풀이

🔍 1. 문제 소개

백준 1013번 "Contact" 문제는 외계 전파 신호의 패턴을 분석하는 프로그램을 작성하는 문제입니다. 전파 신호는 0과 1로 이루어진 문자열로 표현되며, 특정한 패턴을 따릅니다. 문제에서는 + (반복) 연산자와 | (or) 연산자를 사용하여 표현된 복잡한 패턴을 주어진 문자열이 따르는지 확인해야 합니다. 예를 들어 (100+1+ | 01)+ 와 같은 패턴이 주어지면, 입력 문자열이 이 패턴에 맞는지 판별하는 프로그램을 작성해야 합니다.

💡 2. 문제 해석

문제의 핵심은 주어진 전파 패턴을 정확하게 표현하고, 입력 문자열과의 일치 여부를 효율적으로 판별하는 것입니다. 문제에서 사용되는 + 연산자는 최소 한 번 이상의 반복을 의미하며, | 연산자는 두 가지 패턴 중 하나를 선택할 수 있음을 의미합니다. 입력 문자열의 길이는 최대 200이며, 여러 개의 테스트 케이스가 주어집니다. 따라서 효율적인 알고리즘을 사용하여 시간 제한 내에 모든 테스트 케이스를 처리해야 합니다.

🧠 3. 접근 방법

이 문제는 정규 표현식(Regular Expression)을 사용하여 효율적으로 해결할 수 있습니다. 주어진 전파 패턴을 정규 표현식으로 변환하여, 입력 문자열과 일치하는지 확인합니다. Kotlin은 내장된 정규 표현식 기능을 제공하므로, 이를 활용하면 간결하고 효율적인 코드를 작성할 수 있습니다. 정규 표현식을 사용하면 반복과 선택 연산을 쉽게 표현할 수 있으며, 문자열 매칭을 효율적으로 수행할 수 있습니다.

⚙️ 4. 구현 과정

1. **입력:** 테스트 케이스의 개수 T를 입력받습니다.

2. 반복: T번 반복하며, 각 테스트 케이스마다 전파 문자열을 입력받습니다. 3. 정규 표현식 매칭: 입력받은 전파 문자열이 주어진 패턴 (100+1+|01)+ 과 일치하는지 matches() 함수를 이용하여 확인합니다. ^와 $를 추가하여 문자열 전체가 패턴과 일치하는지 확인합니다. 4. 출력: 매칭 결과에 따라 "YES" 또는 "NO"를 출력합니다.

💻 5. 코드 설명

fun solve() {
    val input = readLine()!!
    println(if (input.matches(Regex("^(100+1+|01)+$"))) "YES" else "NO")
}

fun main() {
    val t = readLine()!!.toInt()
    repeat(t) {
        solve()
    }
}

* main 함수: 테스트 케이스의 개수를 입력받고, solve 함수를 반복적으로 호출합니다. * solve 함수: * readLine()!!: 표준 입력으로부터 전파 문자열을 한 줄 읽어옵니다. !!은 null이 아님을 보장하는 non-null assertion operator입니다. 입력이 항상 존재한다는 가정하에 사용합니다. 더 안전한 방법은 ?: "" 와 같은 null 처리를 추가하는 것입니다. * Regex("^(100+1+|01)+$"): (100+1+|01)+ 패턴을 정규 표현식으로 나타냅니다. ^는 문자열의 시작을, $는 문자열의 끝을 의미합니다. 이는 입력 문자열 전체가 패턴과 일치해야 함을 의미합니다. * matches(): 정규 표현식과 입력 문자열이 일치하는지 확인합니다. boolean 값을 반환합니다. * if ( ... ) "YES" else "NO": 삼항 연산자를 사용하여 결과를 간결하게 출력합니다.

⏱️ 6. 시간 복잡도와 공간 복잡도 분석

* 시간 복잡도: 정규 표현식 매칭의 시간 복잡도는 일반적으로 입력 문자열의 길이에 따라 선형 또는 지수적으로 증가할 수 있습니다. 하지만, 이 문제의 경우 입력 문자열의 길이가 최대 200으로 제한되어 있고, 비교적 간단한 정규 표현식을 사용하므로, 실제 실행 시간은 매우 빠릅니다. 따라서 시간 복잡도는 O(N)으로 볼 수 있습니다. (N은 입력 문자열의 길이) * 공간 복잡도: 정규 표현식 객체와 입력 문자열을 저장하는 공간이 필요합니다. 입력 문자열의 길이가 최대 200이므로, 공간 복잡도는 O(N)입니다.

🎯 7. 결론

이 문제는 정규 표현식을 활용하여 효율적으로 해결할 수 있습니다. Kotlin의 정규 표현식 기능을 사용하면 코드를 간결하고 읽기 쉽게 작성할 수 있으며, 시간 제한 내에 모든 테스트 케이스를 처리할 수 있습니다. 입력 크기가 작기 때문에 시간 복잡도에 대한 고려는 크게 필요하지 않았지만, 더 큰 입력에 대해서는 정규 표현식의 효율성을 고려해야 할 수 있습니다. 더욱 효율적인 알고리즘을 고안하기 보다는, 주어진 문제에 맞는 적절한 도구(정규표현식)를 사용하는 것이 중요하다는 것을 알 수 있습니다. 코드의 안정성을 높이기 위해 readLine()!! 부분에 null 처리를 추가하는 것을 고려해볼 수 있습니다.