[코드트리 챌린지] 1주차 - 격자 안에서 여러 객체를 이동

한 달 반만에 300점 향상!!

대략 한 달 반 동안 매일매일 꾸준히 코딩테스트 문제를 한 문제 이상 풀었다.

(방학이라 시간을 내서 풀 수 있었다. 이제 개학해서 아마 일주일에 한 문제 정도 풀 것 같다..ㅎㅎ) 

실력 진단 테스트를 통해 실력이 얼마나 향상됐는지 확인할 수 있을뿐만 아니라,

내가 잘하는 부분과 부족한 부분을 알 수 있어서 좋았다.

 

실력 진단 당시 완전탐색은 2문제 빼고 다 푼 상태이고 dfs, bfs는 50%가량 푼 상태였는데,

그래서였는지 완전탐색은 잘 풀어나갔고 dfs, bfs 부분에서는 막혔다.

  사실 이번에 실력 진단을 하기 전까지는 50%가량만 풀어도 충분하지 않을까?라고 생각했었는데,

최소 90% 이상은 풀어야 체화할 수 있는 것 같다.

코드트리 학습 커리큘럼의 문제수가 딱 적절하게 구성되어 있었던 것이다..!

 

벽이 없는 충돌 실험

문제 링크: https://www.codetree.ai/missions/2/problems/collision-experiment-without-wall?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

이 문제는 내가 유일하게 일주일동안 끙끙 싸맸던 문제다.

보통 다른 문제는 그래도 2일 안에는 풀렸는데, 일주일이나 걸린 문제는 처음이다.

메모리 초과로 인해서 테스트케이스를 통과하지 못했는데,

원인과 이를 해결한 방법에 대해 얘기해보겠다.

COORD_SIZE = 4000
BLANK = -1

T = int(input())  # 테스트 케이스 수
dtoN = {'U': 0, 'D': 1, 'L': 2, 'R': 3}
dis, djs = [-1, 1, 0, 0], [0, 0, -1, 1]

next_marble_index = [
    [BLANK for _ in range(COORD_SIZE + 1)]
    for _ in range(COORD_SIZE + 1)
]

for _ in range(T):
    marbles = []
    N = int(input())  # 구슬 개수
    for num in range(1, N+1):
        x, y, w, d = tuple(input().split())
        i, j, w, dNum = (-int(y)) * 2 + 2000, int(x) * \
            2 + 2000, int(w), dtoN[d]
        marbles.append((num, i, j, w, dNum))

    colT = -1

    def in_range(i, j):
        return i >= 0 and i < COORD_SIZE + 1 and j >= 0 and j < COORD_SIZE + 1

    for t in range(1, COORD_SIZE + 1):
        next_marbles = []
        # 이동
        for marble in marbles:
            num, i, j, w, dNum = marble
            new_i, new_j = i + dis[dNum], j + djs[dNum]
            if in_range(new_i, new_j):
                if next_marble_index[new_i][new_j] == BLANK:
                    next_marbles.append((num, new_i, new_j, w, dNum))
                    next_marble_index[new_i][new_j] = len(next_marbles) - 1
                else:
                    colT = t
                    # 무게가 크면
                    if next_marbles[next_marble_index[new_i][new_j]][3] < w:
                        next_marbles[next_marble_index[new_i][new_j]] = (
                            num, new_i, new_j, w, dNum)
                    # 무게가 같고 번호가 크면
                    elif next_marbles[next_marble_index[new_i][new_j]][3] == w and next_marbles[next_marble_index[new_i][new_j]][0] < num:
                        next_marbles[next_marble_index[new_i][new_j]] = (
                            num, new_i, new_j, w, dNum)

        marbles = next_marbles[:]

        # 다음 수행을 위한 초기화
        for marble in next_marbles:
            next_marble_index[marble[1]][marble[2]] = BLANK

    print(colT)

위는 내가 해설을 참고해 작성한 테스트케이스를 통과한 정답 코드이다.

해설과 다른 점은 함수화해서 작성하지 않은 것이다.

 

에러를 해결한 방법은 next_marble_index를 전역변수로 선언하고 매초마다 초기화가 필요한 인덱스만 초기화해준 것이다. 처음에는 for t in range 반복문 안에서 next_marble_index 변수를 선언과 동시에 매초마다 전부 초기화해주었다. 아무래도 next_marble_index가 4001 x 4001 크기의 2차원 리스트이다 보니, 무리가 되었던 것 같다.

 

따라서 next_marble_index를 전역변수로 선언해주고, next_marbles에 저장된 t초 뒤 구슬들의 위치 정보를 이용하여 구슬이 이동한 자리만 다시 초기화해 주었다.