Algorithm/자료구조 (126) 썸네일형 리스트형 (Python3) - LeetCode (Medium) : 1014. Best Sightseeing Pair.py https://leetcode.com/problems/best-sightseeing-pairheap또는 binary search를 사용해 풀어본 문제였습니다.📕 풀이방법📔 입력 및 초기화values의 길이를 length로 저장, 정렬된 값을 저장할 배열 sorted_values, 정답 변수 max_score를 선언 후 적절히 초기화합니다.📔 풀이과정values의 원소를 순회하며 다음을 진행합니다.values에서 values[i] + i값의 최댓값을 O(logN)만에 찾을 수 있다면 sorted_values의 마지막 원소 + values[j] - j값의 최댓값만 찾는다면 O(NlogN)만에 답을 찾을 수 있습니다. 다음 두 가지 방식을 생각해볼 수 있습니다. 1. sorted_values에 넣을 때.. (Python3) - LeetCode (Medium) : 2. Add Two Numbers https://leetcode.com/problems/add-two-numbers/description/재귀를 활용해 linked list 순회 및 자료구조를 만들어본 문제였습니다.📕 풀이방법📔 입력 및 초기화 📔 풀이과정1. l1, l2를 순회하며 실제 숫자를 추출하는 함수 num_of_linked_list를 구현해줍니다. next가 None이 아닌 동안 loop를 수행하면서 현재 값에 10의 piv승만큼 곱한 값을 num에 더해주는 방식입니다. 해당 결과를 num에 저장합니다. 2. 주어진 num을 입력받아 reverse로 num의 일의 자리 수로 linked list를 재귀형태로 연결하여 만들어진 linked list를 반환하는 make_linked_list를 구현해줍니다. 해당 결과를 a.. (Python3) - LeetCode (Medium) : 2182. Construct String With Repeat Limit https://leetcode.com/problems/construct-string-with-repeat-limit📕 풀이방법📔 입력 및 초기화key로는 알파뱃 value는 빈도 수를 저장할 해시맵 char_map, max_heap, 정답변수 answer, 이전 문자 prev를 선언 후 적절히 저장해줍니다. max_heap은 python에서 제공되지 않으므로 저장시 음수로 저장해줍니다.📔 풀이과정큰 문자부터 넣다가 reapeatLimit을 넘어가면 다음문자를 1개씩 넣어줍니다. 이 때 큰 문자와 이전에 넣은 문자가 같은 경우 적절히 빼서 repeatLimit만큼의 문자만 answer 뒤에 붙이도록 구현해야합니다. max_heap에 원소가 있는 동안 다음을 진행합니다.1. 이전에 있는 문자가 같고 .. (Python3) - LeetCode (Medium) : 1792. Maximum Average Pass Ratio https://leetcode.com/problems/maximum-average-pass-ratiomax heap을 사용해본 문제였습니다.📕 풀이방법📔 입력 및 초기화정답 avg, heap pq를 선언 후 (1명이 추가될 경우 증가하는 합격율, 현재 합격율, index정보)를 하나의 tuple로 classes의 원소를 순회하며 계산해 저장합니다.📔 풀이과정extraStudents만큼 for loop를 수행하며, 1명 증가시 비율이 최대한 증가하는 순으로 extraStudents를 배분해줍니다. 1. python에서는 max heap이 없으므로 -형태로 tuple의 첫 번째 값을 저장하고 꺼냈을 때 -후 값을 구합니다. 2. classes에서 추가될 idx번째 수업에서 통과자와 전체 인원을 1씩 .. (Python3) - LeetCode (Medium) : 2593. Find Score of an Array After Marking All Elements https://leetcode.com/problems/find-score-of-an-array-after-marking-all-elements📕 풀이방법📔 입력 및 초기화1. 우선순위 큐 pq, 정답 score, check 여부 ck배열 선언 후 적절히 초기화합니다. 2. nums의 원소를 순회하면 값, index정보를 pq에 저장합니다.📔 풀이과정min heap인 pq의 원소에 대해 while lop를 수행하며 다음을 진행합니다.1. 이미 check되어 있다면 continue 합니다. 2. check가 안된 원소를 score에 더하고 인접 index를 범위를 넘지 않았다면 check해줍니다. pq의 길이 n개 만큼 while loop를 진행해 인접 원소를 pop후 check해주므로 우선순위큐에 원.. (Python3) - LeetCode (Medium) : 2924. Find Champion II https://leetcode.com/problems/find-champion-iigraph(DAG) 문제였습니다.📕 풀이방법📔 입력 및 초기화1. 각 node별 진입하는 노드의 개수 in_degree_count를 선언 후 n-1까지 0으로 채워 초기화합니다. 2. edges를 돌며 e[1]에 진입하는 in_degree_count를 세줍니다. 3. 정답 변수 champion, champion 수 champion_count를 선언 후 각각 -1, 0으로 초기화합니다.📔 풀이과정n-1까지 for loop를 수행하며 다음을 진행합니다.1. 각 node별 진입 노드가 존재여부를 파악합니다. 존재하지 않다면 champion이므로 champion을 현 node로 갱신 후 champion_count를 1더해.. (Python3) - 프로그래머스(연습문제): 추억 점수 https://school.programmers.co.kr/learn/courses/30/lessons/176963 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krhashmap을 사용해본 문제였습니다.📕 풀이방법📔 입력 및 초기화1. 정답변수 answer 선언 후 빈 배열로 초기화합니다.2. name, yearning을 각각 key, value로 name_yearning_dict를 선언 후 빈 객체로 초기화합니다. 3. name에 대해 loop를 수행하며 name별 그리움을 저장합니다.📔 풀이과정photo에 대해 2차원 for loop를 수행하면서 다음을 진행합니다.1. 행마다 name_yearni.. (Python3) - 프로그래머스(코딩테스트 입문) : 한 번만 등장한 문자 https://school.programmers.co.kr/learn/courses/30/lessons/120896 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krhash map을 사용해본 문제였습니다.📕 풀이방법📔 입력 및 초기화한 번만 나온 alphabat을 저장할 char_count, hash_map dict를 선언 후 빈 배열과 객체로 초기화해줍니다.📔 풀이과정1. s에 대해 원소를 순회하며 dict에 문자와 빈도수를 저장합니다. 2. dict의 items를 순회하며 빈도수가 1인 문자를 char_count에 추가합니다. 3. char_count를 오름차순으로 정렬합니다.📔 정답 출력 | .. 이전 1 2 3 4 ··· 16 다음