programmers. 이중우선순위큐 이 문제는 PriorityQueue 를 두 개를 쓰면서 삽입할 때는 동시에 넣고, 최대값 삭제할때는 maxheap을 삭제하고, 최소값을 삭제할 때는 minHeap을 삭제하면 쉽게 해결할 수 있는 문제였습니다. 하지만 PriorityQueue 를 두 개를 사용함에 따라 두 개의 큐 안에 있는 값을 잘 파악해야 하는데요. 그 이유는 다음과 같은 상황들 때문입니다. maxHeap, minHeap 두 개의 큐 중 하나가 비워질 경우 → 모두가 꺼내어졌을 때입니다. 다 꺼내고 나서 의미없는 꺼내는 행위가 행해졌을 때 → 이 행위는 전혀 의미없는 것으로 데이터에 영향을 미쳐서는 안됩니다. 실제 위 두 개의 상황은 코드를 최초 구현하고 나서 제가 미비했던 부분이었습니다. 그럼 이..
programmers. 라면공장 다음 공급날까진 충분히 양이 남았지만 그 다음 공급날, 그 다다음 공급날까지 버텨내지 못하는 경우는 어떻게 처리해야할까요? 그래서 dfs로 현재 상황에서 공급량이 충분히 되더라도 공급을 받는 경우, 그리고 공급을 받지 못하는 경우를 모두 실행하도록 구성하였습니다. class Solution { int answer; int k; public int solution(int stock, int[] dates, int[] supplies, int k) { this.k = k; this.answer = supplies.length; dfs(stock, dates, supplies, 0, 0, 0); return answer; } public void dfs(int stock, in..
programmers 더 맵게 문제 자체가 어렵진 않았는데 저의 미천한 지식이 더욱 문제를 어렵게 만들었네요. 제가 풀어본 방법은 3가지 입니다. Collections.sort() 를 이용한 정렬 → 시간초과 발생 힙 구현 및 정렬 → 로직이 꼬임, 시간초과 Java의 PriorityQueue이용 → 성공 처음엔 해시 카테고리인 문제임에도 불구하고 Collections.sort() 를 이용하였습니다. 역시나 '시간초과'가 발생하였습니다. 이렇게 처음 푼 이유는 물론 익숙한대로 쓰다보니 쓴 것도 있지만 Collections.sort() 도 시간복잡도가 O(Nlog(N))라고 생각하였고 다른 방법으로 풀어도 빨라봤자 정렬할 때 이 시간복잡도 보다는 빠르지 않을 것이라 생각하였습니다. 하지만 결..
Today's Algorithm(2018-11-27) leetcode 11. Container With Most Water 어제 손쉽게 풀었던 문제인데요. 문제를 풀고나서 효율성은 거의 빵점이더라구요. 그래서 오늘 다른 사람의 코드를 참고하면서 기존의 코드를 개선할 수 있는 방법을 찾으려 노력하였습니다. 어제 다른 사람의 코드를 봤었을 때는 잘 이해가 안갔는데 넉넉하게 여유를 잡고 보니 알겠더라구요. 그래서 기존 코드와 오늘 참고한 코드에 대해 모두 정리해보려 합니다. 처음에 문제를 봤을 때 가장 처음 든 생각은 막대기가 index값을 가지고 있으면서도 height를 가지고 있어야 하기 때문에 Stick이라는 클래스를 만들면 좋겠다는 것이었습니다. 그리고 for문 2개를 이용하여 다른 막대기를 2개를 골..
Today's Algorithm(2018-11-22) programmers 여행경로 어제 짧은 시간이었지만 문제를 풀었는데 테스트케이스 4개 중에 2개가 '런타임오류'가 발생하였습니다. 뭐가 무엇인지 찾지 못하다가 같이 스터디하는 멤버로부터 받은 커스텀 테스트케이스를 돌려봄으로써 어떤 것에서 오류가 발생했는지 알았네요. 그럼 저는 문제를 어떻게 해결했는지 간략하게 정리해볼께요. 먼저 티켓들을 원하는대로 쉽게 꺼내기 위해 자료구조를 만들건데요. 우선 이전에 Ticket이라는 클래스를 만들었습니다. (출발지, 도착지, 사용여부) 이렇게 3개의 상태값을 가지고 있습니다. class Ticket implements Comparable { String departure; String arrival; boolean..
programmers 단어 변환 이 문제는 어제부터 시작했었는데요. 테스트 케이스 5개 중 1개가 계속 틀려서 결국 해결하지 못하고 오늘로 넘겼던 문제입니다. 틀린 이유를 여러가지로 생각해봤었는데요. 참 허무하지만 저의 이해의 부족으로 틀렸던 것이더라구요. 그럼 어떤 과정으로 해결해왔는지 간략하게 정리해보겠습니다. 맨 처음에는 BFS(너비 우선 탐색)으로 접근하였는데요. 맨 처음 제출하여 틀린 소스코드는 다음과 같습니다. class Solution { public int solution(String begin, String target, String[] words) { List wordList = Arrays.asList(words); boolean[] visit = new boolean[wordList..
