[백준 5534번] 파이썬 - 간판

백준 5534 - 간판

시간 제한 1초, 메모리 제한 256MB

# 조건

• 편의점이 있기 전에 원래 이 곳은 간판 가게였다.
• 따라서, 편의점에는 이전 주인이 버리고 간 오래된 간판이 N개 있다.
• 상근이는 오래된 간판에서 일부 문자를 지워 새로운 간판을 만들려고 한다.
• 이때, 남은 문자열이 편의점 이름이어야 하고, 남은 문자가 모두 일정한 간격으로 떨어져 있어야 한다.
• 간판은 오래된 간판 하나에서 만들어야 하고, 간판을 자르거나 붙일수는 없다.
• 편의점 이름과 오래된 간판의 정보가 주어졌을 때, 만들 수 있는 새 간판의 수를 구하는 프로그램을 작성하시오.
• 하나의 오래된 간판에서 만들 수 있는 방법이 여러 개인 경우에도 만들 수 있는 간판은 하나이다.

입력

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

출력

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

# 접근 방법

• 일정한 간격으로 알파벳을 남겼을 때 주어진 target 문자열과 같아야 한다.
• 따라서, word를 순회하며 현재 문자가 target의 첫 번째 문자와 같은 경우 target의 마지막 문자와 같은 알파벳의 위치를 찾아 e_idx에 기록해준다.
• target 문자열의 알파벳이 모두 들어 있는 거리가 e_idx - s_idx 이며 target 문자열의 길이로 나눠주면 일정한 간격이 나온다.
• 일정한 간격으로 순회하며 target문자열과 같다면 1을 리턴해준다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

def check(str):
    s_len = len(str)
    for s_idx in range(s_len):
        if str[s_idx] == target[0]:
            for e_idx in range(s_idx, s_len):
                if str[e_idx] == target[-1]:
                    dist = (e_idx - s_idx) // (t_len - 1)
                    cnt = 0
                    while cnt < t_len:
                        if str[s_idx + dist*cnt] == target[cnt]:
                            cnt += 1
                            continue
                        break
                    else:
                        return 1
    return 0


N = int(input())
target = input().strip()
result = 0
t_len = len(target)

words = list(input().strip() for _ in range(N))
result = 0

for word in words:
    result += check(word)
print(result)

 

• cpp 코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int result = 0;

bool isTrue(int first, int sec, string n, string o) {
    int gap = sec - first;
    if (gap * (n.size() - 1) + first > o.size()) {
        return 0;
    }
    else {
        for (size_t i = 0; i < n.size(); i++) {
            if (n[i] != o[first + gap * i])
                return 0;
        }
        return 1;
    }
    return 1;
}

void solve(string n) {
    string o;
    cin >> o;
    for (size_t i = 0; i < o.size(); i++) {
        if (o[i] == n[0]) {
            for (size_t j = i; j < o.size(); j++) {
                if (o[j] == n[1]) {
                    if (isTrue(i, j, n, o)) {
                        result++;
                        return;
                    }
                }
            }
        }
    }
}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int num;
    string board;
    cin >> num;
    cin >> board;

    for (int i=0; i<num; i++) solve(board);
    cout << result;
    return 0;
}