자료구조 & 알고리즘 (10) 썸네일형 리스트형 [dfs] 프로그래머스 - 아이템 줍기 1. 목표 지점까지 테두리를 시계 방향으로 이동 vs (반시계 방향 이동 == 목표 지점에서 현 위치까지 시계 방향 이동) => 두개를 구해서 더 짧은걸 채용 2. 도달하지 못하는 경우는 없으므로 목표 지점에 도달 할 때까지 계속 반복 (while True) 3. 현재 좌표가 어떤 사각형 위에 있는지 봐야됨 (for rectangle in rectangles) 4. 현재 좌표가 어떤 사각형 위에 있다면 그 변을 따라서 계속 이동함 (while True) 5. 변을 이동한 좌표가 다른 사각형의 내부라면 다시 back하고 다른 사각형의 변을 따라 이동함 (while 문 break 이후 다시 for문으로 다른 rectangle 탐색) 5-1. 1씩 체크하는 경우 사각형의 변이 1이라면 내부를 뚫고 지나가는 경.. [프로그래머스] 베스트앨범 python/파이썬 이 문제의 핵심은 해쉬의 정렬에 있다. 파이썬의 Dictionary는 key값으로 해쉬를 이용하기 때문에 마치 주머니에 정보를 담듯이 순서가 없다고 한다. 그런데 정렬을 해야되는 문제가 나와서 처음엔 당황을 했다. 찾아보니 딕셔너리를 정렬하여 저장하는 방법은 나오지 않았지만 딕셔너리의 key, value 중 하나를 기준으로 정렬하여 추출하는것이 가능했다. 처음 접근: Dict은 정렬이 불가하다 생각했기에 max1, max2 키를 추가로 만들어 정보를 담을 play[]를 순회하며 비교하여 정보를 담으려했다. 또 정답 출력시 필요한 장르의 총 재생횟수를 위해 cnt 키도 추가했다. 이 또한 구현이 가능할거 같았지만 Dict에 중복되는 정보가 담기고 구현이 복잡해지는거 같아 정렬이 가능하지 찾아보았다. Dic.. [프로그래머스] 전화번호 목록 python/파이썬 (해시 사용) 해시를 이용한 코드 phone_book을 정렬해준다. i번째가 i+1, i+2...의 접두사가 될 순 있지만 i-1의 접두사가 될 순 없다. 따라서 우리는 i, i+1만 비교해서 i가 i+1의 접두사인지 확인해주면된다. i가 접두사이기 위해선 i+1보다 길면 확인 할 필요가 없다. => continue i가 i+1보다 작을 경우 해당 번호(phone_book[i])를 키값으로 dictionary에 초기화 값을 넣어준다. i가 i+1의 접두사인지 확인하기 위해 i+1을 앞부터 len(i) 만큼 잘라 일치하는지 확인해준다. (in을 이용해 dic에 값이 있는지 확인한다.) 사실 startwith을 이용하거나 단순히 문자열을 자르고 같은지 비교하는게 더 편한거 같고 가장 빠르게 생각이 났다. 하지만 해시를 이.. [프로그래머스] 완주하지 못한 선수 python/파이썬 (4가지 솔루션) 첫번째 솔루션 배열 정렬 할 수 있다는 특성을 이용했다. participant과 completion 배열을 정렬 할 경우 완주하지 못한 참가자를 제외하면 completion과 일치해야한다는 점을 이용했다. 완주하지 못한 선수가 1명 이상이더라도 위의 개념을 이용해서 해결 할 수 있다. python 내부 함수 sort 정렬 과정에서 O(N log N) 반복문 O(N) def solution(participant, completion): participant.sort() completion.sort() for i in range(len(completion)): if participant[i] != completion[i]: return participant[i] return participant[len(pa.. [Java] 우선 순위 큐 구현 (Heap, PriorityQueue, minHeap) 코딩 중 구현하기 귀찮아서 구글링해서 갖다 썼는데 최대힙을 최소힙이라고 올려놨길래 다시 올려본다...(덕분에 한참 삽질..ㅎ) 무려 내가 본 3군데가 다 그랬다... 서로 퍼온건가.. (추후 정리 예정 우선은 class MinHeap 부분만 보면된다) package study.heap; import java.util.ArrayList; import java.util.PriorityQueue; class Heap_01 { public int solution(int[] scoville, int K) { int answer = 0; // heap을 이용해 minheap 구현 //MinHeap priorityQueue = new MinHeap(); // 우선 순위 큐 PriorityQueue을 사용 Priori.. [codeup] 코드업 2137 : 자라나라 머리머리 풀이 최종 풀이 코드는 제일 하단에 있다. 일단 블로그 국룰은 헛소리로 시작하는 거기 때문에 헛소리를 시전한다. 프로그래머스 들어가려고했는데 오랜만에 들어가려니 코드업이랑 햇갈려서 잘못 들어갔다. 그런데 내 관심을 끄는 문제가 있어서 문제를 풀기 시작했다. 풀어보니 새로 알게된 점이 많은 문제였던거 같다. 문제도 신선하니 재밌고 배울 포인트도 많으니 한번 풀어보길 추천한다. 문제 출처 : codeup.kr/problem.php?id=2137 자라나라 머리머리 머리카락의 개수 \(n\)과 초기 머리 길이 \(x\)가 공백으로 구분되어 주어진다. \((1 ≤ n ≤ 2,000,000,000 \ ; \ 0.0000 ≤ x ≤ 1000.0000)\) 이때 \(n\)은 양의 정수, \(x\)는 소수점 아래 자리가 네 .. [프로그래머스] K번째 수 자바에서는 한번 만든 배열을 초기화 하기가 어렵기 때문에 temp라는 배열을 만들어 필요한 부분에만 array 배열의 값을 복사해주었다. 그리고 quickSort를 사용해서 복사 받은 부분만을 정렬해주고 해당하는 순서에 있는 temp의 값을 가져와 answer에 넣어 줬다. 사용된 quickSort를 자세히 알고 싶다면 추천하는 유튜브 강의이다. https://www.youtube.com/watch?v=7BDzle2n47c&t=474s 위의 강의를 보고 quickSort를 이해했고 배열을 필요한 부분만 뽑아 올 수 있다면 어렵지 않게 풀 수 있을거라 생각한다. class Solution { public int[] solution(int[] array, int[][] commands) { int[] ans.. [프로그래머스] H-Index 최근에 퀵소트를 다시 구현해 써보고 싶어서 정렬 문제를 풀어보았다. 근데 이 문제는 굳이 퀵소트를 할 필요 없을거 같아서 간단하게 java.util.Arrays 의 sort를 사용해서 정렬해 보았다. 이 문제의 관건은 문제를 읽고 h-index를 제대로 파악해 조건 문을 만드는것이다. 졸리고 머리가 아팠다. 이 문제를 해결하지 못하신분은 저처럼 h-index를 잘못 이해 했었을거라 생각이 듭니다... import java.util.*; class Solution { public int solution(int[] citations) { int answer = 0; int n = citations.length; int h = 0; int i = 0; Arrays.sort(citations); // [22, .. 이전 1 2 다음