💡 문제 해결 아이디어

🛠 피드백

• deepcopy는 시간이 완전 오래걸린다. 차라리 원본을 바꿔 시도하고, 원래대로 되돌려 놓는게 더 빠르다.
• 시간복잡도가 1억이 넘으면 대략적으로 1초를 넘긴다고 한다.
• 하지만, 굉장히 허술한 방법이니 그냥 임의의 경계값이라고 생각하자.

내가 생각한 아이디어

• 모든 경우의 수를 다 시도하되, n이 나오면 break

1. 최대길이 = 0
2. 모든 붙어있는 쌍에 대해서 (이중반복문)
   • 만약 둘이 다르다면,
     - 서로 바꾼다
     • 모든 열과 행에 대해서 연속되는 사탕의 최대길이를 찾는다 (이중반복문)
     • 기존 최대길이와 비교하여 갱신한다 (max 함수)
       • 만약 최대길이가 n이라면, 바로 return n
       • 원래 배열대로 다시 바꾼다.
3. return 최대길이

💻 작성된 코드

import sys
# 백준에 넘길 때만 주석 풀기
# input = sys.stdin.readline
n = int(input())
arr = []
for _ in range(n):
    arr.append(list(input()))

# 최대 길이 찾는 함수, 이중 반복문
def count_max(array, n):
    maxNum = 0
    for i in range(n):
    	# 행이 바뀌면 초기화
        key = ""
        cnt = 1
        for j in range(n):
            if key != array[i][j]:
                cnt = 1
                key = array[i][j]
            else :
                cnt += 1
                maxNum = max(maxNum, cnt)
                if maxNum == n:
                    return n
                    
        # 열이 바뀌면 초기화
        key = ""
        cnt = 1
        for j in range(n):
            if key != array[j][i]:
                cnt = 1
                key = array[j][i]
            else :
                cnt += 1
                maxNum = max(maxNum, cnt)
                if maxNum == n:
                    return n
    return maxNum

def try_change(array, n):
    maxNum = 0
    
    # 모든 붙어있는 짝에 대해서 
    for i in range(n):
        for j in range(n-1):
        	# 좌우 짝이 다르면, 자리를 바꿔본다
            if array[i][j] != array[i][j+1]:
                tmp = array
                tmp[i][j], tmp[i][j+1] = tmp[i][j+1], tmp[i][j]
                maxNum = max(maxNum, count_max(tmp, n))
                if maxNum == n:
                    return n
                tmp[i][j], tmp[i][j+1] = tmp[i][j+1], tmp[i][j]
                
            # 상하 짝이 다르면, 자리를 바꿔본다.
            if array[j][i] != array[j+1][i]:
                tmp = array
                tmp[j][i], tmp[j+1][i] = tmp[j+1][i], tmp[j][i]
                maxNum = max(maxNum, count_max(tmp, n))
                if maxNum == n:
                    return n
                tmp[j][i], tmp[j+1][i] = tmp[j+1][i], tmp[j][i]
    return maxNum

print(try_change(arr,n))