5534번: 간판

문제 출처 : https://www.acmicpc.net/problem/5534

 

언어 : Kotlin

 

문제 설명 :

상근이는 학교 근처에 새로운 편의점을 열었다. 편의점의 얼굴은 간판이라고 할 수 있다. 상근이가 새로 연 편의점은 프랜차이즈 편의점이 아니기 때문에, 간판도 자신이 직접 돈을 들여서 만들어야 한다.

근처 편의점은 이미 할인 카드, 적립 카드와 같은 정책으로 손님을 끌어 모으고 있다. 상근이는 전 품목을 5%해서 손님을 모으려고 한다. 이렇게 물건의 가격을 할인해서 팔려면, 다른 곳에 들어가는 비용을 줄어야 한다. 따라서, 상근이는 간판을 재활용해서 만들기로 했다.

편의점이 있기 전에 원래 이 곳은 간판 가게였다. 따라서, 편의점에는 이전 주인이 버리고 간 오래된 간판이 N개 있다. 상근이는 오래된 간판에서 일부 문자를 지워 새로운 간판을 만들려고 한다. 이때, 남은 문자열이 편의점 이름이어야 하고, 남은 문자가 모두 일정한 간격으로 떨어져 있어야 한다. 간판은 오래된 간판 하나에서 만들어야 하고, 간판을 자르거나 붙일수는 없다.

편의점 이름과 오래된 간판의 정보가 주어졌을 때, 만들 수 있는 새 간판의 수를 구하는 프로그램을 작성하시오. 하나의 오래된 간판에서 만들 수 있는 방법이 여러 개인 경우에도 만들 수 있는 간판은 하나이다.

 

입력 :

첫째 줄에 오래된 간판의 수 N이 주어진다. (1 ≤ N ≤ 100) 둘째 줄에는 상근이가 새로 연 편의점의 이름이 주어진다. 이름은 알파벳 소문자로만 이루어져 있고, 길이는 3자 이상, 25자 이하이다. 다음 N개 줄에는 이전 주인이 버리고 간 간판에 쓰여 있는 문자가 주어진다. 이 간판에 쓰여 있는 문자는 알파벳 소문자이고, 길이는 1자 이상 100자 이하이다.

 

출력 :

첫째 줄에 상근이가 만들 수 있는 간판의 수를 출력한다.

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 256MB

 

입출력 예 :

입력	출력
4 bar abracadabra bear bar baraxbara	3

 

풀이 : 

버리고 간 간판의 시작점 기준으로 반복문을 형성한다.

내 간판[0] == 버리고 간 간판[i]가 같다면 반복문을 또 만들어 이후의 문자열들을 비교해나간다.

 

버리고 간 간판[j]와 내 간판의 마지막 글자가 같다면 그 사이의 문자열들로 하여금 간격을 계산한다.

시작과 끝을 알고 있기 때문에 가운데에 있는 문자열들의 구성과 별개로 우선 일정하게 떨어져 있는지 계산하는 것이다.

 

일정하게 떨어져 있지 않다면 틀린 것이므로 continue를 통해 다음 시작점을 반복문을 나가고 다음 시작점을 찾는다.

없다면 0을 반환하고 cnt에 추가한다.

 

일정하게 떨어져 있다면 그제서야 가운데에 있는 문자열들의 구성을 비교한다.

버리고 간 문자열의 시작점 i + 간격 * cnt를 통해 내 간판 문자열과 비교하고

같다면 cnt를 증가시킨다.

 

반복문을 빠져나와 cnt가 내 간판 문자열의 길이와 동일하다면 1을 반환한다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val n = readLine().toInt()
    val name = readLine()
    val choice = MutableList<String>(n) { readLine() }

    var cnt = 0
    for (str in choice) {
        cnt += checkChoice(str, name)
    }

    bw.write("$cnt")
    bw.flush()
    bw.close()
}

fun checkChoice(str: String, name: String): Int {
    val nL = name.length

    for (i in str.indices) {
        if (str[i] == name[0]) {
            for (j in i + 1 until str.length) {
                if (str[j] == name[nL - 1]) {
                    val gap = (j - i) / (nL - 1)
                    if ((j - i) % (nL - 1) != 0) continue

                    var cnt = 1
                    while (cnt < nL) {
                        if (str[i + gap * cnt] == name[cnt]) {
                            cnt++
                        } else {
                            break
                        }
                    }

                    if (cnt == nL) return 1
                }
            }
        }
    }

    return 0
}