✨ 문제
문제 링크 → 백준 1241번 - 머리 톡톡
✨ 주의할 점
- 문제를 푸는 것 자체는 쉬운데 시간 제한 때문에 여러 방법을 이용하지 못하는 경우가 생긴다.
- 자기 자신의 머리는 치지 않는다는 것
- 자신의 숫자가 다른 사람 숫자의 배수일 때만 머리를 톡톡친다는 것
✨ 풀이
시간 초과 코드들
N = int(input())
student_nums = []
for _ in range(N):
student_nums.append(int(input()))
results = [0] * N
for i in range(N):
for j in range(i+1, N):
stu1 = student_nums[i]
stu2 = student_nums[j]
if (stu1 == stu2):
results[i]+=1
results[j]+=1
elif (stu1 % stu2 == 0):
results[i]+=1
elif (stu2 % stu1 == 0):
results[j]+=1
for result in results:
print(result)- 위 코드는 내가 쓰면서도 너무 오래걸리지 않을까 고민했던 코드이다..
- 일단 이중 for문을 썼기 때문에 시간 복잡도가 거의 N^2에 가까워서 시간 초과가 발생한 듯 하다.
- 여기서는 일단 학생들의 숫자를 입력받고 (i+1)번째 학생의 숫자와 i+2, ..., N번째 학생의 숫자를 다음 3가지 경우로 비교해 최종 경우의 수를 구해주려고 했다.
1) 숫자 같은 경우 : 두 학생 모두 서로의 배수이므로 i, j 인덱스에 해당하는 원소에 1을 더함
2) i+1번째 학생의 숫자가 다른 학생의 숫자의 배수일 경우 : i 인덱스에 해당하는 원소에 1을 더함
3) 2에서 반대의 경우 : j 인덱스에 해당하는 원소에 1을 더함
👉🏻 시간 초과가 발생해서 일단 될까..? 하는 마음으로 작성한 코드가 아래에 있다.
import sys
N = int(sys.stdin.readline())
student_nums = [0]*N
results = [0]*N
for i in range(N):
stu_num = int(sys.stdin.readline())
student_nums[i] = stu_num
for j in range(i):
if (stu_num == student_nums[j]):
results[i]+=1
results[j]+=1
elif (stu_num % student_nums[j] == 0):
results[i]+=1
elif (student_nums[j] % stu_num == 0):
results[j]+=1
answer = ""
for result in results:
answer += str(result)+"\n"
print(answer)- 여기서는 파이썬에서 시간 초과 발생 시 할 수 있다는 대표적인? 방법들 중 다음 3가지를 적용해봤다.
- input 대신 sys 모듈 import 후 sys.stdin.readline을 사용
- append() 함수 대신 인덱스를 사용해 array에 값을 대입
- print() 함수를 여러 번 호출하는 대신 문자열로 구성해 1번의 print() 함수 호출만으로 여러 줄바꿈을 수행
👉🏻 역시나 골드 문제답게 이걸로 해결은 불가능했다.. 이럴 때 생각해야 하는 것은 다른 풀이를 찾아보는 것이다. 아마 문제에서 요구하는 풀이 방향이 있을 것이라 생각하고 어떤 것을 활용할지 생각해봐야 한다.
시간 통과한 코드
시간 초과가 뜬 코드에서는 배수 개념을 그대로 사용했는데, 문제는 중복되게 구해야 하는 것들이 너무 많았다는 것이다. 그래서 이번에는 반대로 약수 개념을 사용해 중복되는 부분들은 최대한 이미 구했던 부분에서 활용할 수 있게 해보려고 했다.
- 배수 → 약수로 바꿔 생각하면, 결국 어떤 특정 숫자 A의 약수가 되는 숫자 개수를 찾는 문제가 된다.
- 단, 최종적으로 자기 자신은 카운팅하면 안된다.
- 아래 코드는 결국 숫자 4가 있을 때 약수인 숫자 1, 2, 4의 개수를 더하면 정답을 풀 수 있다는 점을 가지고 작성한 내용이다.
import sys
N = int(sys.stdin.readline())
circle, result = [0]*N, [0]*N
for i in range(N):
circle[i] = int(sys.stdin.readline())
matrix = [0 for _ in range(max(circle)+1)]
for c in circle:
matrix[c]+=1
for n in range(N):
k = 1
while (k*k <= circle[n]):
if circle[n] % k == 0: # k가 circle[n]의 약수이면 다음 2가지 경우로 나눠 생각
if k*k != circle[n]: # 1) circle[n]과 k**2이 같지 않을 때 : 약수 k와 circle[n]//k의 개수를 더한다.
result[n] += matrix[k] + matrix[circle[n]//k]
else: # 2) circle[n]과 k**2이 같을 때 : k의 제곱과 같으면 약수는 k 하나이므로 matrix[k] 하나만 더한다.
result[n] += matrix[k]
k += 1
answer = ""
for r in result:
answer += str(r-1)+"\n" # -1은 while 문에서 자기 자신을 배수로 취급하여 센 것을 빼기 위해서이다.
print(answer)코드를 주어진 예제로 이해하면 다음과 같다.
circle
| 2 | 1 | 2 | 3 | 4 |
|---|
matrix - 숫자 개수 나타내는 배열(범위는 0~circle 배열에서 최대 숫자)
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 0 | 1 | 2 | 1 | 1 |
👉🏻 숫자 1이 1개, 숫자 2가 2개, 숫자 3이 1개, 숫자 4가 1개 등장한다는 의미
result
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 2 | 0 | 2 | 1 | 3 |
예시) n = 0, k = 1일 때 - circle[0] = 2
: k*k(1)이 2보다 작은데, 같지는 않으므로 약수 1과 2//1=2에 대해 matrix[1]과 matrix[2//1]=matrix[2]를 더해 result[0]을 계산한다.
시간 단축한 다른 풀이
import sys
t = 1000000
N = int(sys.stdin.readline())
circle = [int(sys.stdin.readline()) for _ in range(N)]
list = [0]*(t+1) # circle 요소들 개수 세는 리스트
cnt = [0]*(t+1) # 머리 툭툭 치는 횟수 저장하는 리스트
for c in circle:
list[c] += 1
for i in range(1,t+1):
if list[i]: # list[i] != 0일 때
cnt[i] += list[i]-1 # 1을 뺀 것은 자기 자신을 제외하기 위함
for j in range(i+i,t+1,i): # 2*i, 3*i, 4*i, ... 는 i의 배수이므로 j의 cnt에 i 개수를 더해준다.
cnt[j] += list[i]
answer = ""
for i in circle:
answer += str(cnt[i]) + "\n"
print(answer)- 이 코드는 문제에서 제공해준 N의 범위 중 최댓값을 t에 저장해 시간복잡도가 O(t)가 되도록 했다.
- i라는 숫자가 입력에서 존재했더라면 if list[i]가 if True가 되어 if문 안 3줄의 코드가 수행된다. 먼저 첫 번째 덧셈 부분은 자기 자신을 제외하고 같은 숫자가 존재하는 개수를 더해준 것이고, for문은 숫자 i의 배수들의 cnt에 i의 개수를 더해주는 코드이다.
✨ 결과
시간 통과한 코드
시간 단축한 다른 풀이
👩🏻💻 후기
시간 단축이 나타나면 문제 풀이 방향을 다르게 생각해봐야 하고 배수 문제 같은 경우는 약수 문제로도 바꿔 풀 수 있는지 확인해보는 게 좋다는 생각이 들었다. 또, 3번째 코드도 결과를 보면 시간이 꽤 오래 걸렸는데, 이것보다 더 시간을 단축한 아래 풀이는 다른 풀이들을 보고 정리한 거라 아직 많이 부족하다는 생각이 들었다. 다 풀고 나서 보니 시간을 단축한 풀이가 더 생각하기 쉬웠을 것 같다는 생각을 했다. 그래도 이번 기회에 상대적으로 다양한 풀이로 문제를 접근해봐서 좋았다. 다음 문제도 고고~~!!
