본문 바로가기

Algorithm/Programmers93

[2020 카카오 기출] 자물쇠와 열쇠 시뮬레이션 문제입니다. M, N 제한이 작으므로 2*M +N 크기의 2차원 배열을 생성한 뒤 배열 한 가운데에 LOCK 정보를 입력합니다. 그리고 나서 (0,0) 좌표부터 ~ (M + N -1, M + N -1) 좌표를 시작점으로 KEY를 LOCK과 비교해봅니다. 0도, 90도, 180도, 270도로 형태를 바꿔가면서 (2*M + N) * 2*M + N) 배열을 전부 탐색해도 시간초과가 나지 않습니다. 한 가지 유의할 점은, LOCK과 KEY가 아닌 나머지 배열 칸들은 0/1이 아닌 값으로 구별해줘야 KEY과 LOCK 둘 사이의 관계를 제대로 비교할 수 있습니다. 2020. 5. 6.
[2019 카카오 기출] 호텔 방 배정 [문제 해설: https://tech.kakao.com/2020/04/01/2019-internship-test/] 문제 해설을 보고 해결한 문제입니다. 구현 시 중요한 부분은 두 가지 입니다. 1. 링크드 리스트와 비슷한 자료구조로, 노드가 생성될 때 자신의 번호 + 1를 부모노드로 가지도록 만들어줍니다. 2. 자신의 부모 노드 번호를 찾기 위해 find 함수를 구현 시 O(K)가 아닌 O(log(K))만에 탐색하도록 구현해줘야 합니다. 2020. 5. 6.
[2019 카카오 기출] 블록 게임 시뮬레이션 문제입니다. 중요한 것은 12개의 블록 중 검은 블록을 떨어뜨려 파괴할 수 있는 블록의 가짓 수는 5가지입니다. 이 5가지 형태의 블록에 대해서만 계속 파괴할 수 있는지 루프를 돌아주면 됩니다. 종료조건은 후보 블록들중 아무것도 파괴할 수 없을 때 입니다. 블록을 파괴할 때는 BFS를 써주면 손 쉽게 블럭을 파괴할 수 있습니다. 2020. 5. 4.
[2018 카카오 기출] 방금 그 곡 1st. 문자열 파싱 (# 제거하기) 2nd. 재생시간 계산을 통한 FULL STRING 구하기 3rd. 정답 구하기 4th. 정답이 여러 개라면 재생시간이 긴 순서대로, 입력순서가 빠른 순서대로 정렬하고 맨 앞에 있는 값을 취하면 됩니다. 본인의 경우 아래처럼 문자열을 파싱하여 유일한 문자열을 받았습니다. A# ▶▶ H C# ▶▶ I D# ▶▶ J F# ▶▶ K G# ▶▶ L 2020. 5. 4.

티스토리툴바