* 파이썬으로 풀었습니다.
String Match
6550. 부분문자열
문제
2개의 문자열 s와 t가 주어졌을 때 s가 t의 부분 문자열인지 판단하는 프로그램을 작성하라. 부분 문자열을 가지고 있는지 판단하는 방법은 t에서 몇 개의 문자를 제거하고 이를 순서를 바꾸지 않고 합쳤을 경우 s가 되는 경우를 이야기 한다.
String Match (문자열 매치) : 전체 문자열에서 부분 문자열이 존재하는지 확인하는 알고리즘
위의 문제의 예제 입력 중
VERDI vivaVittorioEmanueleReDiItalia출력이 Yes로 되는 것을 보아 굳이 붙어있어야하는 건 아닌 것 같습니다.
코드 구현
import sys
input = sys.stdin.readline
while True:
try:
line = input()
if not line.strip():
break
parts = line.strip().split()
if len(parts) != 2:
continue
s, t = map(list, parts)
count = 0
now = 0
found = False
for i in range(len(s)):
for j in range(now, len(t)):
if s[i] == t[j]:
count += 1
now = j + 1
break
if j == len(t) - 1 and s[i] != t[j]:
found = True
break
if found:
break
if count == len(s):
print("Yes")
else:
print("No")
except EOFError:
break
일단 입력 조건을 보면 테스트 케이스의 개수가 한정적이지 않습니다. try-except로 예외처리를 해줍니다.
제 바보뇌는 이중반복문밖에 못 떠올려서 누가봐도 최악인 성능으로 코드를 구현하게되었습니다.
맞았다고 끝이 아니니 더 효율적인 코드를 공부해줍니다.
투 포인터 방식
s, t = parts
i = j = 0
while i < len(s) and j < len(t):
if s[i] == t[j]:
i += 1 # s의 현재 문자가 t에서 발견되었으니 다음 문자 비교
j += 1 # t는 항상 다음으로 이동
print("Yes" if i == len(s) else "No")이중 반복문의 복잡도 O(N * M)과 다르게 투 포인터 방식은 O(N + M)으로 복잡도가 낮습니다.
i는 s의 현재 위치이고, j는 t의 현재 위치로 s[i]와 t[j]가 같을 때 다음 s로 넘어가고, t는 항상 넘어가는 방식입니다. 저의 바보코드와는 다르게 간결하고 이쁘게 생겼습니다.
1543. 문서검색
문제
세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 단어가 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다.
세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오.
그 전 문제와는 다르게 단어가 쪼개져도 상관없는게 아닌 온전히 있는 걸 찾아야합니다.
아까 지피티에게 배운 방법을 응용해서 코드를 구현해보았습니다.
import sys
input = sys.stdin.readline
document = input().rstrip() #문서
word = input().rstrip() #검색단어
i = 0
j = len(word) #검색단어의 길이
wordCount = 0
while i <= len(document) - len(word):
if document[i : j] == word:
wordCount += 1
i += len(word)
j += len(word)
else:
i += 1
j += 1
print(wordCount)여기서 중요한 점은 문자열로 진행하니 rstrip()로 개행문자를 꼭 지워주기!
11656. 접미사 배열
문제
접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열이다.
baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n, on, oon이 된다.
문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 다음 출력하는 프로그램을 작성하시오.
import sys
input = sys.stdin.readline
S = input().rstrip()
SuffixArr = []
for i in range(len(S)):
SuffixArr.append(S[i:len(S)])
SuffixArr.sort()
for i in range(len(S)):
print(SuffixArr[i])
문제는 쉬웠는데 파이썬으로 풀어서 쉬운 것 같습니다. 더 효율적으로 String Match 하는 법을 더 공부해야겠습니다.