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; // 조합(모든 경우..
title: "메뉴 리뉴얼" category: 프로그래머스[Level-2] tags: [C++, JavaScript, 프로그래머스] date: "2021-01-27" 문제 링크 메뉴 리뉴얼 C++ #include #include #include #include using namespace std; vector solution(vector orders, vector course) { vector answer; map course_count; // 코스당 주문 횟수 map length_max; // 조합 길이당 코스 주문 갯수 최대 for(int len: course){ length_max[len]=0; // init } for(string& str: orders){ stable_sort(str.begin(..
문제 링크 코딩테스트 연습 - 징검다리 건너기 [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 함수 중복을 제거하기 위해 을 사용하였고 재..
문제 링크 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 풀이 전위 순회(preorder), 후위 순회(postorder)를 리턴하는 문제다. Node 구조체를 만들어 order하였다. 1단계) node들을 vector 컨테이너에 담기 2단계) vector 컨테이너에 있는 node들을 y값으로 정렬(순회하면서 노드들을 추가하기 위해) 3단계) 이진트리 생성(y값은 미리 정렬했으니 x값만 신경썼다) - 부모의 x보다 작으면 left, 부모의 x보다 크면 right 4단계) order() - 전위 순회는 먼저 방..
문제 링크 코딩테스트 연습 - 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..
문제 링크 코딩테스트 연습 - 호텔 방 배정 programmers.co.kr 풀이 효율성 문제라길래 해설을 보았고 union-find 알고리즘으로 푸는 문제였다. 시간 복잡도는 O(nlogN)으로 풀어야 효율성 테스트 케이스가 풀린다고 한다. // findRoom() --- 전역 변수로 map을 선언하는 대신 참조자로 매개변수로 받아서 구현하였다. if(요구하는 방번호는 배정해도 된다) map에 요구하는 방 번호는 다음 방 번호 저장한다.(다음 방 번호를 재귀로 찾을 수 있도록) 배정 안된 것의 번호를 리턴 else(이미 배정된 것이 있다) 배정 안된 것의 번호를 찾아서 저장 map에는 배정 안된 것의 다음 번호를 저장(나중에 또 물어보면 바로 찾을 수 있도록, 순차적으로X) 배정 안된 것의 번호를 리턴..