배열 A에 N개의 요소가 있고, 찾고자 하는 값 p와 구간(segment)의 크기 k가 주어졌을 때, 배열 A를 크기 k로 나눈 모든 구간 안에 값 p가 존재하는지 확인해야 하는 문제입니다.
예를 들어, 입력이 다음과 같다고 가정해 보겠습니다.
- A = [4, 6, 3, 5, 10, 4, 2, 8, 4, 12, 13, 4]
- p = 4 (찾을 키)
- k = 3 (구간 크기)
배열을 크기 3씩 나누면 [4, 6, 3], [5, 10, 4], [2, 8, 4], [12, 13, 4] 네 개의 구간이 되고, 각 구간마다 4가 모두 포함되어 있으므로 출력은 True가 됩니다.
문제 해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 인덱스 i를 0으로 초기화합니다.
- i가 n보다 작은 동안 반복하면서, 각 구간 내부에서 j를 이용해 요소를 하나씩 검사합니다.
- 구간 안에서 arr[j + i]와 p가 같으면 내부 루프를 종료하고 다음 구간으로 넘어갑니다.
- 내부 루프가 끝났는데도 j가 k와 같다면, 해당 구간에서 p를 찾지 못한 것이므로 False를 반환합니다.
- 모든 구간을 확인한 후 i가 n과 같으면 True를 반환합니다.
마지막 불완전한 구간 처리하기
주의할 점은 배열의 길이가 k의 배수가 아닐 수 있다는 것입니다. 이 경우 마지막 남은 부분 구간도 별도로 검사해야 합니다. 마지막 구간은 i - k부터 n까지 순회하며 p가 존재하는지 확인하고, 끝까지 찾지 못하면 False를 반환합니다.
구현 예시
아래 코드를 통해 더 잘 이해할 수 있습니다.
def key_in_segment_k(arr, p, k, n) :
i = 0
while i < n :
j = 0
while j < k :
if arr[j + i] == p :
break
j += 1
if j == k :
return False
i = i + k
if i == n :
return True
# 배열 길이가 k의 배수가 아닌 경우 마지막 부분 구간 검사
j = i - k
while j < n :
if arr[j] == p :
break
j += 1
if j == n :
return False
return True
arr = [4, 6, 3, 5, 10, 4, 2, 8, 4, 12, 13, 4]
p, k = 4, 3
n = len(arr)
print(key_in_segment_k(arr, p, k, n))입력
[4, 6, 3, 5, 10, 4, 2, 8, 4, 12, 13, 4]
출력
True
시간 복잡도
이 알고리즘은 각 구간을 한 번씩 순회하므로 시간 복잡도는 O(n)입니다. 여기서 n은 배열의 전체 길이이며, 공간 복잡도는 추가 메모리를 사용하지 않으므로 O(1)입니다.