알고리즘 문제 오답 노트

오답 노트

• 알고리즘 문제를 풀며 틀린 원인 분석 및 새로 알게된 부분 정리 
• 코딩 테스트 전 한번 보고 갈만한 노트

---

1. 출력값에 % 10 (마지막 자리 수만 출력) 을 요구할 때는 

   조건을 모두 고려해서 계산 후 최종 값에 % 10 계산 필요 

   ex) 백준 16946 벽 부수고 이동하기 4 : 틀렸습니다 -> 맞았습니다

2. 배열 크기가 너무 크면 배열 초기화에도 시간이 걸림

   아래 코드 주석 부분 (방문 확인을 위해 checked 배열 사용) 을 set 으로 변경하여 시간 초과 해결

   ex) 백준 16946 벽 부수고 이동하기 4 : 시간초과 -> 맞았습니다

# count the number of grids can be moved
can_move = [[0] * M for _ in range(N)]
for i in range(N):
    for j in range(M):
        if jido[i][j]==1:
            can_move[i][j] = 1
            # checked = [False] * len(zero_grouping)
            checked = set()
            for dx, dy in move:
                nx = j + dx
                ny = i + dy
                if 0<=ny<N and 0<=nx<M and jido[ny][nx]!=1:# and not checked[jido[ny][nx]-2]:
                    # cnt += zero_grouping[jido[ny][nx]]
                    # checked[jido[ny][nx]-2] = True
                    checked.add(jido[ny][nx])
            
            # can_move[i][j] = cnt % 10
            for x in checked:
                can_move[i][j] += zero_grouping[x]
                can_move[i][j] %= 10