문제 베스트 앨범 문제 바로가기 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 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' 셔틀에 사람이 꽉 차지..

문제 [사이클 게임 문제 바로가기] 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 번호가 부여된 평면 상의 점 n 개가 주어지며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 매 차례 마다 플레이어는 두 점을 선택해서 이를 연결하는 선분을 긋는데, 이전에 그린 선분을 다시 그을 수는 없지만 이미 그린 다른 ..

문제 [영어 읽기 문제 바로가기] 1501번: 영어 읽기 첫째 줄에 사전에 있는 단어들의 개수 N(0 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄에 하나씩, 영어 사전에 있는 단어들이 주어진다. 각 단어의 길이는 100자를 넘지 않는다. 다음 줄에 www.acmicpc.net 혹시 인터넷을 하다가, 다음과 같은 식의 문장을 본 적이 있는가? It is itnersetnig taht pepole can raed smoe grabeld wrods. 원래의 문장은 'It is interesting that people can read some garbled words'이다. 각각의 단어들은 제일 첫 문자와 제일 끝 문자를 제외하고는 순서가 뒤섞여 있다. 한 대학에서 시행한 연구 조사 결과에..

문제 친구 네트워크 문제 바로가기 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 풀이 특정 이름이 주어졌을 때 해당 이름이 속한 그룹을 알 수 있어야 하고, 해당 그룹에 있는 이름의 개수를 파악할 수 있어야 하는 문제이다. 이름이 속한 그룹을 바로 찾기 위해서는 map를 이용할 수 있으며 해당 그룹에 있는 이름의 개수를 파악하기 위해서는 다음과 같은 방식으로 구현이 가능하다. set group[..

난이도 : 골드 5 걸린 시간 : 30분 문제 최소비용 구하기 문제 바로가기 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 풀이 다익스트라 기본 구현을 이용해서 푼다. 다익스트라 개념 바로가기 코드 #include #include #include using namespace std; int main() { // 최소비용 문제 => bfs / 그래프 탐색(다익스트라) // N 10^3이하 M 10^6 이하 // 출발, 도착, 비용 // 비용 10^6 이하 // 마지막 (출발..