크기가 n인 양의 정수 리스트와 또 다른 양의 정수 m이 주어졌다고 가정해 보겠습니다. 우리는 어떤 루프를 진행 중이며, 매 반복마다 배열의 일부 요소 값은 1씩 감소시키고 나머지 요소 값은 m씩 증가시킵니다. 이때 여러 번의 반복 후에 리스트 요소 중 절반 이상이 0이 될 수 있는지 판별해야 합니다. 가능하다면 True를, 불가능하다면 False를 반환하면 됩니다.
예를 들어 입력이 input_list = [10, 18, 35, 5, 12], m = 4라고 한다면 출력은 True가 됩니다.
핵심 아이디어
이 문제의 열쇠는 모듈로(modulo) 연산에 있습니다. 매 반복에서 어떤 요소는 1만큼 줄어들고 나머지 요소는 m만큼 늘어나는데, m ≡ −1 (mod m+1)이므로 감소하든 증가하든 모든 요소의 값은 매 반복마다 (m+1)을 법으로 했을 때 1씩 줄어드는 것과 같습니다.
따라서 T번 반복한 시점에 어떤 요소가 정확히 0이 되려면 초기값 x에 대해 T ≡ x (mod m+1)를 만족해야 합니다. 즉, 동시에 0이 될 수 있는 요소들은 반드시 (m+1)로 나눈 나머지가 서로 같아야 합니다. 반대로 나머지가 같은 요소들이 있다면 반복 횟수 T를 충분히 크게 설정하여 감소 횟수를 적절히 분배함으로써 모두 0으로 만들 수 있습니다.
결론적으로, '배열의 절반 이상을 0으로 만들 수 있는가?'라는 질문은 '(m+1)로 나눈 나머지가 같은 요소가 배열 전체의 절반 이상인가?'와 동일한 문제가 됩니다.
풀이 단계
- 크기가 m+1이고 0으로 초기화된 빈도 리스트(frequency_list)를 생성합니다.
- 배열의 각 요소를 (m+1)로 나눈 나머지를 인덱스로 사용하여 빈도 리스트의 해당 값을 1씩 증가시킵니다.
- 빈도 리스트를 순회하면서 특정 나머지 값의 빈도가 배열 길이의 절반(n/2) 이상인지 확인합니다.
- 조건을 만족하는 나머지가 존재하면 True를, 끝까지 없으면 False를 반환합니다.
예제 구현
아래 구현을 통해 더 잘 이해해 보겠습니다.
def solve(input_list, m):
frequency_list = [0] * (m + 1)
i = 0
while(i < len(input_list)):
frequency_list[(input_list[i] % (m + 1))] += 1
i += 1
i = 0
while(i <= m):
if(frequency_list[i] >= (len(input_list)/ 2)):
break
i += 1
if (i <= m):
return True
else:
return False
input_list = [10, 18, 35, 5, 12]
print(solve(input_list, 4))
입력
[10, 18, 35, 5, 12], 4
출력
True
동작 과정 살펴보기
m = 4이므로 기준값은 (m+1) = 5입니다. 각 요소를 5로 나눈 나머지를 계산하면 10 → 0, 18 → 3, 35 → 0, 5 → 0, 12 → 2입니다. 따라서 빈도 리스트는 [3, 0, 1, 1, 0]이 되고, 나머지가 0인 요소가 3개(10, 35, 5)로 배열 길이 5의 절반인 2.5 이상입니다. 조건을 만족하므로 결과는 True입니다.
이 풀이의 시간 복잡도는 배열 순회와 빈도 리스트 검사로 O(n + m)이며, 공간 복잡도는 크기가 m+1인 빈도 리스트로 인해 O(m)입니다.