문제 링크 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 �� programmers.co.kr 풀이 주석으로 많이 표시해놓았지만, 요약하면 다음과 같다. // init 1. map(중복X)로 장르당 총 횟수를 저장 2. 동시에, multimap(중복O)으로 장르당 고유번호를 저장 // 사전처리 - map(중복X)에 장르(string)로 사전 순으로 정렬돼있으므로 횟수 순으로 정렬을 바꿔주기 위한 처리 1. 횟수당 장르로 map으로 다시 저장 - 횟수순으로 알아서 오름차순 정렬된다, 횟수는 고유하다고 문제에 나와있다. 2. vector 컨..
문제 링크 코딩테스트 연습 - 위장 programmers.co.kr 풀이 중복되지 않는 map 컨테이너를 이용해서 갯수를 하나씩 증가시켰다(해당 key에 대해 횟수 증가하기 좋은 컨테이너) 그리고 (종류1 집합(공집합 포함) * 종류2 집합(공집합 포함) * .... = 다른 종류로 입을 수 있는 가짓수) 가 나오며 공집합끼리 겹쳐있는 것을 제외하기 위해 (-1)을 하였다. 공집합 = 안입는 경우 더보기 #include #include #include using namespace std; int solution(vector clothes) { int answer = 1; map m; for(auto e: clothes) m[e[1]]++; for(auto i=m.begin(); i!=m.end(); i+..
문제 링크 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조�� programmers.co.kr 풀이 string은 정렬하면 사전 순으로 정렬되므로 정렬하고 전의 원소가 접두어인 경우를 알 수 있다. 이를 이용... 풀이가 너무 짧... 더보기 #include #include #include using namespace std; bool solution(vector phone_book) { bool answer = true; sort(phone_book.begin(), phone_book.end()); // 정렬 for(int i=1; i
문제 링크 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수�� programmers.co.kr 풀이 completion 컨테이너에 있는 갯수가 하나 적으므로 무작위로 돼있는 원소들을 정렬한다 이후 원소들을 비교하면서 없는게 있다면 완주하지 못한 선수다.(참가자의 원소를 return) 더보기 #include #include #include using namespace std; string solution(vector participant, vector completion) { string answer = ""; sort(p..
문제 링크 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 풀이 전형적인 크루스칼 + 유니온파인드 문제다. 최소신장트리(MST)를 만들고 간선에 대해서 모든 비용을 합한다. // cmp 함수 크루스칼 알고리즘을 이용하기 위해 간선(비용)에 대해서 오름차순 정렬한다. // find_root 함수 root 찾는 함수다. 1) root가 지금 나라면 바로 리턴 2) 아니면 나의 부모로 재귀로 호출 // solution 함수 map을 이용해 연결됨을 이용했다(어차피 정점에 대해서 중복하지 않으므로) 1) init - 각 정점은 자신을 루트로 지정 2) MST가 만들어질 때까지 반복문을 돌린다(MST는 간선의 수와 ..
문제 링크 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 풀이 이분탐색 문제였다.(구글링해서 앎) // 요약 1) 처음에 최대값, 최소값을 구한다. 2) 최소값이 최대값과 같아질 때까지 반복문을 돈다. 중간값은 (최소값+최대값)이 홀수일 때는 2로 나누고 +1, 짝수일 때는 2로만 나눈 값이다 (가능한 최대값을 기준으로 진행) (stones의 원소 - 중간값)이 음수가 연속으로 K번 이상으로 나올 때 최대값을 중간값으로 갱신 (stones의 원소 - 중간값)이 음수가 연속으로 K번 미만 나올 때, 최소값을 중간값으로 갱신 대신, 최대값을 갱신할 때는 불가능했던 값이므로 중간값-1로 갱신 해준다. 3) answer에 최소값..
문제 링크 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 �� programmers.co.kr 풀이 재귀 DFS로 풀었다. // check_equal 함수 불량 사용자인지 판별하는 함수다. '*'에 대한 처리를 한다. // solution 함수 banned_id가 각각 어떤 것에 해당되는지 미리 "vv" vector 컨테이너에 담는다. "vv" 컨테이너는 user_id의 인덱스로 담는다.(중복 검사하는데 string보다 정수 하나 비교하는게 더 간편하기 때문에) 그리고 DFS 진행한다. // dfs 함수 중복을 제거하기 위해 을 사용하였고 재..
문제 링크 코딩테스트 연습 - 방문 길이 programmers.co.kr 풀이 범위 검사, 방문 이력 검사 함수와 x, y는 row, column으로 대조하여 풀었다. // Node 구조체 row, column의 int 타입을 가지며 1)생성자와 2)복사 생성자, 3)비교 연산자 오버로딩, 4)대입 연산자 오버로딩을 정의하여 다른 외부에서 편하게 사용하였다.(참고로 Java에서는 this가 참조자고 C++에서는 this가 포인터라는 것을 일깨워줌) // check_range 함수 범위 체크 함수. size를 받아 범위를 초과하는지 체크한다. // check_visit 함수 방문 이력 체크 함수. tuple을 모아놓은 vector 컨테이너를 방문 이력으로 참조자를 사용하여 갱신(push_back)되도록 한..