프로그래머스lv263 [프로그래머스 lv3] 베스트앨범 풀이 해설해시를 이용하여 장르별 정보를 처리하는 문제이다. 1) map nplay: 장르별 재생 횟수를 저장한다.2) map> minfo: 장르별로 곡의 (재생수, 번호) 배열을 저장한다.3) minfo[장르]을 내림차순으로 정렬한다. 이때, 같은 재생 수를 가진 곡에 대해서는 곡 번호가 작은 녀석이 앞에 오도록 정렬한다.4) nplay를 배열(vnplay)로 만들고 재생수 기준 내림차순으로 정렬한다. 이후, vnplay에 저장된 순으로 장르를 순회하면서 minfo[장르]의 가장 앞쪽 두 곡 번호를 벡터에 저장한다.곡 번호가 기록된 벡터를 리턴하면 정답이다. 코드#include #include #include #include #include #include #include #include #include #.. 2022. 9. 2. [프로그래머스 lv3] 표 편집 풀이 해설표를 구성하고, 이동(U, D), 삭제(C), 복구(Z) 명령어를 구현하는 문제이다.이 문제의 핵심은 표를 구성할 자료구조를 선택하는 것이다. 가장 먼저 생각했던 자료구조는 set이었다.U X, D X 명령어에서 X의 총합이 1000000 이하이고, set에서는 원소의 삭제가 log(n)에 가능하므로 총 시간복잡도는 최대 t = 1000000 + cmd.size()*log(n) 이 된다. cmd와 n의 최대 범위를 고려했을 때 1초 내에 연산 가능하므로 통과할 것이라 생각했는데 이런! 효율성 통과가 안된다.여러 블로그글들을 살펴보니 예전에는 set 풀이가 통과되었는데 어느 날 채점 방식(?)이 수정된 것 같다고 한다. 시간복잡도를 더 줄일 수 있는 방법으로 연결리스트를 활용하는 방법이 있다.c++에 .. 2022. 9. 1. [프로그래머스 lv3] [1차] 셔틀버스 풀이 해설콘이 셔틀을 타기 위해 나갈 수 있는 가장 늦은 시간을 구하는 문제이다. 일단, 모든 크루들의 대기 시간을 정렬하고, 각 시간대별 셔틀에 한명씩 태운다.이 때, 콘은 가장 마지막 버스에 타야 한다. 따라서, 마지막 셔틀까지 크루들을 태웠을 때, 버스의 정원이 남는다면 가장 늦게 나가도 마지막 버스를 탈 수 있으므로 정답은 마지막 버스의 도착 시간이 된다. 반면, 정원이 다 찬 경우, 콘은 마지막으로 탄 사람보다 1분 먼저 나와야 버스에 탈 수 있으므로 정답은 마지막에 탄사람의 대기시간-1분이 된다. 팁문자열이 특정 포맷으로 이루어져있을 때 sscanf() 함수를 사용하면 값을 쉽게 추출할 수 있다.특정 포맷으로 문자열을 만들어야 할 때 sprintf() 함수를 이용하면 쉽게 문자열을 만들 수 있다. .. 2022. 8. 31. [프로그래머스 lv3] 다단계 칫솔 판매 풀이 해설서로의 추천 관계를 그래프(트리)로 만들어놓자.특정인 x에 대하여 수익 n이 발생했을 때, 부모 노드인 추천인을 따라가면서 재귀적으로 수익을 분배하면 된다.수익 분배는 n/10만큼씩 부모 노드 방향으로 진행되다가, 더이상 위의 추천인이 없거나 배분할 금액이 없을 때 중단된다.수익을 재귀적으로 분배한 후, enroll 배열에 있는 이름의 순서대로 수익을 나열하여 리턴하면 정답이다. 코드#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;using ii = pair;using iii = tuple.. 2022. 8. 30. [프로그래머스 lv3] 단어 변환 풀이 해설재귀를 이용하여 가능한 모든 경우를 탐색하는 백트래킹 문제이다.현재 단어를 x라고 했을 때, 다음으로 이동할 수 있는 단어는 words에 있는 단어 중 아직 방문하지 않았고, x와 한개의 글자만 다른 단어이다.다음 단어로 이동하면서, 도착한 노드가 target과 같을 때 이동 횟수의 최솟값을 갱신한다.모든 경로를 탐색한 뒤 이동 횟수의 최솟값을 리턴하면 정답이다. 코드#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;using ii = pair;using iii = tuple;int mn =.. 2022. 8. 29. [프로그래머스 lv3] 여행경로 풀이 해설여러 경로가 있을 때, 사전 순으로 목적지를 선택해야 하므로 tickets을 정렬시킨다. 흔히 dfs는 노드를 중심으로 방문여부를 체크하고 탐색을 진행한다.그런데, 이 문제의 경우 노드가 아닌 티켓을 중심으로 탐색을 진행해야 한다.노드의 경우 여러번 방문이 가능하기 때문에, 티켓의 사용여부를 체크하면서 다음 티켓을 탐색해야 한다. 현재 방문 노드가 x일 때, 출발지를 x로 하는 티켓 중 아직 체크되지 않은 티켓을 사용할 수 있다.tickets[i]를 사용할 때, tickest[i][1]이 다음 목적지가 되므로 tickets[i][1]을 출발지점으로 하는 dfs를 수행하면 된다.가능한 깊이까지 모두 탐색하였을 때, 모든 티켓을 사용하지 않았다면 다음 루트를 고려해야 하므로 flag를 사용하여 모든 티켓.. 2022. 8. 28. [프로그래머스 lv3] 네트워크 풀이 해설bfs(너비 우선 탐색)을 수행하면 한번에 하나의 그래프를 탐색할 수 있다.visited 배열에 탐색한 노드를 체크할 때, 특정 노드를 아직 체크하지 않았다면 해당 노드를 루트노드로 하는 새로운 그래프를 탐색할 수 있다는 뜻이다.따라서, 모든 노드를 순회하면서 해당 노드가 이미 체크되었는지 확인하고, 체크되지 않았다면 이를 루트노드로 하는 새로운 그래프를 bfs로 탐색한다.새로운 그래프를 순회할 때마다 네트워크 개수를 1 증가시키고 총 네트워크 개수를 리턴하면 정답이다. 코드#include #include #include #include #include #include #include #include #include #include #include #include #include #include #.. 2022. 8. 27. [프로그래머스 lv3] 순위 풀이 해설n의 입력값이 100이하 이므로, 시간복잡도가 O(V^3)인 플로이드 와샬 알고리즘으로 해결할 수 있다. i가 k를 이길 수 있고, k가 j를 이길 수 있을 때, i는 j를 이길 수 있다.따라서, dp[i][k] == true 이고 dp[k][j] == true 이면 dp[i][j] = true 이다. 위의 사실을 이용하여 이길 수 있는 모든 경우를 구해놓은 뒤, 특정 선수에 대하여 이기는 경우의 수와 지는 경우의 수를 모두 세어보자.특정 선수가 이기는 사람 수를 nwin, 특정 선수가 지는 사람 수를 nloss라고 했을 때 nwin+nloss-1(본인 제외) = n 이면 해당 선수의 순위를 결정할 수 있다. nwin+loss-1 == n인 선수의 수를 카운트하여 리턴하면 정답이다. 코드#includ.. 2022. 8. 27. [프로그래머스 lv3] 가장 먼 노드 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 1번 노드로 부터 각 노드까지의 최단 거리를 구한 후, 최단 거리가 최대인 노드의 개수를 구하는 문제이다. 1번 노드를 출발지점으로 하여 bfs를 수행시키고, 각 노드를 방문할 때 최단 거리를 기록한다. 1번 노드로 부터 x번 노드까지의 최단 거리를 dist[x]라 할 때, dist[x] 값 중 최댓값을 구하고, 최댓값을 갖는 x의 개수를 리턴하면 정답이다. 코드 #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ii = pair;.. 2022. 8. 27. [프로그래머스 lv2] 3xn 타일링 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 2x1(1x2) 모양의 직사각형으로 3xn 직사각형을 채우는 경우의 수를 구하는 문제이다. n을 하나씩 늘려가면서 규칙을 찾아보자. 1. n = 1 일 때 주어진 직사각형으로 3 x 1 직사각형을 채울 수 없다. n = 1 뿐만 아니라 n이 홀수이면 무조건 채울 수 없다는 사실을 알 수 있다. 2. n = 2 일 때 3가지 방법으로 채울 수 있다. 즉, d[2] = 3 3. n = 4 일 때 (1) 앞의 두 칸을 먼저 채우고 나머지를 3x2 직사각형을 채우는 방법으로 채운다. (3 x dp[2]) (2) 네 칸을 전역에 걸쳐 채운다. (2) (네 칸을 전역에 걸쳐 채우는 방법은 다음과 같다.) 즉, dp[4] = 3 x dp[2] + 2 4. n = .. 2022. 8. 25. 이전 1 2 3 4 ··· 7 다음