[코테/Python] 페인트칠

목차 (OPEN)

• 📑 문제
• 💡 아이디어
• 👩🏻‍💻 전체 코드
• 📚 결론

 

 

 

 

얼마전에 졸업 필수요건인 코테 1차 시험 겸 교내 코딩 경진대회에 참여했었는데,

더 미루면 문제를 까먹을 것 같아서 우선 간단히 기록해두려고 한다 ,,🤧

따로 문제를 올려주시지는 않았고, 내가 제출한 파일만 다운받을 수 있게 돼있어서

문제 설명이 많이 빈약할 수도 있다 ..

 

📑 문제

• n개의 벽돌이 주어진다.
• 쿼리 2가지가 주어진다.
  1) `1 p x` 형태의 입력이 들어오면 👉🏻 p번 벽돌을 x번 색으로 다시 칠한다.
  2) `2 x` 형태의 입력이 들어오면 👉🏻 모든 벽돌을 x번 색으로 다시 칠한다.
• 모든 쿼리를 수행한 뒤, 각 벽돌의 최종 색깔을 출력해야 한다.

 

즉, 전체 색칠과 부분 색칠이 섞여 있을 때,

각 벽돌의 최종 상태를 어떻게 효율적으로 기록할지가 핵심이다.

 

 

---

💡 아이디어

처음에는 단순히 쿼리마다 벽돌 배열을 업데이트하려고 했지만,

이런 문제에서 시간 초과 난게 한두번이 아니어서 .. ㅎㅎ

이런 단순한 방법은 아닐 거라 생각하고 다른 방법을 고민해보았다.

 

그래서 떠올린 전략은 아래와 같다.

1. 전체 색칠은 벽돌 배열을 업데이트 하지 않고,
   변수에 마지막 전체 색칠 시각과 마지막 전체 색칠 색상만 기록한다.
2. 부분 색칠은 벽돌 배열을 업데이트 해주고,
   변수에 마지막 부분 색칠 시각을 기록해준다.
   (해당 벽돌을 언제 마지막으로 칠했는지)
3. 마지막에 각 벽돌을 검색할 때
   1) 만약, 부분 색칠 시간이 전체 색칠 시간보다 늦으면 👉🏻 해당 블록은 부분 색칠 색상으로 칠해준다.
   2) 그렇지 않으면 👉🏻 전체 색칠 색상으로 칠해준다.
   3) 아무 기록도 없으면 👉🏻 초기 색상으로 칠해준다.

 

이렇게 하면 각 쿼리를 O(1)안에 작업하고,

마지막 출력 단계에서만 O(n)으로 계산하면 되기 때문에

무조건 통과할 거라고 생각했다 😎

 

 

---

👩🏻‍💻 전체 코드

n = int(input().strip())
a = list(map(int, input().split())) # 초기 벽돌 색
q = int(input().strip())

last_time = 0             # 마지막 전체 색칠 시각
last_color = None         # 마지막 전체 색칠 색상
last_small_time = [0] * n # 각 벽돌별 마지막 부분 색칠 시각
color = a[:]              # 벽돌 색 기록



t = 0

for _ in range(q):
	parts = input().split()
	t += 1 # 쿼리마다 시각 1씩 증가시키기

	if parts[0] == '1': # 부분 색칠
		p = int(parts[1]) - 1
		x = int(parts[2])
		color[p] = x
		last_small_time[p] = t
	else: # 전체 색칠
		x = int(parts[1])
		last_time = t
		last_color = x

ans = []
for i in range(n):
	if last_small_time[i] > last_time: # 부분 색칠이 더 최근인 경우
		ans.append(color[i])
	else:
		if last_time > 0: # 전체 색칠이 더 최근인 경우
			ans.append(last_color)
		else: # 한 번도 색칠하지 않은 경우
			ans.append(a[i])

print(*ans)

 

 

---

📚 결론

이번 문제는 단순 구현처럼 보여도, 전체 갱신 연산을 그대로 수행하면 시간 초과가 난다는 함정을 숨기고 있었다.

(실제로 코테가 끝난 후 친구와 얘기해봤을 때, 그 친구도 시간초과 때문에 고생했다고 했다.)

 

만약 전체 갱신 연산을 그대로 수행하게 되면,

전체 색칠 연산이 여러번 나오는 경우 시간 복잡도가 O(nq)로 커져버리기 때문에 이는 상당히 비효율적이다.

 

따라서 전체 색칠은 실제로 각 쿼리마다 벽돌 배열을 업데이트하는 대신에 시각과 색상만을 기록한 것이고,

부분 색칠은 해당 벽돌 배열을 실제로 업데이트해주고, 추후 업데이트를 위해 시각을 기록해준 것이다.

 

이제 이런 유형은 하도 많이 봐서 시간 복잡도가 관건일거라고 생각하고 접근하기는 하지만 ,,

앞으로도 모든 원소를 갱신해야 하는 경우, '정말 굳이 다 갱신할 필요가 있을까?' 라는 질문을 던질 수 있도록 계속 의식하고 있어야 겠다.