본문 바로가기

Algorithm/programmers42

2019 카카오 개발자 겨울 인턴쉽 - 호텔 방 배정(경로 압축) - Java 풀이 https://programmers.co.kr/learn/courses/30/lessons/64063 코딩테스트 연습 - 호텔 방 배정 programmers.co.kr - 방의 갯수가 최대 1e12 1조이고, 고객들이 요청하는 방 갯수는 20만이다. 고객들이 요구한 번호의 방 혹은 번호가 크면서 비어있는 방 중 가장 번호가 작은 방이라는 조건이 있기 때문에 해시맵으로 사용된 방과 사용할 수 있는 그 다음 방을 해쉬맵에 기록하는 방식으로 접근하였다. - 방을 길이 k의 1차원배열로 생각했을 때 방 정보를 업데이트 할 때마다 해당 방의 오른쪽으로 연결되어있는 방들에 대하여 다음 제공할 수 있는 방 정보에 대해 경로압축을 해놓으면 사용가능한 다음 방을 logM 혹은 a(M)안에 찾을 수 있다.(M은 시작지점으.. 2022. 3. 28.
2019 카카오 개발자 겨울 인턴쉽 - 불량 사용자(순열, 해시, 정규표현식) - Java 풀이 https://programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr - user_id와 banned_id 원소가 1대1 매칭이 되어야 한다. 그래서 처음에는 banned_id 각각에 해당될 수 있는 경우의 수를 모두 세는 것으로 접근하였다가 중복처리를 하기가 힘들었다. - user_id 갯수가 8 이하이기 때문에 banned_id의 갯수만큼 순서대로 뽑으면서 중복을 허락하지 않는 순열을 만들어도 최대 8P4 밖에 안되기 때문에.. 2022. 3. 28.
2019 카카오 개발자 겨울 인턴쉽 - 튜플(문자열 파싱, 구현 ) - Java 풀이 https://programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr - 변수 제한사항 범위가 좁아서 딱히 복잡도 걱정을 안하고 푼 문제이다. 실무에서도 JSON 파싱 등을 할 때 종종 쓸만한 방법인 것 같다. },{ 단위로 쪼개는 String.split(String regex) 함수를 쓰려고 정규표현식을 한번 복습했다. 정규표현식에서 중괄호가 앞 문자의 반복을 나타내는 특수문자.. 2022. 3. 28.
2022 Kakao blind 92343 - 양과 늑대(트리, 백트래킹 or dp) - Java, C++ 풀이 https://programmers.co.kr/learn/courses/30/lessons/92343 코딩테스트 연습 - 양과 늑대 [0,0,1,1,1,0,1,0,1,0,1,1] [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] 5 [0,1,0,1,1,0,1,0,0,1,0] [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]] 5 programmers.co.kr - 방문한 노드를 또 방문할 수 있고 노드의 갯수 n = 17이기 때문에 17^17 완전탐색을 할 수 없다. 방문한 노드는 다시 방문하지 않으면서 현재 노드에서 방문가능한 노드를 메모이제이션 하면서 재귀적으로 방문.. 2022. 3. 24.

티스토리툴바