youngik

이번 문제는 heap 문제분류에서 있던 문제이다. 먼저, heap에 대한 이해가 먼저 되어야 했기에 heap에 대해서 알아보자! heap - 최댓값, 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리이다. - A, B가 각각 부모, 자식 노드라면 대소관계가 성립 (최대 힙 -> A>B) / (최소 힙 -> A 배열 길이보다 많은 연산을 했을 때 -1 리턴하기

문제를 읽어봤을 때 정말 현실에서도 저렇게 문제를 찍는 사람들이 있을텐데, 그 생각을 알고리즘으로써 풀어보는게 재밌는 것 같다! 위 문제도 분석을 해보았을 때, 1. 먼저 1번, 2번, 3번 수포자가 찍는 패턴이 있음 (*1번 : 1~5번 반복 / 2번 : 2,1,2,2,2,3,2,4 반복 / 3번 : 3,3,1,1,2,2,4,4,5,5) 2. answers의 배열과 비교를 해서 각각의 수포자 패턴의 정답과 일치하면 count 증가 3. answers의 배열이 더 긴 경우에는, 다시 첫번째 배열로 가서 로테이션으로 비교 4. 가장 높은 점수를 받는 사람이 여러명일수도 있음. (오름차순 정렬) 쉬운 문제처럼 보였지만,, 번거로운 작업들이 많았던 것 같다. 1) 수포자 배열 끝까지 검색을 하면 다시 첫번째로..

먼저 위 문제를 분석해봤을 때, 1. (중요도, 위치값)를 가진 Point쌍의 값을 queue에 넣는다. 2. 각 cycle마다 현재 남은 queue의 중요도가 가장 큰 값과 비교를 한다. 3. 맨 앞에 값을 poll() 해봤을 때 max값과 일치하면 output queue에 넣고 작으면 다시 queue에 add()한다. (*1-3번의 작업은 priority 큐가 비어있을 때 까지 반복) 4. 1-3번의 작업이 끝나면 output queue에서 location과 일치하는 위치값을 출력한다. (몇번째로 출력되는지) -> 예제 문제에서 봤을 때, 동일한 값이라도 출력되는 순서가 다르기 때문에 원래 queue에서 위치값을 같이 저장했다. -> 몇번째로 인쇄됐는지 결과값을 물어볼때 0이 아닌 1부터 시작하기 때..

이 문제도 H-index에 대한 이해가 처음에 부족해서 1번 삽질을 하고 코드를 구성했던 것 같다. H-index의 H값이 citations에 주어진 값 중에서 1개로 결정되는 줄 알고 처음에 코드를 짰는데 질문하기에서 test케이스 중 {6, 5, 4, 1, 0} 일때 H의 값이 4가 아니라 3이 된다는 것이다. H = 4일때 : 4보다 크거나 같은 값이 3개, 4보다 작거나 같은 값 3개 => 충족 X H = 3일때 : 3보다 크거나 값은 값 3개, 3보다 작거나 같은 값 2개 => 충족 O 먼저 H-index에 대한 부분을 다시 분석을 해보았을 때 1. H-index는 배열에 있는 값들 중에서 H보다 크거나 값은 값이 H개 이상, H보다 작은 값이 H보다 작거나 같아야 함 (*간단히 생각해보면 H의..

스택의 3번째 문제이다. 먼저 위의 문제를 분석해보면서 1. Queue에 각 작업을 등록하고, 각 작업의 값을 speed값을 더한다. 2. 맨 앞에 작업보다 뒤에 작업이 먼저 100이 될 수가 있고, 바로 나오는 것이 아니라 앞 작업이 100이 되어야 나올 수 있어야 함. 3. 결과값으로 출력해야하는 return값의 배열길이는 한번에 나오는 작업의 수 *따라서 전체 작업의 수의 길이와 배열길이는 다르다! * 여기서 progresses 값만 queue에 넣고 speed는 그대로 배열로 사용하려고 하다가, queue에서 progresses값이 나가면, speed 배열은 그대로 유지하기 때문에 이전 문제에서 사용했던 큐를 사용해서 x = progresses, y = speeds 를 넣었다. * 구현한 기능 1..

먼저 위 문제를 분석해보았을 때 1. 배열의 i번째의 값에서 i+1의 값을 차례대로 비교해 나간다. 2. 비교를 해서 그 값보다 같거나 클때 count를 1씩 증가시킨다. 이 문제는 처음에 보고 아? 쉽네라는 생각으로 10분도 안되서 코드를 짰던 것 같다. 굳이 배열이 주어지는데 스택과 큐로 구현할 필요도 없어보여서 테스트 케이스를 성공하고 제출을 했는데, 왠걸,, 1개의 case빼고는 다 실패하지 않는가?? 처음 짠 코드 부분인데, 왜 안되지? 라는 생각으로 질문에 들어가보니 입출력 예제의 3초때를 잘 보아야 한다라는 말이 있었고, 나는 결과값이 (전체비교횟수 - i보다 작은 수)라고 생각했었는데 그것이 아닌 (i보다 작은 수가 있었을 때에는 그 거리만큼 값)을 출력하는 것이었다. (*말장난,,) 그래..

이번 문제는 처음부터 삽질을 많이 한 결과로 볼수가 있다ㅠ stack & queue에 대한 개념을 먼저 잡아야 했고, 다리를 통과하는 것은 stack보다는 queue가 더 적합한 것 같아서 queue를 통해 구현하기로 했다. *기본적인 stack 선언 Queue temp = new LinkedList(); Queue는 LikedList 형태로 구현이 되어있고, array와 같은 개별적으로 존재하는 것이 아닌 값들이 서로 연결되어있어 메모리의 빈 공간을 차지하지 않는다는 장점이 있다. 하지만 장점이 있으면 단점이 있다는 것인데, 자료값을 search 하거나, 삽입, 삭제 등을 할 때 시간이 걸린다. array는 int arr[4] = 0; 같이 직관적으로 삽입할 수 있으니!! ▶위 문제를 먼저 분석해본결과..

K번째 수 네이버 코딩테스트를 준비를 알아보면서 프로그래머스, 백준 알고리즘을 이용해서 문제를 많이 풀어보는 것이 좋다고하여 오늘부터 2-3문제씩 문제를 풀어보려고 한다. 문제 : array와 commannds가 [i,j,k]로 2차원 배열로 주어지고 array를 i,j 범위로 자른후에 k번째 배열의 결과값을 저장하고 return 해야한다. 먼저 위 문제를 분석해보면서 1. array를 먼저 i에서부터 j까지 자르고 2. 자른 배열의 k번째 값을 배열에 저장해야한다. 3. 그리고 각 결과값들을 저장하여 return 시켜야 함. *유의점 : i에서부터 j번째까지는 0부터 시작하는 것이 아닌, 1부터 시작한다. 일반적인 배열의 시작은 0부터 시작 오랜만에 java를 사용하면서 2차원 배열의 길이는 어떻게 구..