Problems/Programmers (6) 썸네일형 리스트형 보석 쇼핑 (카카오 인턴 2020 기출) 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/67258?language=python3 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 진열된 순서대로 보석의 이름이 저장된 list가 매개변수로 주어질 때, 모든 종류의 보석을 1개 이상 포함하는 가장 짧은 구간을 반환하는 문제였습니다. (가장 짧은 구간이 여러 개 있다면 구간의 시작점이 가장 왼쪽에 있는 경우를 반환합니다.) 이번 문제에는 정확성 테스트와 효율성 테스트가 별개로 존재합니다. 1) 모든 경우를 탐색할 경우 진열된 보석의 정보가 저장된 .. 길 찾기 게임 문제 링크 : programmers.co.kr/learn/courses/30/lessons/42892?language=python3 이진 트리를 구현하고 그 안에서 전위 순회와 후위 순회를 다시 구현하는 방식으로 문제를 해결했습니다. 전위 순회는 금방 떠올릴 수 있었는데 후위 순회를 고려하느라 많이 헤맸습니다. 입력으로 주어지는 node의 최대 깊이가 1000인 것을 고려할 때, 배열로 이진 트리를 구현하는 것은 메모리 낭비가 심할 것으로 생각하고 번호, x값, leftNode, rightNode를 property로 갖는 Node class를 생성했습니다. 완전 이진 트리가 아니므로 leaf node가 아닌 모든 node가 leftNode와 rightNode를 가질 필요는 없습니다. 문제의 조건 중 임의.. 오픈채팅방 문제 링크 : programmers.co.kr/learn/courses/30/lessons/42888?language=python3 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 도중에 닉네임을 변경하는 경우가 생길 수 있기 때문에, 주어진 records의 순서대로 result를 바로 만들 수는 없습니다. 모든 유저를 [유저 아이디]로 구분한다는 점에 착안해서 [유저 아이디]를 key로 가지고 [닉네임]을 value로 갖는 Dictionary를 이용하여 문제를 해결할 수 있습니다. 먼저 records를 앞에.. 외벽 점검 문제 링크 : programmers.co.kr/learn/courses/30/lessons/60062?language=python3 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하 programmers.co.kr 외벽의 길이가 n, 취약 지점의 위치가 weak, 각 친구가 이동할 수 있는 거리가 dist로 각각 주어집니다. 외벽이 원형으로 이루어졌기 때문에 길이가 100인 벽에서 지점 0과 지점 90까지의 최단 거리는 10입니다. p1 >= p2일 때, dis = min(p1 - p2, p2 - p1 + n)이 성립합니다. 친구가 투입되는 .. 가사 검색 문제 링크 : programmers.co.kr/learn/courses/30/lessons/60060?language=python3 코딩테스트 연습 - 가사 검색 programmers.co.kr 가사(words)의 최대 개수가 100,000개, 검색 키워드(queries)의 최대 개수가 100,000개이므로 모든 검색 키워드에 대해서 가사와 비교하면 많은 시간이 소요됩니다. 효율적인 검색을 위해 Trie 자료 구조를 이용했습니다. Trie는 여러 문자열을 저장하고 있고 입력으로 임의의 문자열이 주어졌을 때 Trie에 포함된 것인지 빠르게 확인할 수 있습니다. 찾고자 하는 문자열의 길이가 m이라면 Trie는 O(m) 만큼의 시간복잡도를 갖습니다. 입력으로 주어지는 가사(words)의 각 문자를 '?'로 치.. 괄호 변환 문제 링크 : programmers.co.kr/learn/courses/30/lessons/60058?language=python3 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 programmers.co.kr 문제에서 문자열을 변환하는 방법에 대해 상세하게 설명하고 있으므로 착실하게 구현하면 해결할 수 있습니다. 문자열이 "올바른 문자열"이 아니라면 재귀적으로 변환하는 구조이므로 재귀 함수를 사용하여 구현했습니다.(recurvise 함수) 문자열 p가 "균형잡힌 문자열"로 주어지므로 일일이 문자열의 마지막까지 괄호의 수를 확인해줄 필요는 .. 이전 1 다음
