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..
Today's Algorithm(2018-10-19) programmers 네트워크 깊이/너비 우선 탐색으로 풀 수 있는 문제 중 가장 간단한 형태의 문제 중 하나가 아닐까 생각합니다. 한마디로 연결되어 있는 네트워크의 개수를 구하라는 것이죠. 모두가 이어져 있으면 1개, 만약 모두 연결되어 있지 않으면 n이 반환되는 것입니다. 이 경우 '깊이 우선 탐색', '너비 우선 탐색' 모두 사용 가능한데요. 저는 Queue를 이용한 '너비 우선 탐색'을 이용하였습니다. 대략적인 풀이 방법은 다음과 같습니다. n개의 반복문을 돌면서 방문하지 않은 컴퓨터를 하나 고릅니다. 방문하지 않은 컴퓨터를 큐에 넣고 방문 표시 및 네트워크 개수를 +1 증감합니다. 이 큐가 비워질 때까지 반복합니다. 그 반복문 안에서 우선 큐..
programmers 타겟 넘버 뭔가 어려울줄 알았는데 막상 풀어보니 단순한 문제였네요. 결국은 모두 탐색해봐야하는 문제인데요. 이 경우 고려해볼 수 있는 것은 DFS를 고려해볼 수 있습니다. DFS를 구현하기 위해 재귀를 썼습니다. 하지만 구현을 하는데 있어 전역변수를 최대한 써보지 않는 방향으로 노력해봤는데 생각보다 잘 안되더라구요. 그래서 다 풀고나서 다른 사람들의 풀이를 참고하여 전역변수없이 구현하는 부분까지 해봤습니다. class Solution { int answer, target; public int solution(int[] numbers, int target) { answer = 0; this.target = target; int[] sign = {-1, 1}; visit(numbers,..
