두뇌를 자극하는 문제 1

🙋‍♂️ 들어가며

이번문제를 통해 내 능지를 파악해보자

문자열 = “o t o o f o f o o o o t”

target = {‘t’, ‘f’, ‘t’}

d = 5;

라고 가정하자

이때 target의 순서대로 d이내 거리만큼 문자열이 연결되면 1을 반환

그렇지 못하면 0을 반환하자

조건

• 문자열 arr의 길이 N (1 ≤ N ≤ 1,000)
• target의 길이 M (1 ≤ M ≤ 100)
• 거리 d (1 ≤ d ≤ N)

test case

#1. input
o t t o o f o f o o o o t
t f t
5

#1 output
1



#2. output 
j j j j k k k k l l l l 
j k l
2

#2. output
0

🤔접근법

—————– test case 1번 기준 —————–

1. 배열 생성 (arr, target)
2. target[0]의 idx를 cur[] 배열에 저장 {1, 2, 12},    cur_size = 3
3. 2번째 target부터 보자. next[], next_size 활용
   • 3-1. 중복 인덱스 생성 방지를 위해 vistied[] 쓰자
   • 3-1. cur[] 에 저장된 각 원소를 idx+1 ~ idx+d 까지
   • 3-2. 만약 범위 초과시 break if (k >= arr길이) break
   • 3-3. next{5, 7} 이며 12는 범위 초과라 skip 했고 cur[] = next[] 로 갱신
4. next_size == 0 이면 다음 idx로 도달을 못한거니 flag = false 하고 break
5. cur[7] -> next[12] 로 도달 가능

코드

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;


public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input_arr = br.readLine().split(" ");
		String[] input_target = br.readLine().split(" ");
		int d = Integer.parseInt(br.readLine());
		
		int N = input_arr.length;
		int M = input_target.length;
		char[] arr = new char[N];
		char[] target = new char[M];
		
		for (int r = 0; r < N; r++) {
			arr[r] = input_arr[r].charAt(0);
		}
		for (int r = 0; r < M; r++) {
			target[r] = input_target[r].charAt(0);
		}
		
		// 1. target[0]을 먼저 확보
		int[] cur = new int[N];
		int cur_size = 0;
		for (int i = 0; i < N; i++) {
			if (arr[i] == target[0]) {
				cur[cur_size] = i;
				cur_size++;
			}
		}
		
		// 2. 2번째부터 탐색
		boolean success = true;
		for (int i = 1; i < M; i++) {
			int[] next = new int[N];
			int next_size = 0;
			char cur_ch = target[i];
			
			// 3. 중복 인덱스 생성 방지를 위해 visited[]
			boolean[] visited = new boolean[N];
			
			// 4. cur[]에서 cur_size만큼 각 원소 확인
			for (int j = 0; j < cur_size; j++) {
				int cur_val = cur[j];
				
				// 5. d만큼 확인
				for (int k = cur_val + 1; k < cur_val + d + 1; k++) {
					
					// 6. 가지치기 (범위 초과시에)
					if (k >= N) break;
					
					// 7. 방문 안했고, cur_ch랑 일치하면 next[]에 추가
					if (!visited[k] && arr[k] == cur_ch) {
						next[next_size] = k;
						next_size++;
						visited[k] = true;
					}
				}
			}
			
			// 8. next_size == 0 이라면 더이상 나아가지 못한거니 break
			if (next_size == 0) {
				success = false;
				break;
			}
			
			// 9. 그게 아니라면
			cur = next;
			cur_size = next_size;
		}
		
		// 10. 출력
		if (success) System.out.println(1);
		else System.out.println(0);	
	}
}