Create Sorted Array through Instructions 문제 내용 빈 Array nums[]가 있고 이곳에 입력할 값 Array 인 instructions가 있다고 할때 instructions Array의 왼쪽에서 오른쪽으로 nums[] Array에 값을 추가해 나간다. 단, nums[]의 Array는 정렬이 되어야 한다. 정렬을 위한 cost는 다음과 같이 정의한다. Min( 현재 있는 nums 중 insturction[i] 보다 작은 숫자의 갯수, 현재 있는 nums 중 instruction[i]보다 큰 숫자의 갯수 ) 예를 들자면 [1,2,3,4,5]의 nums가 주어졌을 때 3을 넣기 위한 최소의 cost 값은 1,2 => 2개, 4,5 => 2개 min(2,2) 임으로 cost..

Employee Free Time 문제 내용 종업원들의 스케쥴이 주어진다 모든 스케쥴을 확인한 후 모든 종업원들이 쉬는 시간을 구하라 접근 방법 모든 종업원들이 쉬는 시간, 즉 업무를 진행 하지 않는 시간을 찾으면 된다. 예를 들자면 [[[1,2],[5,6]],[[1,3]],[[4,10]]] 이라는 스케쥴이 주어졌다고 생각하자 상기의 그림처럼 `3~4`를 찾는게 문제이다. 이 그림을 보면 예상이 되겠지만, 어떤 사람별 스케쥴은 의미가 없다. 즉 모든 스케쥴을 한사람의 스케쥴이라고 생각하고 쉬는 시간을 찾으면 된다. 보이는 것처럼 단 2개의 스케쥴만 확인하고 해당 스케쥴 사이의 거리를 찾으면 되는 것이다. 그럼 어떻게 스케쥴이 겹치지 않는지 확신 할 수 있는가? 이것을 이벤트로 보면 다음과 같이 정리 할 ..

First Missing Positive 문제 내용 주어진 Integer Array에 1부터 N까지의 수가 있다. 이중에 1이상의 수중에 첫번째로 없는 수를 찾아라 O(N)을 목표로 한다. 접근 방법 O(N)이라는 부분이 이 문제의 핵심이다. 만약에 쉽게 정리 한다면 Sorting O(NlogN)으로 문제를 해결할 수 있다. 그러나 O(N)의 속도는 Sorting으로 해결되지 않는다. 이런경우 자료 구조를 통한 접근을 우선적으로 생각할 수 있다. 나는 Priority Queue를 통한 접근을 생각했다. 값을 Push할 경우 O(LogN) Delete할 경우 O(1)과 자리를 찾는데 걸리는 시간 최대 (N)이 걸릴 수 있다. 그래서 최대 O(N)으로 Priority Queue를 생각했다. public in..

Consecutive Numbers Sum 문제 내용 주어진 숫자(N)보다 같거나 낮은 수의 연속적인 배열의 Sum이 주어진 숫자와 같은 경우의 수는 몇개인가? 접근 방법 수학적인 접근을 통해서 문제를 해결해야 한다. 만약에 15라는 N이 주어졌다고 생각해 보겠다. 15(N) = 4 + 5 + 6 으로 이루어 질 수 있다. 또는 15(N) = 8 + 7 로도 이루어 질 수 있다. 이것을 일반항화 시키면 다음과 같다. N = (x + 1) + (x + 2) + (x+ 3) + ... + (x + k) 여기서 k는 연속된 갯수이다. 8 + 7은 두개의 연속된 갯수 임으로 k는 2이다. 이를 x로 묶어 보겠다. N = x*k + (0 + 1) + (0 + 2) + (0+ 3) + ... + (0 + k) 여기..

Basic Calculator 문제 내용 숫자, 더하기, 빼기, 중괄호 '(' ')' 그리고 ' ' 스페이스로만 구성된 계산식을 계산 하시오 풀이 방법 기본적으로 후위연산을 통해서 해당 문제를 푸는게 학교에서 배우는 방법이다. 자세한 내용은 www.programmersought.com/article/93565454512/ 여기를 참고 하면 되는데 간단하게 순서를 설명하자면 아래와 같다. 1. Stack을 2개로 유지한다 2. 1번 Stack은 숫자와 Operand(연산자) 로 이루어진 Stack이다. 3. 2번 Stack은 Operand(연산자)와 '(' 왼쪽 대괄호로 이루어진 Stack이다. 4. 2번 Stack에서 ')' 좌측 대괄호를 만나면 2번 Stack에 있던 Operand를 1번 Stack으로..

Trapping Rain Water 문제 내용 Stones가 쌓여있는 길이 Arrays가 주어졌을 때 Stones 사이에 얼마나 많은 물이 쌓일 수 있는가? 풀이 방법 풀이 방법은 여러가지가 있을 수 있는데 가장 쉬운 방법은 왼쪽에서 부터 포지션을 하나씩 늘려가면서, 현재 포지션의 왼쪽과 오른쪽을 Full Search한 후 왼쪽과 오른쪽의 가장 높은 높이를 찾고 그중 낮은 값을 답으로 하면된다. 상기 그림을 보면 왼쪽 포지션과 오른쪽 포지션을 보고 가장 낮은 포지션의 값인 2을 현재 포지션의 물 높이로 선택 하면 된다. 그런데 이렇게 full search 하게 되면 Height의 Size N 만큼 왼쪽으로 움직일 때마다 (N-1) 만큼의 Search가 매번 필요하다. 수식으로 하면 O(N*(N-1))이 ..