백준 3085번(사탕게임) 파이썬

 

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

3085번: 사탕 게임

문제를 보자마자 "아 이거 완탐인데?" 하고 알고리즘 분류를 보니까 완탐이 맞았다.

여담인데 문제를 보고 어떤 유형의 알고리즘을 써야하는지 파악하는거도 코테 볼때 매우 중요한 부분이라고 생각한다.

문제 자체는 완탐이라 접근 방법은 알았지만 코드 구현이 빡셀거 같았다.

역시나 '시간초과'가 떠버렸다. 이후 오랜 고민을 해봤지만 더 이상이 시간을 끌면 안될 거 같아 정답코드를 봤다.

내가 생각하지 못한건 행이 아닌 열을 검사할때 기존에 있던 for문으로 가면 됐지만 그러지 못하고 새로 for문을 또 만들어 

삼중for문을 만들어 버렸다. 아마 여기서 시간 초과가 난거 같다. 상당이 빡센 문제였다.

 

<오류 코드(내 코드)>

import sys
input = sys.stdin.readline

n = int(input())
candyList = []
for _ in range(n):
    candyList.append(list(input()))
maxCandy = 0
cnt=0
def check():
    global maxCandy
    for i in range(n):
        for j in range(n):
            cnt = 0
            if maxCandy < candyList[i].count(candyList[i][j]):
                maxCandy = candyList[i].count(candyList[i][j])
            for k in range(n):
                if candyList[i][j] == candyList[k][j]:
                    cnt += 1
            if maxCandy < cnt:
                maxCandy = cnt
        

for i in range(n):
    for j in range(n):
        if j+1 < n:
            candyList[i][j], candyList[i][j+1] = candyList[i][j+1], candyList[i][j]
            check()
            candyList[i][j], candyList[i][j+1] = candyList[i][j+1], candyList[i][j] 
        if i+1 < n:
            candyList[i][j], candyList[i+1][j] = candyList[i+1][j], candyList[i][j]
            check()
            candyList[i][j], candyList[i+1][j] = candyList[i+1][j], candyList[i][j] 

print(maxCandy)

위의 코드는 시간초과가 난 코드이다.

 

<정답 코드>

import sys
input = sys.stdin.readline

n = int(input())
candyList = [list(input()) for _ in range(n)]
maxCandy = 0

def check():
    global maxCandy
    for i in range(n):
        cnt = 1
        #행 탐색
        for j in range(1,n):
            if candyList[i][j] == candyList[i][j-1]: # 행으로 연속되는 요소가 있을경우
                cnt+=1
                maxCandy = max(cnt,maxCandy)
            else:
                cnt=1
           
        cnt=1
        #열 탐색
        for j in range(1,n):
            if candyList[j][i] == candyList[j-1][i]:# 열로 연속되는 경우가 있을경우
                cnt+=1
                maxCandy = max(cnt,maxCandy)
            else:
                cnt = 1
            
        

for i in range(n):
    for j in range(n):
        if j+1 < n:
            #오른쪽꺼와 변겅
            candyList[i][j], candyList[i][j+1] = candyList[i][j+1], candyList[i][j]
            #검사
            check()
            # 원위치 시킨다
            candyList[i][j], candyList[i][j+1] = candyList[i][j+1], candyList[i][j] 
        
        if i+1 < n:
            #아래쪽꺼와 변경
            candyList[i][j], candyList[i+1][j] = candyList[i+1][j], candyList[i][j]
            #검사
            check()
            #원위치 시킨다
            candyList[i][j], candyList[i+1][j] = candyList[i+1][j], candyList[i][j] 

print(maxCandy)

열 탐색 부분이 저렇게도 작동 될거라는걸 생각을 못했다.

좋은 문제였던거 같다.