문제 베스트 앨범 문제 바로가기 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 풀이 우선 알아내야 할 것은 다음과 같다. 장르의 총 재생 횟수 -> 장르 순위 정하기 각 장르의 개별 곡 재생 횟수 -> 곡 순위 정하기 이걸 한 번에 알아내려고 하면 장르를 key로 두고 있는 map에 value로 (총 재생 횟수, index마다의 재생횟수)을 저장해두어야 하고 이러면 장르의 순위를 알아내기 힘들 뿐만 아니라 곡 순위도 추출해서 나타내야 한다. 따라서 map을 두개로 나누었다. 1번 map은 { key : 장..

문제 전화번호 목록 문제 바로 가기 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 풀이 보자마자 트라이(Trie)가 생각났다. 문자열 길이도 20 이하이니 최대 높이가 20인 트리를 만들면 될 것 같다. 하지만 연결리스트 구현이 너무 귀찮기도 하고, 입력의 범위가 10^6이라 O(nlgn) 이하로 한 번에 해결할 수 있는 쉬운 방법이 있지 않을까 생각했다. 정렬되어 있는 phone_book을 한 번에 훑으면 등장했던 문자열을 포함하고 있는 지를 확인하면 되는데, 일반적으로 등장했던 모든 문자열을 다시 순..

문제 불량 사용자 문제 바로가기 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr 풀이 처음에는 제재 아이디 당 몇 가지의 경우의 수가 가능한 지 계산하려고 했으나, 이렇게 한다면 기존에 제재 아이디에 걸린 아이디는 다시금 판단하면 안되는 등 생각해야 할 문제가 많아지므로 아래의 방법을 사용한다. 제재 아이디와 매칭되는 아이디를 찾을때마다 dfs로 돌면서 모든 제재 아이디에 매칭되는 경우의 수를 찾으면 된다. 입력의 범위가 작아서 시간복잡도는 문제 없다. 더해서 순열이 아니라 조합이므로 순서에 관계없이 하나의 ..

문제 셔틀버스 문제 바로가기 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 ["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"] "18:00" programmers.co.kr 풀이 셔틀이 출발하는 시간을 다 구한다. 사람들의 timetable을 오름차순으로 정렬한다. 각 셔틀에 탈 수 있는 사람(셔틀 시간보다 작거나 같은 사람)을 구한다. 이 때, 콘이 해당 셔틀에 탈 수 있기 위한 최후의 시간을 구해놓는다. 최후의 시간은 셔틀에 사람이 꽉 찰 경우 '가장 큰 시간 - 1' 셔틀에 사람이 꽉 차지..

문제 문제 설명 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다. 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요. 제한사항 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다. money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다. 풀이 만약 완전탐색으로 하고자 했다면? 반복을 index 0부터 n-1까지 돌면서 해당 집에서 시작해서 나타나는 최대의 money를 구할 수 있음 하지만 index 2를 고른다면, 집의 개수..

합승 택시 요금 난이도 : ★★★☆☆ 걸린 시간 : 못 풀었음 문제 합승 택시 요금 링크 해설 그래프 최단 경로 알고리즘 dijkstra나 floyd-warshal 알고리즘 이용 플로이드 와샬 알고리즘 모든 정점 => 모든 정점 최단 경로 구하기 d[i][j] = i부터 j까지의 최저 택시 요금 min(d[s][k]+d[k][a]+d[k][b])를 구하면 됨 다익스트라 알고리즘 한 정점 => 모든 정점 최단 경로 구하기 배열(dist)과 우선순위 큐(qp)를 이용해서 첫 정점부터 각 노드까지의 거리를 배열에 업데이트하는 방식 우선순위 큐에 다음 갈 수 있는 노드들을 넣으면서 해당 거리를 dist 배열에서 갱신하는 방식 a, b 각각의 최단 거리 비용과 특정 지점까지의 최단 거리 비용 중 가장 작은 것을 ..

메뉴 리뉴얼 난이도 : ★★☆☆☆ 걸린 시간 : 50분 문제 메뉴 리뉴얼 문제 바로가기 문제 설명 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 스카피는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다. 단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다. 예를 들어, 손님 6명이 주..

신규 아이디 추천 난이도 : ★☆☆☆☆ 걸린 시간 : 30분 => 반성! 문제 신규 아이디 추천 문제 바로가기 문제 설명 카카오에 입사한 신입 개발자 네오는 카카오계정개발팀에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. 네오에게 주어진 첫 업무는 새로 가입하는 유저들이 카카오 아이디 규칙에 맞지 않는 아이디를 입력했을 때, 입력된 아이디와 유사하면서 규칙에 맞는 아이디를 추천해주는 프로그램을 개발하는 것입니다. 다음은 카카오 아이디의 규칙입니다. 아이디의 길이는 3자 이상 15자 이하여야 합니다. 아이디는 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.) 문자만 사용할 수 있습니다. 단, 마침표(.)는 처음과 끝에 사용할 수 없으며 또한 연속으로 ..