전체 글
-
[JAVA] 큐 구현은 어느것이 적당할까? LinkedList vs ArrayDeque알고리즘/알고리즘 Tip! 2020. 4. 20. 12:42
보통 배열의 경우 고정된 크기가 주어지기 때문에 검색이 빠르지만 삽입 삭제시 배열 크기 재 조정때문에 추가 비용 및 연산이 발생합니다. 그리고 공간 비효율성과 배열의 재배치가 일어납니다. 그렇다면 큐는 배열보다는 리스트로 구현하는게 낫지 않을까 하는 생각이 들 수 있습니다. 그러나 Queue를 구현할때 ArrayDeque로 구현하는 것이 LinkedList로 구현하는 것보다 빠르다고 Java API document는 설명하고 있습니다. 왜 ArrayDeque가 LinkedList보다 빠른걸까요?? 그 이유는 다음과 같이 2개 입니다. 출처 : http://javaqueue2010.blogspot.com/ ArrayDeque는 Array에 의해 지원되며 Array는 LinkedList보다 cache-loc..
-
[JAVA] 스택(Stack) vs 덱(Deque)알고리즘/알고리즘 Tip! 2020. 4. 19. 19:06
Stack 클래스는 List 컬렉션 클래스의 Vector 클래스를 상속받아, 전형적인 스택 메모리 구조의 클래스를 제공합니다. Stack st = new Stack(); 더욱 복잡하고 빠른 스택을 구현하고 싶다면 Deque 인터페이스를 구현한 ArrayDeque 클래스를 사용하면 됩니다. Deque st = new ArrayDeque(); 단, ArrayDeque 클래스는 Stack 클래스와는 달리 search() 메소드는 지원하지 않습니다. Java SE 6부터 지원되는 ArrayDeque 클래스는 스택과 큐 메모리 구조를 모두 구현하는데 가장 적합한 클래스입니다. 위의 내용은 자바 도큐먼트 사이트에서 직접 명시된 내용입니다. 왜 이런 구조로 되어있는 것일까요?? 그에 대한 분석이 2013년에 Badd..
-
코딩테스트 고득점 kit / 스택&큐 / 프린터 / JAVA알고리즘/프로그래머스 2020. 4. 19. 15:57
문제 https://programmers.co.kr/learn/courses/30/lessons/42587 풀이방법1 - Queue 2개 사용 import java.util.Queue; import java.util.LinkedList; import java.util.Arrays; class Solution { public int solution(int[] priorities, int location) { int answer = 0; Queue indexQ = new LinkedList(); Queue valueQ = new LinkedList(); for(int i=0; i
-
코딩테스트 고득점 kit / 스택&큐 / 주식가격 / JAVA알고리즘/프로그래머스 2020. 4. 18. 23:40
문제 https://programmers.co.kr/learn/courses/30/lessons/42584 풀이방법 1 import java.util.ArrayDeque; import java.util.Deque; class Stock { private int index; private int stock; public int getIndex() { return index; } public void setIndex(int index) { this.index = index; } public int getStock() { return stock; } public void setStock(int stock) { this.stock = stock; } } class Solution { public int[] so..
-
코딩테스트 고득점 kit / 힙(Heap) / 이중우선순위큐 / JAVA알고리즘/프로그래머스 2020. 4. 17. 23:56
문제 설명 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다. 명령어수신 탑(높이) I 숫자 큐에 주어진 숫자를 삽입합니다. D 1 큐에서 최댓값을 삭제합니다. D -1 큐에서 최솟값을 삭제합니다. 이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요. 제한사항 operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다. operations의 원소는 큐가 수행할 연산을 나타냅니다. 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합..
-
코딩테스트 고득점 kit / 힙(Heap) / 라면공장 / JAVA알고리즘/프로그래머스 2020. 4. 17. 23:50
문제 설명 라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다. 해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다. 현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 return 하도록 solution 함수를 완성하세요. ..
-
코딩테스트 고득점 kit / 탐욕법(Greedy) / 구명보트 / JAVA알고리즘/프로그래머스 2020. 4. 17. 23:28
문제 설명 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다. 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다. 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요..
-
코딩테스트 고득점 kit / 탐욕법(Greedy) / 체육복 / JAVA알고리즘/프로그래머스 2020. 4. 17. 22:33
문제 설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를..