“괜찮아! 아직 코딩테스트까지 3일이나 남았어” 프로젝트 (3)

SoniaComp

·

Follow

2 min read

·

Apr 2, 2021

--

Share

2020 카카오 블라인드 테스트

1. 문자열 압축
2. 괄호 변환
3. 자물쇠와 열쇠
4. 기둥과 보 설치
5. 외벽점검
6. 블록 이동하기

공식해설

문제

문제 분해

• 로봇이 이동할 수 있는 방법은 두 가지이다.
  → 오른쪽 이동
  → 아래쪽으로 이동 — 아래로 이동, 회전하여 세로

자료표현

• (count, [가로 or 세로]) 이런 식으로 저장해서 counting

일반화

• 완전 탐색 문제!
• queue에 경로를 넣고, BFS처럼 풀어보자!

구현

틀린 답

• 예제 케이스는 맞았지만 테스트 케이스에서 정확도가 0이다. 예제 케이스에 과적합한 논리로 풀었던 것 같다.
• 위에 내가 처음 생각한 논리는 보면, 오른쪽 이동, 회전 두가지이지만, 실제로는 더 많다. → 상하좌우 이동, 회전

맞는 답

• BFS로 할 때는, 다익스트라와 다르게, 기존 값과 대소비교해주지 않아도 된다. 왜냐하면 나중에 접근하는 노드는 항상, 최초 접근 노드보다 접근 시간이 많기 때문에 비교해주지 않아도 된다.
  → 탐색했는지 여부: set으로 확인
• padding을 통해서 외벽을 쌓아준다. → 이렇게 할 경우, 끝에 도달했는지 여부를 체크하지 않아도 돼서, 수행시간이 줄어든다.