title: "순위 검색" category: 프로그래머스[Level-2] tags: [C++, JavaScript, 프로그래머스] date: "2021-01-29" 문제 링크 순위 검색 C++ #include #include #include #include #include using namespace std; vector solution(vector info, vector query) { vector answer; map info_score; // 조건(key)_점수(value) for(string& str: info){ // split vector v(4); stringstream ss(str); for(int i=0; i> v[i]; } int score; ss >> score; // 조합(모든 경우..
문제 링크 코딩테스트 연습 - 섬 연결하기 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 함수 중복을 제거하기 위해 을 사용하였고 재..
문제 링크 코딩테스트 연습 - 숫자 게임 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 � programmers.co.kr 풀이 주어진 문제가 구하는 것은 "최대 승점"이다. A팀의 점수보다 큰 B팀의 점수 중에서 최소 값으로 1경기씩 나간 것이 "최대 승점"이다. 그래서 sort로 정렬해서 할까하다가 priority_queue에 넣고 (넣은 방향 기준)내림차순 정렬로 하나씩 빼면서 승점을 올렸다. // 요약 1) 우선순위 큐에 push 2) 승점 추가(A팀의 점수보다 큰 B팀의 점수 중 최소 값을 결정) 반복문(B팀원의 수가 없을 때까지) { A팀원 숫..
문제 링크 코딩테스트 연습 - 기지국 설치 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5 programmers.co.kr 풀이 전달되지 않는 범위를 ranges 컨테이너에 담아서 최소 개수를 리턴하여 풀었다. 최소 개수만을 리턴하는 문제이므로 전달되지 않는 범위(vector 컨테이너 값) / 전달 범위(2w+1)가 최소 개수고 전달되지 않는 범위(vector 컨테이너 값) % 전달 범위(2w+1)로 나머지가 있다면 기지국 1개를 더 추가해준다. 더보기 #include #include using namespace std; // 아파트 개수 n, 사전 기..
문제 링크 코딩테스트 연습 - GPS edge_list [[1, 2], [1, 3], [2, 3], [2, 4], [3, 4], [3, 5], [4, 6], [5, 6], [5, 7], [6, 7]] programmers.co.kr 풀이 어렵다... 풀이를 봐도 처음에 이해하기 어려웠다. 주석으로 써놓긴 했지만 DP 문제로서 풀이는 최소 오류 수정값을 넣으면서 진행해간다. // 변수들 1) adj[201]; 이 변수는 한 점의 연결된 정점들을 모아둔 vector 컨테이너라고 보면된다. 201개로 설정한 이유는 정점은 1~n이므로 넘버링 되어 있기 때문이다. ex) adj[0] = 1, adj[0] = 2 라면 0에 연결된 점은 1과 2가 있다. 물론 문제에서는 양방향이기 때문에 adj[1] = 0, ad..