[Python] 23796번. 2,147,483,648 게임

문제 링크

성능 요약

메모리: 32412 KB, 시간: 36 ms

분류

구현

 

첫 제출은 하드코딩으로 구현하여 보았다.

#1.입력
matrix=[list(map(int,input().split())) for _ in range(8)]
cmd=input()

#2.자료형 정의

#3.동작 알고리즘
'''
한줄씩 가져온다 
U: row -> matrix[0][c]~matrix[7][c]
D: row -> matrix[7][c]~matrix[0][c]
L: col -> matrix[r][0]~matrix[r][7]
R: col -> matrix[r][7]~matrix[r][0]

시작은 1부터 -> 그 다음 칸을 한칸씩 땡기기
visited를 통해 현재 칸이 합쳐졌다면 합치지 않는다
'''
def move(cmd):
    visited=[[False]*8 for _ in range(8)] #합쳐진 칸인지

    if cmd=='U':
        ys,ye,yk=1,8,1
        xs,xe,xk=0,8,1
        dy,dx=-1,0
    elif cmd=='D':
        ys,ye,yk=6,-1,-1
        xs,xe,xk=0,8,1
        dy,dx=1,0
    elif cmd=='L':
        ys,ye,yk=0,8,1
        xs,xe,xk=1,8,1
        dy,dx=0,-1
    else:
        ys,ye,yk=0,8,1
        xs,xe,xk=6,-1,-1
        dy,dx=0,1

    for y in range(ys,ye,yk):
        for x in range(xs,xe,xk):
            ny,nx=y,x #임시 변수
            while True: #이동할 수 있다면
                #범위를 벗어나면 stop
                if not (0<=ny+dy<8 and 0<=nx+dx<8):
                    break
                if matrix[ny+dy][nx+dx]==0 and matrix[ny][nx]!=0:
                    matrix[ny+dy][nx+dx]=matrix[ny][nx]
                    matrix[ny][nx]=0
                    ny+=dy
                    nx+=dx
                else:
                    break
            if 0<=ny+dy<8 and 0<=nx+dx<8:
                if matrix[ny+dy][nx+dx]>0 and matrix[ny][nx]>0 and (matrix[ny+dy][nx+dx]==matrix[ny][nx]):
                    if not visited[ny+dy][nx+dx]:
                        matrix[ny+dy][nx+dx]*=2
                        matrix[ny][nx]=0
                        visited[ny+dy][nx+dx]=True

    return matrix

nmatrix=move(cmd)

#4.출력
for nm in nmatrix:
    print(*nm)

근데 이렇게 풀고 나니 너무 하드코딩인 것 같아 다른 방법이 있는지 GPT에게 물어봤다.

GPT한테 물어보고 다른 방법을 알고 나니 진짜 왜 이런 생각을 못했는지 조금 바보 같긴 했다.

 

행/열 단위로 처리하는 방법

1. 0 제거
2. 인접 같은 수 합치기
3. 빈 자리는 0 채우기

예시

line=[2, 0, 2, 4, 0, 4, 4, 0]

# 1) 0 제거 (압축)
arr1=[2,2,4,4,4]

# 2) 병합
arr2=[4,8,4]

# 3) 0 채우기
arr+=[0]*(N-len(out))

# 결과
# [4,8,4,0,0,0,0,0]

 

코드 과정

def merge_line(line):
	# 1) 0 제거
    arr=[x for x in line if x!=0]
    
    # 2) 병합
    i=0
    while i<len(arr):
    	if i+1<len(arr) and arr[i]==arr[i+1]:
        	out.append(arr[i]*2)
            i+=2
        else:
        	out.append(arr[i])
            i+=1
    
    # 3) 0 채우기
    out+=[0]*(N-len(out))
    
    return out

개선된 코드

#1.입력
matrix=[list(map(int,input().split())) for _ in range(8)]
cmd=input()

#2.자료형 정의

#3.동작 알고리즘
def merge_line(line):
    # 1) 0 제거
    arr=[x for x in line if x!=0]

    # 2) 병합
    res=[]
    i=0
    while i<len(arr):
        if i+1<len(arr) and arr[i]==arr[i+1]:
            res.append(arr[i]*2)
            i+=2
        else:
            res.append(arr[i])
            i+=1

    # 3) 0 채우기
    res+=[0]*(8-len(res))

    return res

def move(cmd):
    if cmd=='L':
        for r in range(8):
            print(*merge_line(matrix[r]))
    elif cmd=='R':
        for r in range(8):
            print(*reversed(merge_line(reversed(matrix[r]))))
    elif cmd=='U':
        col=list(zip(*matrix))
        new_cols = zip(*[merge_line(col) for col in zip(*matrix)])
        for row in new_cols:
            print(*row)
    else:
        col=list(zip(*matrix))
        new_cols = zip(*[
            list(reversed(merge_line(list(reversed(col)))))
            for col in zip(*matrix)
        ])
        for row in new_cols:
            print(*row)

#4.출력
move(cmd)

 

근데 메모리면이나 시간면에서는 위에 첫번째 하드코딩과 같긴하였다.

위가 개선된 코드, 아래가 첫 번째 코드

 

이런,, 구현 문제를 풀 때마다 늘 마음 한편에는

이런 생각이 들긴한다,,,,

내가 한참을 생각해도 안 풀리거나 엄청난 노가다로 푼 문제를 너무 간단하고 신박한 풀이로 풀어버리는 사람들을 보면 좀 많이 현타가 오긴한다. 근데 한편으로는! 운 좋으면 풀 수 있으니까! 또 그런 생각이 들기도 하고,,,

그냥 코테를 치는 그날 머리가 잘 돌아가고 무식하게 뚝딱뚝딱 풀릴 그런 문제이길 바랄 수 밖에,,,

구현의 최고봉,,,은 삼성 코테인데ㅜㅜ 할 수 있을까ㅜㅜ