본문 바로가기

알고리즘 문제408

[Leetcode][955] Delete Columns to Make Sorted II 문제 : https://leetcode.com/problems/delete-columns-to-make-sorted-ii/ ["ax", "ay", "ba", "bb"]를 입력값으로 예를 들어보면 1, 2행 "ax", "ay" 는 첫번째 열 a 가 같으므로 두 번째 열 x, y는 정렬이 되어야 한다.2, 3행 "ay", "ba" 는 첫번째 열 a, b 가 같지 않고 사전순정렬이 되어있기 때문에 두 번째 열 y, a는 정렬이 될 필요가 없다.(정렬되지 않아도 사전 순 정렬이 되기 때문에)위 개념으로 알고리즘을 생각해본다. A 요소 개수를 N, A[i]의 길이를 M이라 하자.N크기만큼의 bool형 배열(ordered)을 하나 만든다.ordered[i] = A[i-1], A[i] 는 사전순 정렬이 되어있는가.를.. 2018. 12. 16.
[Leetcode][124] Binary Tree Maximum Path Sum 문제 : https://leetcode.com/problems/binary-tree-maximum-path-sum/ 서브트리의 루트 노드를 기준으로 만들 수 있는 sequence들은 다음과 같다.1. 현재 루트노드, 루트노드의 왼쪽, 오른쪽 노드를 sequence로 가지는 경우. 2. 왼쪽 노드와 부모노드를 sequence로 가지는 경우왼쪽 자식노드 value가 오른쪽 자식노드보다 크고 root와의 합이 0이거나 양수인 경우이다. 3. 오른쪽 노드와 부모 노드를 sequence로 가지는 경우오른쪽 자식 노드가 왼쪽 자식노드보다 크고 오른쪽 자식 노드와 root노드의 value를 합한 값이 양수인 경우이다. 4. root노드만을 sequence에 포함시키는 경우이 경우는 왼쪽 자식 노드와 오른쪽 자식 노드.. 2018. 12. 10.
[Leetcode][948] Bag of Tokens 문제 : https://leetcode.com/problems/bag-of-tokens/ tokens 배열을 오름차순 정렬한다.tokens 배열의 앞에서부터 토큰을 power로 얻으면서 탐색해나간다. (앞으로 탐색중인 인덱스는 i, 토큰 배열 요소 값은 tokens[i]라 하자.)만약 탐색중에 남은 power로 tokens[i]를 얻을 수 없다면 토큰을 하나 돌려주고 가장 비싼 토큰(인덱스 r이라 하자. r의 초기값은 tokens 배열의 마지막 인덱스와 같다.)의 power부터 가져온다. (낮은 power로 큰 power를 얻은 것과 같다.)power를 가져온 뒤는 반드시 tokens[i]를 얻을 수 있다. 왜냐하면 인덱스는 i < r인데 오름차순 정렬했기 때문에 tokens[i] 2018. 12. 4.
[leetcode][945] Minimum Increment to Make Array Unique 문제 : https://leetcode.com/problems/minimum-increment-to-make-array-unique/ A 배열을 오름차순 정렬한다.그리고 unique한 값을 저장하는 변수를 하나 만든다.unique한 값의 초기값은 A배열에서 가장 작은 값과 같고A배열을 탐색해갈수록 1씩 커진다.A배열을 앞에서부터 탐색할 때,unique 값이 A[i]값보다 같거나 작다면 unique 값은 A[i]로 갱신시켜준다. (오름차순 정렬을 했고 조건이 1을 더하는 것이므로 1을 더해서 이후에 유니크한 값을 만드려면 현재 탐색 중인 값보다는 반드시 커야한다.)unique 값이 A[i] 값보다 크다면 A[i]는 unique값이 되기위해 값을 더해야 한다. 이 값이 정답에 더해진다. (ex. unique.. 2018. 11. 27.
[leetcode][946] Validate Stack Sequences 문제 : https://leetcode.com/problems/validate-stack-sequences/ poped배열을 앞에서부터 탐색하면서 가능한 순서인지 체크한다. pushed : 1 2 3 4 5 poped : 4 2 5 3 1 를 예로 들어보자. pop할 값 stack에 들어간 값 아직 stack에 들어가지 않은 값 1 2 3 4 5 4 1 2 3 5 5 1 2 3 3 1 2 2 1 1 위 테이블을 보면 pop해야 할 값이 아직 stack에 들어가지 않았다면 pop할 값이 나올 때까지 stack에 값을 넣는다. pop해야 할 값이 이미 stack에 있다고 한다면 stack의 top에 해당하는 값이 해당 값이어야 한다.문제에서 조건을 보면 poped배열 크기와 pushed 배열크기는 같고 모든.. 2018. 11. 25.
[leetcode][941] Valid Mountain Array 문제 : https://leetcode.com/problems/valid-mountain-array/ 배열 A의 크기가 3미만인 것들은 정답이 될 수 없다. (값이 증가하는 범위와 감소하는 범위가 존재하려면 적어도 3개의 값이 필요하므로)배열의 첫번째 값과 두번째 값을 비교했을 때 증가하지 않는다면 정답이 될 수 없다. (값이 증가하는 범위가 존재하지 않으므로)위 두 경우를 먼저 체크한다. 이후 배열의 연속된 값 2개를 비교하면서 다음을 체크한다.1. A[i-1] == A[i] : 값이 같은 경우 -> 정답이 될 수 없다.2. A[i-1] 이전에 값이 감소하는 경우가 나온경우 정답이 될 수 없다.3. A[i-1] > A[i] : 값이 감소하는 경우 -> 이후부터는.. 2018. 11. 25.

티스토리툴바