유자맛바나나의 Dev-log

public void bfs(Node root) { Queue q = new LinkedList(); q.offer(root); while(!q.isEmpty()){ int len = q.size(); for(int i=0; i

1. 서론Codility Lesson4. MissingInteger 문제를 풀면서 Hash와 Array간 데이터 접근/삽입 속도의 차이를 크게 체감할 수 있었다. 해당 문제에서 array로 접근하기엔 size를 100만개로 줘야 했기에 사이즈가 좀 크지 않은가 하는 생각에 Hash, Priorty Queue로 접근했는데 아무리 머리를 굴려봐도 Time Out이 났다. 그래서..! 메모리 제한도 없고, 그냥 배열로 풀라는 뜻인가 해서 배열로 풀었더니 바로 Pass. 도대체 Hash와 Array간 속도 차이가 얼마나 나길래 이런것인가 싶어서 직접 테스트해봤다. 2. 테스트 개요 array, HashMap, ConcurrentHashMap 세 가지에 대해 데이터 삽입/접근을 테스트한다 데이터 삽입(Add El..

분석 문제는 워낙 간단하고 쉽다. 단 해당 문제의 Lesson 주제가 Time Complexity인 만큼 시간 복잡도를 최소화하는 것이 문제의 의도로 보인다. 가장 쉽게 떠올릴 수 있는 방법은 N개의 크기 배열 A를 받았을 때 (1부터 N+1)까지의 숫자를 전부 Hash의 Key로 넣고 하나씩 Remove 하는 것이다. 이렇게 하면 가장 마지막에 남는 Key가 답이 된다. 하지만 이 방법은 Hash에 넣는데 N+1번, 그리고 A배열을 순회하며 찾는데 N번 걸리므로 O(n^2)이다. O(N)으로 끝낼 수 있는 방법은 배열을 딱 한 번만 순회하는 것이다. 처음 A 배열을 받으면 1~N+1 숫자의 합을 구한다. 그리고 A 배열을 순회하면서 합에서 값을 한 개씩 뺀다. 이렇게 하면 없는 숫자는 뺄 수 없으므로 ..

제약사항 N is an odd integer within the range [1..1,000,000]; each element of array A is an integer within the range [1..1,000,000,000]; all but one of the values in A occur an even number of times. 간단한 문제다. A에 들어가는 값이 1~10억이므로 배열의 인덱스와 동일하게 처리하기엔 사이즈가 너무 큼 그래서 Hash를 이용해서 발생한 숫자를 Key로, 발생한 횟수를 Value로 사용함 그리고 2로 나눈 나머지가 0이 안되는 것이 홀수번 발생한 것이므로 해당 숫자를 답으로 리턴 Code class Solution { public int solution(in..

예외사항을 생각해야 한다. Empty array, input 배열의 크기보다 rotation 횟수가 더 클때, K가 0일 때 등을 추가 테스트 케이스로 넣어준다 Additional Test Case ([], 3) ([1,2,3,4], 5) ([1,2,3,4], 0) Code class Solution { public int[] solution(int[] A, int K) { int[] res = new int[A.length]; // K 값이 A 배열의 길이보다 클 때 중복해서 rotation 하는 것이므로 나머지를 대입 if (A.length != 0 && K > A.length) { K = K % A.length; } // A배열의 크기가 K와 동일하면 로테이션 필요 없음 // A배열의 크기가 0이거..

문제 https://programmers.co.kr/learn/courses/30/lessons/42840 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr class Solution { public int[] solution(int[] answers) { int[] answer = {}; Solver sovler = new Solver(); int[] res = new int[3]; for (int i = 0; i < answers.length; i++) { int[] solve = sovler.solve(a..

문제 https://programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 오랜만에 공부 시작할 겸 가벼운 문제 풀어봄 주의할 점은 완주한 사람(completion)을 기준으로 해시를 만들고 참여한 사람(participant)을찾는 방식이 아니라, 참여한 사람을 기준으로 해시를 만들고 완주한 사람을 찾아야 한다는 것. 그리고 이름이 중복되는 사람이 여러 사람일 수 있으므로 각 사람의 이름을 count 한 후 ..