글 읽기 - 시간초과(파이썬)

wbjkwjj 3년 전 0

수행시간을 더 줄일 수 있는 부분을 알려주시면 감사하겠습니다.

로직은 이렇습니다.

1-바꾸지 않은 상태에서 최댓값 체크

2-하나씩 바꾸어가며 배열이 바뀐 열 및 행에서 최댓값 체크

from sys import stdin
def check(a):#check maximum number of consecutive items in each row and column
    x=len(a)
    maxxx=0
    result=[]
    for i in range(x):
        case={}#numbers of each candy in row or column
        maxx=0
        for j in range(x):
            if a[i][j] not in case:
                case[a[i][j]]=1
            elif a[i][j] in case and a[i][j-1]==a[i][j]:
                case[a[i][j]]+=1
            else:
                case[a[i][j]]=1
        for k in case:
            if case[k]>maxx:
                maxx=case[k]
        if maxx>maxxx:
            maxxx=maxx
    for i in range(x):
        case={}#numbers of each candy in row or column
        maxx=0
        for j in range(x):
            if a[j][i] not in case:
                case[a[j][i]]=1
            elif a[j][i] in case and a[j-1][i]==a[j][i]:
                case[a[j][i]]+=1
            else:
                case[a[j][i]]=1
        for k in case:
            if case[k]>maxx:
                maxx=case[k]
        if maxx>maxxx:
            maxxx=maxx
    return maxxx
def swap1(x,y,c):#switch horizontally
    c[x][y],c[x][y+1]=c[x][y+1],c[x][y]
def swap2(x,y,c):#swtich vertically
    c[x][y],c[x+1][y]=c[x+1][y],c[x][y]
def hcheck(x,y,c):#check if horizontally switched
    case={}
    maxx=0
    for j in range(n):
        if c[x][j] not in case:
            case[c[x][j]]=1
        elif c[x][j] in case and c[x][j-1]==c[x][j]:
            case[c[x][j]]+=1
        else:
            case[c[x][j]]=1
    for k in case:
        if case[k]>maxx:
            maxx=case[k]
    case={}
    for j in range(n):
        if c[j][y] not in case:
            case[c[j][y]]=1
        elif c[j][y] in case and c[j-1][y]==c[j][y]:
            case[c[j][y]]+=1
        else:
            case[c[j][y]]=1
    for k in case:
        if case[k]>maxx:
            maxx=case[k]
    case={}
    for j in range(n):
        if c[j][y+1] not in case:
            case[c[j][y+1]]=1
        elif c[j][y+1] in case and c[j-1][y+1]==c[j][y+1]:
            case[c[j][y+1]]+=1
        else:
            case[c[j][y+1]]=1
    for k in case:
        if case[k]>maxx:
            maxx=case[k]
    return maxx
def vcheck(x,y,c):#check if vertically switched
    case={}
    maxx=0
    for j in range(n):
        if c[x][j] not in case:
            case[c[x][j]]=1
        elif c[x][j] in case and c[x][j-1]==c[x][j]:
            case[c[x][j]]+=1
        else:
            case[c[x][j]]=1
    for k in case:
        if case[k]>maxx:
            maxx=case[k]
    case={}
    for j in range(n):
        if c[j][y] not in case:
            case[c[j][y]]=1
        elif c[j][y] in case and c[j-1][y]==c[j][y]:
            case[c[j][y]]+=1
        else:
            case[c[j][y]]=1
    for k in case:
        if case[k]>maxx:
            maxx=case[k]
    case={}
    for j in range(n):
        if c[x+1][j] not in case:
            case[c[x+1][j]]=1
        elif c[x+1][j] in case and c[x+1][j-1]==c[x+1][j]:
            case[c[x+1][j]]+=1
        else:
            case[c[x+1][j]]=1
    for k in case:
        if case[k]>maxx:
            maxx=case[k]
    return maxx
c=[]
n=int(stdin.readline())
for i in range(n):
    q=list(str(stdin.readline()))
    q.remove('\n')
    c.append(q)
x=len(c)
y=len(c[0])
result=check(c)#there could be answer before switching

for i in range(x):
    for j in range(y-1):
        swap1(i,j,c)
        chec=hcheck(i,j,c)
        if chec>result:
            result=chec
        swap1(i,j,c)#swap one more time to restore 
        swap2(j,i,c)
        chec=vcheck(j,i,c)
        if chec>result:
            result=chec
        swap2(j,i,c)#swap one more time to restore

print(result)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과(파이썬)

wbjkwjj 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말