문제 베스트 앨범 문제 바로가기 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 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 개가 주어지며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 매 차례 마다 플레이어는 두 점을 선택해서 이를 연결하는 선분을 긋는데, 이전에 그린 선분을 다시 그을 수는 없지만 이미 그린 다른 ..

문제 [앱 문제 바로가기] 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 현재 N개의 앱, A1, ..., AN이 활성화 되어 있다고 가정하자. 이들 앱 Ai는 각각 mi 바이트만큼의 메모리를 사용하고 있다. 또한, 앱 Ai를 비활성화한 후에 다시 실행하고자 할 경우, 추가적으로 들어가는 비용(시간 등)을 수치화 한 것을 ci 라고 하자. 이러한 상황에서 사용자가 새로운 앱 B를 실행하고자 하여, 추가로 M 바이트의 메모리가 필요하다고 하자. 즉, 현재 활성화 되어 있는 앱 A1, ..., AN 중에서 몇 개를 비..

문제 [영어 읽기 문제 바로가기] 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'이다. 각각의 단어들은 제일 첫 문자와 제일 끝 문자를 제외하고는 순서가 뒤섞여 있다. 한 대학에서 시행한 연구 조사 결과에..

문제 좋다 문제 바로가기 N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다. N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다. 풀이 처음에 생각했던 방법은 주어진 숫자들을 for문 3중으로 돌면서 두 수의 합으로 표현할 수 있는 지 찾는 방법이다. 입력이 크지 않아서 가능할 것이라 생각하였고 해당 방법을 사용할 경우 찾으려는 숫자보다 작은 수들만 고려하면 된다고 생각하였다. 하지만 문제에서 음수까지 범위에 들어가므로 target이 된 수보다 큰 수에 음수가 더해져서 target인 수를 만들 수도 있다. 따라서 어차피 입력이 10^3 밖에 되지 않으니 주어진 숫자들 중 2개씩 골라서..