본문 바로가기

Algorithm/Programmers93

[2018 카카오 기출] 셔틀버스 시뮬레이션 문제입니다. 버스를 객체로 만든 후, 벡터로 관리해줍니다. 그리고 콘을 제외한 나머지 승객들이 버스를 탄 상황을 셋팅해줍니다. 두 가지 경우로 답을 나눌 수 있을 것입니다. 1. 버스를 탈 수 있는 경우 → 그냥 마지막에 온 빈 버스에 타면 됩니다. 2. 버스를 탈 수 없는 경우 → 콘이 봐야할 거는 한 가지입니다. 마지막 버스에 탄, 마지막 승객만 이기면 됩니다. 그 승객보다 1분만 먼저 타면 그게 정답이 됩니다. 2020. 5. 9.
[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.

티스토리툴바