본문 바로가기

전체 글361

[2018 카카오 기출] 자동완성 트라이 자료 구조로 해결할 수 있는 문제입니다. 탐색을 O(L)에 할 수 있습니다. 먼저 입력받은 문자열에 대해 트라이를 만들고, 다시 한 번 더 순회하면서 정답을 구하면 됩니다. 트라이는 상태정보로 child를 가지고 있습니다. 특정 노드에 있는 알파벳이 insert 메서드에 호출될 때 마다 child += 1을 해줍니다. 즉, 자신이 완성된 뒤에도 누군가 자신을 호출했다면 그 단어는 자신과 자식관계가 되는 셈입니다. 자동완성 기능을 통해 더 이상 탐색을 안해도 되는 경우는 현재 탐색하는 알파벳에서 남은 문자열이 하나밖에 없는 경우이고, 그 때 child 값은 1입니다. 그래서 그 높이까지 탐색하도록 find 함수를 작성하면 됩니다. 2020. 5. 8.
[2019 카카오 기출] 징검다리 건너기 스톤 배열 크기를 N이라 했을 때 정렬을 수행하고 선형탐색을 통해 건너려고 하면 O(N^2)이 되어 시간초과가 나게 됩니다. 결국 특정 높이에 대한 탐색을 O(N)이 아닌, O(logN)에 해야하므로 이분 탐색으로 접근해볼수 있습니다. 통과한 니니즈 친구들의 수를 F라고 했을 때, 각 돌은 F만큼 높이가 감소합니다. 이 감소한 높이로 인해 연속으로 0이 되는 돌의 개수가 K이상이면 더 이상 친구들은 지나갈 수 없습니다. 그래서 특정 인원 수 M명이 지나간 후에 디딤돌을 더 지날 수 있는지 없는지를 파악해서 이 M값의 상한선을 구하면 그게 답이 됩니다. 2020. 5. 6.
[2019 카카오 기출] 불량 사용자 배열 크기 제한이 크지 않으므로 팩토리얼로 경우의 수를 생성해도 시간초과가 나지 않습니다. user_id 목록을 next_permutation을 통해 모든 경우의 수를 생성해주고, 이를 banned_id 와 비교해줍니다. 포함되는 경우의 수는 비트연산자 & set을 통해 특정 상태 나타내는 하나의 수를 set에 저장하였습니다. set에 들어있는 수는 banned_id 리스트와 일치하는 user_id의 유일한 목록을 나타내므로 set에 들어가있는 원소의 수가 정답이 됩니다. 2020. 5. 6.
[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.

티스토리툴바