B. Reverse String | Harbour.Space Scholarship Contest
https://codeforces.com/contest/1553/problem/B
시간 3초, 메모리 256MB
input :
- q (1 ≤ q ≤ 500)
- s (1 ≤ |s| ≤ 500)
- t (1 ≤ |t| ≤ 2⋅|s|−1)
output :
- For each test case, print "YES" if you can obtain the string t by performing the process mentioned in the statement with the string s, or "NO" if you cannot.
각 테스트 케이스에서 t를 얻을 수 있다면 "YES"를 그렇지 않은 경우에는 "NO"를 출력하시오.
조건 :
-
After placing the chip, you move it to the right several (maybe zero) times, i. e. you perform the following operation several times: if the current position of the chip is i, you move it to the position i+1. Of course, moving the chip to the right is impossible if it is already in the last position.
칩을 놓은 이후에 오른쪽으로 몇 번 움직입니다. 이 행동은 아래의 조건을 따릅니다.
현재 칩의 위치를 i라 할 때, 칩을 i + 1로 이동시킵니다. 물론 문자열의 바깥으론 이동할 수 없습니다. -
After moving the chip to the right, you move it to the left several (maybe zero) times, i. e. you perform the following operation several times: if the current position of the chip is i, you move it to the position i−1. Of course, moving the chip to the left is impossible if it is already in the first position.
오른쪽으로 이동이 끝난 후, 칩을 왼쪽으로 몇 번 움직입니다. 이 행동은 아래의 조건을 따릅니다.
현재 칩의 위치를 i라 할 때, 칩을 i - 1로 이동시킵니다. 물론 문자열의 바깥으론 이동할 수 없습니다.
처음 시간을 소요하면서 생각한 것은 오른쪽 왼쪽으로 왔다 갔다 하는 경우를 생각하는 바람에 코드를 수정해야 했다.
오른쪽 이동, 왼쪽 이동
이동하는 횟수? 라기 보다는 방향 전환이 1번만 발생해야 한다.
그렇기 target문자열을 만들 수 있는 문자라면 이 때 왼쪽으로 가도 될까? 하는 방식으로 문제를 해결했다.
결국 재귀의 방식을 사용해서 시간은 많이 소요되겠지만 사이즈가 작아서 가능 하다.
import sys
sys.setrecursionlimit(100000)
def check(idx, target_idx, direction):
if target_idx == len(target) - 1:
return True
if idx - 1 >= 0 and data[idx - 1] == target[target_idx + 1]:
if check(idx - 1, target_idx + 1, 0):
return True
if direction == 1 and idx + 1 < len(data) and data[idx + 1] == target[target_idx + 1]:
if check(idx + 1, target_idx + 1, 1):
return True
return False
t = int(sys.stdin.readline())
for _ in range(t):
data = sys.stdin.readline().rstrip()
target = sys.stdin.readline().rstrip()
start = []
for i in range(len(data)):
if target[0] == data[i]:
start.append(i)
flag = False
for idx in start:
flag = check(idx, 0, 1)
if flag:
break
print("YES" if flag else "NO")
Author And Source
이 문제에 관하여(B. Reverse String | Harbour.Space Scholarship Contest), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsin2475/B.-Reverse-String-Harbour.Space-Scholarship-Contest저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)