프로그래머스 - 공이동 시뮬레이션

월간 챌린지에서 3번 문제로 나왔었던 문제였다.

def solution(n, m, x, y, queries):
	# 가로 체크
    leftEnd, rightEnd = 0, m-1
    leftEndAmount, rightEndAmount = 1, 1
    canAddValue = True
    
    # Y가 앞에 붙은 변수들은 세로 체크를 위한 것
    YleftEnd, YrightEnd = 0, n-1
    YleftEndAmount, YrightEndAmount = 1, 1
    YcanAddValue = True
    
    for orderNum, amount in queries:
        if orderNum == 0:
            leftEnd -= amount
            rightEnd -= amount

            if leftEnd < 0:
                if canAddValue:
                    leftEndAmount -= leftEnd
                leftEnd = 0
            if rightEnd < 0:
                if canAddValue:
                    rightEndAmount -= rightEnd
                rightEnd = 0
            # 둘이 같으면 모든 공이 한곳에 모였으니 공의 Amount가 변할 수 없음. 그러니 False로 세팅
            if rightEnd == leftEnd:
                rightEndAmount = leftEndAmount
                canAddValue = False

        elif orderNum == 1:
            leftEnd += amount
            rightEnd += amount
            if leftEnd >= m:
                if canAddValue:
                    leftEndAmount += leftEnd - (m-1)
                leftEnd = m-1
            if rightEnd >= m:
                if canAddValue:
                    rightEndAmount += rightEnd - (m - 1)
                rightEnd = m-1
            if rightEnd == leftEnd:
                leftEndAmount = rightEndAmount
                canAddValue = False

        elif orderNum == 2:
            YleftEnd -= amount
            YrightEnd -= amount

            if YleftEnd < 0:
                if YcanAddValue:
                    YleftEndAmount -= YleftEnd
                YleftEnd = 0
            if YrightEnd < 0:
                if YcanAddValue:
                    YrightEndAmount -= YrightEnd
                YrightEnd = 0
            if YrightEnd == YleftEnd:
                YrightEndAmount = YleftEndAmount
                YcanAddValue = False

        elif orderNum == 3:
            YleftEnd += amount
            YrightEnd += amount
            if YleftEnd >= n:
                if YcanAddValue:
                    YleftEndAmount += YleftEnd - (n-1)
                YleftEnd = n-1
            if YrightEnd >= n:
                if YcanAddValue:
                    YrightEndAmount += YrightEnd - (n - 1)
                YrightEnd = n-1
            if YrightEnd == YleftEnd:
                YleftEndAmount = YrightEndAmount
                YcanAddValue = False


    X, Y = 0, 0
    if leftEnd == rightEnd:
    	# 모든 공이 한곳에 모였는데 그게 찾는 목적지면
        if y == leftEnd:
            X = m
    else:
    	# 왼쪽 끝과 오른쪽 끝을 제외한 사이에는 모두 공 1개씩임
        if leftEnd == y:
            X = leftEndAmount
        elif rightEnd == y:
            X = rightEndAmount
        elif leftEnd < y < rightEnd:
            X = 1

    if YleftEnd == YrightEnd:
        if x == YleftEnd:
            Y = n
    else:
        if YleftEnd == x:
            Y = YleftEndAmount
        elif YrightEnd == x:
            Y = YrightEndAmount
        elif YleftEnd < x < YrightEnd:
            Y = 1
    print(f'{leftEnd} : {leftEndAmount}, {rightEnd} : {rightEndAmount}')
    print(f'{YleftEnd} : {YleftEndAmount}, {YrightEnd} : {YrightEndAmount}')
    return X*Y

챌린지 풀때는 효율땜에 못풀었는데 왼쪽끝과 오른쪽 끝만 체크하니 34ms 내에 모두 풀렸다. 코드가 좀 길어서 줄일 방법은 없을까 고민해봤지만 아직은 잘 모르겠다. 중복이 많아서 알아보기는 쉬워 다행이다.

해결 아이디어

공을 일렬로 놓고 왼쪽 오른쪽으로 밀어대면 양 끝 부분만 찌그러진다고 상상해보자

양끝을 제외한 가운데는 모두 한칸에 공 1개씩만 있을 것이다. 그러니 양 끝에만 집중하면 된다. 가로 세로를 나눠서 생가하고 모든 query가 끝났을때 왼쪽과 오른쪽 끝의 위치들은 어떻게 되어있는지 생각해보면 된다. 가능한 케이스는 다음과 같을 것이다.

 

** n = 10 일때

1) 한곳으로 몰리지 않은 경우

3 1 1 5 0 0 0 0 0 0

2) 한곳으로 몰린경우

0 0 0 0 0 10 0 0 0 0

 

https://programmers.co.kr/learn/courses/30/lessons/87391

코딩테스트 연습 - 공 이동 시뮬레이션