[백준] 28298 더 흔한 타일 색칠 문제 (python 파이썬)

https://www.acmicpc.net/problem/28298

28298번: 더 흔한 타일 색칠 문제

---

시간 초과가 생긴 문제. 이번엔 입력값 제한을 보고 시간에 맞게 로직을 짰다고 생각했는데 시간초과가 발생했다.

로직을 조금 수정하니까 통과했다. 왜 그런지 생각해 보니 원인을 찾을 수 있었다.

 

중간에 리스트에서 개수가 가장 많은 요소를 출력하는 메서드가 필요했다.

많은 방법이 있지만 나는 코드를 간결하게 작성하고 싶어 max(arr, key = arr.count)로 구현했다.

len(arr) = n이라 가정하면, arr.count 가 n번 실행된다. 따라서 위 코드의 시간복잡도는 n**2이다.

 

따라서 전체 시간복잡도는 약 K * K * ((N/K * M/K )**2)이고 최대 1 * 1 * ((500 * 500)**2) = 62500000000이 된다. 시간초과나 발생하는 게 당연하다.

 

오늘의 교훈: 새로운 방법을 쓸 때는 시간복잡도를 꼼꼼히 계산해 보자.

---

아이디어

1. K * K로 타일들을 나눠준다.

2. 위에 빨간색처럼, K * K로 나눠진 타일들의 각 자리를 기준으로 알파벳 개수를 계산한다.

3. 알파벳 개수가 가장 많은 알파벳으로 타일들을 교체해 준다. 교체한 타일 개수도 저장해 준다.

---

전체 코드 (+ 주석) 

import sys

tiles = [] # N * M 타일
count_list = [0] * 26 # 알파벳의 개수를 count해주는 리스트
Sum = 0 # 교체한 타일 개수

N, M, K = map(int, input().split())
for i in range(N):
    tiles.append(list(sys.stdin.readline().rstrip()))

step_num = N * M // K**2 # K * K 로 나눈 개수

for x in range(K):
    for y in range(K): # K * K 판에서 각각의 자리

        count_list = [0] * 26 # 개수 count 리스트 초기화

        for i in range(0, N - K+ 1, K):
            for j in range(0, M - K + 1, K): 
                t = tiles[i + x][j + y]
                count_list[ord(t) - 65] += 1 # 알파벳 count

        max_tile_num = max(count_list) 
        Sum += step_num - max_tile_num # 변경한 타일 개수 추가
        max_tile = chr(count_list.index(max_tile_num) + 65) #가장 개수가 많은 알파벳 return

        for i in range(0, N - K+ 1, K):
            for j in range(0, M - K + 1, K):
                tiles[i + x][j + y] = max_tile # 타일 변환

# 출력
print(Sum)
for line in tiles:
    print("".join(line))

---

코드 설명

count_list = [0] * 26 # 개수 count 리스트 초기화

for i in range(0, N - K+ 1, K):
    for j in range(0, M - K + 1, K):
        t = tiles[i + x][j + y]
        count_list[ord(t) - 65] += 1 # 알파벳 count

타일에 올 수 있는 값이 알파벳 대문자만 올 수 있다는 걸 이용해 각 알파벳의 개수를 배열의 값으로 표현했다. 

ord() 함수를 활용해 인덱스값과 알파벳을 일치시켜준다. (ord('A') = 65, chr(65) = 'A')

 

max_tile_num = max(count_list)
Sum += step_num - max_tile_num # 변경한 타일 개수 추가
max_tile = chr(count_list.index(max_tile_num) + 65) #가장 개수가 많은 알파벳 return

for i in range(0, N - K+ 1, K):
    for j in range(0, M - K + 1, K):
        tiles[i + x][j + y] = max_tile # 타일 변환

가장 많은 알파벳의 개수를 이용해 변경한 타일 개수를 구한다.

chr() 함수를 사용해서 알파벳을 리턴해준다.