Algorithm/Programmers80 [프로그래머스] 문자열 내림차순으로 배치하기 / 자바 / Java / stringBuilder 💡solutions 💬 String.toCharArray()를 사용하여 문자열 s를 char형 배열(arr[ ])로 바꾼다. * 참고로 char형 배열을 하나의 문자열로도 만들 수 있다 -> String s1 = new String(charArr); 💬 arr 배열을 오름차순으로 정렬한다. 💬 stringBuilder을 사용하여 각 문자들을 appned()로 더한 후 문자열을 출력하기 위해 toString()을 사용한다. stringBuilder을 사용하는 이유 자바에서 String 객체는 변경 불가능하다. 따라서 String 객체끼리 더하는 연산은 메모리 할당과 해제를 발생시켜 성능적으로 좋지 않기 때문에 stringBuilder을 사용한다. stringBuilder은 String 객체를 더할 때 새로.. 2021. 11. 18. [프로그래머스] 섬 연결하기 / 파이썬 / Python / 크루스칼(Kruskal) 알고리즘 💡solutions ) 💬 '최소 비용으로 모든 노드(섬) 연결' -> 최소 신장 트리(MST)를 사용하는 크루스칼 알고리즘 활용 문제다. 신장 트리(Spanning Tree)란? 그래프 내의 모든 정점을 연결하는 트리로 간선의 개수가 n-1개로 최소 연결 부분 그래프이다. 최소 신장 트리(Minimum Spanning Tree )란? 신장 트리에서 사용된 간선들의 가중치의 합이 최소인 트리 즉, 최소 비용으로 모든 노드 연결하는 그래프이다. 참고 블로그 💬 먼저 다리 건설 비용 기준으로 costs를 오름차순 정렬한다. -> 적은 비용의 노드부터 꺼내와서 연결한다. 💬 노드의 부모를 찾는 find_parent를 통해 꺼내온 두 노드의 부모를 비교한다. ->사이클이 생기지 않게 하기 위해 부모가 다른 경우.. 2021. 11. 9. [프로그래머스] 체육복 / 자바 / Java / 그리디(Greedy) 알고리즘 💡solutions ) 💬 처음 코드를 제출했을 때 테스트케이스 13, 18번이 실패하였다. 8월 30일 기준으로 테케가 추가됐다고 하는데 아마도 lost나 reserve가 순서대로 들어오지 않은 경우일 것이다. (예를 들면, lost = [4,3,5]) 이때 sorting을 해주지 않으면 통과하지 못하게 된다. 💬문제에서 주어진 제한사항 중 5번째부터 해결한다. -> 첫 번째 이중 for문에서 여분의 체육복이 있지만 동시에 체육복을 도단당한 학생의 경우 다른 학생에게 체육복을 빌려줄 수 없는 상태로 만든다 reserve[j] = -1; 그리고 도난당한 학생 리스트에서도 제외해준다 lost[i] = -1; 💬 잃어버린 학생의 앞 또는 뒤에 있는 다른 학생으로부터 체육복을 빌려올 수 있는 경우 -> 빌려주.. 2021. 11. 7. [프로그래머스] 디스크 컨트롤러 / 파이썬 / Python / heapq 사용 💡solutions ) 💬 참고 : 디스크 컨트롤러 문제에서 요구하는 작업 처리 방식은 FIFO(First In First Out)가 아니라 SJF(Shortes Job First)방식이다. 즉, 요청된 작업들 중 가장 짧은 작업시간을 요구하는 작업부터 우선적으로 처리하는 방식이다. -> 이런 방식으로 진행하면 각각의 요청된 작업들의 대기 시간을 줄일 수 있다는 장점이 있다. (비선점형 스케줄링 방식에서 평균 대기 시간이 가장 짧다) 💬 heapq 모듈을 통해 최소 힙 사용하였음 -> heap에 작업의 소요시간, 작업이 요청되는 시점 순서로 값을 넣으면 (이번 예제에선 heap = [[3, 0], [6, 2], [9, 1]] 순으로 들어가는 셈) -> heappop할 때 작업의 소요시간을 기준으로 가장 .. 2021. 10. 29. [프로그래머스] 실패율 / 파이썬 / python / 2019 KAKAO BLIND RECRUITMENT 💡solutions ) 💬 이번에 구현한 로직이 효율성면에서는 좋지 못한 코드다. 특히 for문 안에서 매번 count()를 하기 때문에 시간 복잡도가 O(N²)이고, remove() 메소드까지 있기 때문에 맨 처음 stages.sort()를 하지 않으면 몇가지 테스트 케이스에서 시간초과로 통과하지 못하는 문제가 있었다. 💬 참고로 첫 시도에서 1,6,7,9,13,23,24,25 테스트 케이스는 런타임에러가 났고, 질문하기를 통해 어떤 것이 문제인지 확인해보니 -> for문 안에서 전체 남아있는 total_user가 0인 경우 fail_user/total_user로 계산하게 되면 ZeroDivisionError가 발생하는 것이 문제였다. 💬 혹시 필자와 같은 테스트케이스가 런타임에러 나는 경우 아래 테스.. 2021. 10. 28. [프로그래머스] 비밀지도 / 파이썬 / python / 2018 KAKAO BLIND RECRUITMENT/ 카카오 코테 💡solutions ) 💬 arr1과 arr2에서 주어진 정수들을 bin()을 사용해 이진수로 변환한 후 주어진 n크기에서 부족한 만큼을 0으로 채워주기 위해 zfill()사용 -> e.g.) 9를 이진수 1001 변환했을 때 -> 지도 한변의 크기가 5(n= 5)라면 -> 01001로 바꿔주기 👨💻code ) def solution(n, arr1, arr2): answer = [''] * n for i in range(len(arr1)): a1 = bin(arr1[i])[2:].zfill(n) a2 = bin(arr2[i])[2:].zfill(n) for j in range(n): if a1[j] == '0' and a2[j] == '0': answer[i] += ' ' else: answer[i] .. 2021. 10. 27. 이전 1 2 3 4 5 ··· 14 다음
