https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_double_slice_sum/

문제 분석

주어진 배열에서 최대가 되는 부분합을 찾아야 한다.

이때 조건으로 X, Y, Z 3개의 범위를 고려해야 한다.

X보다 큰 범위이어야 한다.

Y는 제외해야 한다.

Z보다 작은 범위이어야 한다.

`DoubleSlice의 합: A[X + 1] + A[X + 2] + ... + A[Y − 1] + A[Y + 1] + A[Y + 2] + ... + A[Z − 1]`

접근

head: 왼쪽 -> 오른쪽 방향의 부분합 / tail: 오른쪽 -> 왼쪽 방향의 부분합을 구함.

Y를 기준으로 head[i-1] + tail[i+1]의 최댓값을 구함.

A = [3, 2, 6, -1, 4, 5, -1, 2]일 때 두 배열의 누적합을 구하면 다음과 같다.

head = [0, 2, 8 7, 11, 16, 15, 0]

tail = [0, 16, 14, 8, 9, 5, 0, 0]

위 두 배열을 Y를 기준으로 head[i-1] + tail[i + 1]이 최대가 되는 값을 구하면,

Y를 기준으로 왼쪽 배열의 최대 부분합 + 오른쪽 배열의 최대 부분합을 구하는 것과 같다.

풀이

def solution(A):
    if len(A) == 3: 
        return 0
        
    head = [0] * len(A)
    tail = [0] * len(A)

    for i in range(1, len(A) - 1):
        head[i] = max(0, head[i - 1] + A[i])
    
    for i in range(len(A)-2, 0, -1):
        tail[i] = max(0, tail[i + 1] + A[i])
    
    max_sum = 0

    for i in range(1, len(A) - 1):
        max_sum = max(max_sum, head[i - 1] + tail[i + 1])

    return max_sum

참고

https://jaejade.tistory.com/121

https://gets-better.tistory.com/m/9

https://sustainable-dev.tistory.com/25

https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_profit/

문제 분석

주어진 배열에서 두 인덱스의 값의 차이의 최대값을 return

결과가 음수이면 0을 반환.

접근

배열을 탐색하면서 최솟값을 찾는다.

최솟값을 찾은 뒤에는, 더 큰 값을 만날 때마다 차이를 갱신한다.

단 result를 갱신한 뒤에, 최소값을 갱신해주자.

테케: [6, 3, 5, 7, 16, 1, 12, 19, 4, 5]

시간복잡도: O(N)으로 풀어야 한다. 배열의 길이가 [0...400,000].

풀이

def solution(A):
    result = 0
    min_value = 200001

    for i in range(len(A)):
    
        if min_value < A[i]: # 0 <= P <= Q < N일 때, A[Q] - A[P]가 양수인 경우만 판단. 음수는 어차피 0으로 반환해야 함.
            result = max(result, A[i] - min_value)
            
        min_value = min(min_value, A[i]) # 계산 이후 최솟값 갱신.

    return result

8. Leader lesson - Learn to Code - Codility

문제 분석

 배열을 쪼개, 두 배열 모두 같은 leader를 갖게 하는 index를 모두 return

의사 코드

 leftCount = 0, rightCount = 배열의 길이, leftLeaderCount = 0, rightLeaderCount = 0
 1 .leader 구함
 2. 배열 탐색하면 leader를 만나면
     leftLeaderCount += 1
     rightLeaderCount -= 1
leftSize += 1
rightSize -= 1
leftLeaderCount > leftSize / 2 && rightLeaderCount > rightSize / 2일 때, answer += 1

풀이

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    // leader 구한다.
    let sortedA = A.sorted()
    let candidate = sortedA[A.count / 2]
    var cnt = 0
    for elem in A {
        if candidate == elem {
            cnt += 1
        }
    }
    let leader = cnt > A.count / 2 ? candidate : -1 

    var leftSize = 0
    var leftLeaderCount = 0
    var rightSize = A.count
    var rightLeaderCount = cnt
    var answer = 0

    for elem in A {
        if elem == leader {
            leftLeaderCount += 1
            rightLeaderCount -= 1
        }

        leftSize += 1
        rightSize -= 1

        if leftLeaderCount > leftSize / 2 && rightLeaderCount > rightSize / 2 {
            answer += 1
        }
    }

    return answer
}

Dominator coding task - Learn to Code - Codility

의사 코드

 1. leader 후보 찾기
     배열을 탐색하며, size == 0이라며면,
         해당 값을 value에 할당한다. size += 1
     size == 0이 아니라면,
         새로운 값이라면, size -= 1
         새로운 값이 아니라면, size += 1
    
     2. 후보 개수 세기
     candidate = -1
     if size > 0이라면,
         candidate = value
     배열에서 candidate와 같은 값의 index를 저장한다.
     return candidate의 개수 > 배열의 크기 / 2 이면 ? index 배열 : - 1

풀이

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    var size = 0
    var value = 0

    for elem in A {
        if size == 0 {
            value = elem
            size += 1
        } else {
            if value != elem {
                size -= 1
            } else {
                size += 1
            }
        }
    }

    var candidate = -1
    var count = 0
    var idxArray = -1
    if size > 0 {
        candidate = value
    }

    for i in 0..<A.count {
        if A[i] == candidate {
            count += 1
            idxArray = i
        }
    }

    return count > (A.count / 2) ? idxArray : -1
}

StoneWall coding task - Learn to Code - Codility

문제 분석 (틀림)

문제 분석
막대 그래프를, 직사각형으로만 구성하기 위해 필요한 최소 개수는?
막대의 높이가 최대 10억이므로, 일반적인 탐색 문제는 아닌 듯하다.
왼쪽부터 현재 원소의 값(높이)를 기준으로, 연속으로 확장 가능한 너비를 측정한다.
현재 값보다 작은 값을 만나면 멈춘다. 직사각형을 1개를 구성한다.
    구성이 완료된 부분은, 각 원소에서 현재 값만큼 빼준다.
    직사각형 개수를 += 1
그런데 이렇게 하면, O(N^2)으로 시간 초과가 난다..

문제 분석 (구글링)

 스택에 저장된 높이와 현재 높이를 비교하면서 다음을 실행한다.
     1. 저장된 높이가 더 높은 경우: 현재 더 낮은 높이 블럭이 생길 것이므로, 이어지던 직사각형 생성 과정이 종료되었다. 이후 판단 과정에서 저장된 높이들이 필요 없어졌다. 현재보다 더 높은 블럭을 모두 스택에서 제거한다.
     2. 같은 경우: 아무 것도 하지 않는다. 블럭을 아끼는 것이다.
     3. 저장된 높이가 더 낮은 경우: 더 높은 새로운 블럭이 필요하다. 개수를 세고, 스택에 추가한다.

풀이 (구글링)

import Foundation
import Glibc

public func solution(_ H : inout [Int]) -> Int {
    var stack: [Int] = []
    var count = 0

    for element in H {
        while !stack.isEmpty && stack.last! > element {
            stack.removeLast()
        }

        if stack.isEmpty || stack.last! < element {
            count += 1
            stack.append(element)
        }
    }

    return count
}

회고

분명 Easy인데, 꽤나 어려운 문제였다.

인간의 직관과는 다른 컴퓨팅 사고가 필요한 문제에 여전히 고전한다.

이 문제는 3가지 케이스를 생각해내는 것이 핵심이다.

stack.top과 탐색 중인 element을 비교한다. 비교값은 3가지 케이스를 갖는다.

1. 같은 경우:
   1. 패스한다.
2. element가 더 작은 경우:
   1. stack의 더 높은 막대들은, element를 만들 수 없다.
   2. 동시에 1.의 케이스로 이어지던 직사각형의 생성 과정이 종료된다.
   3. 생성이 종료된 높은 막대들은 이후 판단 과정에 필요 없다. 모두 제거한다.
3. element가 더 큰 경우:
   1. 새로운 높은 막대가 필요하다.
   2. count를 증가시키고, stack에 element를 추가한다.

참고

https://rkdvnfma90.tistory.com/261

Nesting coding task - Learn to Code - Codility

의사 코드

 입력값이 "("인 경우:
     스택이 비어있으면 추가한다
     스택이 비어있지 않으면
         top이 ")"이면 return 0
         아니라면 추가한다.

 입력값이 ")"인 경우:
     스택이 비어있으면 return 0
     스택이 비어있지 않으면
         top이 "("이면 popLast()
         아니라면 return 0

 stack의 길이가 0이라면 return 1, 아니라면 return 0

풀이

import Foundation
import Glibc

public func solution(_ S : inout String) -> Int {
    var stack: [String] = []
    
    for currentB in S {
        if currentB == "(" {
            if stack.isEmpty {
                stack.append(String(currentB))
            } else {
                if stack.last! == ")" { return 0 }
                else { stack.append(String(currentB)) }
            }
        } else { // ")"
            if stack.isEmpty { 
                return 0
            } else {
                if stack.last! == "(" { _ = stack.popLast() }
                else { return 0 }
            }
        }
    }

    return stack.count == 0 ? 1 : 0
}

https://app.codility.com/programmers/lessons/7-stacks_and_queues/fish/

문제 분석

 인접한 원소가 다른 방향을 갖고 있다면, 싸움이 붙는다.
 싸움: 큰 물고기가 작은 물고기를 먹어버린다.
 물고기는 한 방향으로 계속 이동한다.

의사 코드

 순방향으로 탐색
 while stack이 비어있지 않고, 현재 원소가 올라가고, stack에 있는 원소가 내려가고 있을 때 판단
     if stack.last!.0 < currentElement.0
         stack.popLast()
     else 
				 flag = true // 현재 원소가 잡아먹힘 -> 더 할 게 없음.
		     break
if flag == false // 현재 원소 잡아먹히지 않음 -> stack에 추가
	append

나의 풀이

import Foundation
import Glibc

public func solution(_ A : inout [Int], _ B : inout [Int]) -> Int {
    var survivedStack: [(Int, Int)] = []

    for i in 0..<A.count {
        let currentElement = (A[i], B[i])
        var isEaten = false

        while !survivedStack.isEmpty && survivedStack.last!.1 == 1 && currentElement.1 == 0 {
            if survivedStack.last!.0 < currentElement.0 {
                _ = survivedStack.popLast()
            } else {
                isEaten = true
                break
            }
        }

        if !isEaten {
            survivedStack.append(currentElement)
        }
    }

    return survivedStack.count
}

NumberOfDiscIntersections coding task - Learn to Code - Codility

문제 분석

겹치는 원의 개수를 구한다
 겹치기만 하면 되니까, x축만 고려하자
 겹친다의 정의: i번째 원의 max 값 >= i+1번째 원의 min 값
 O(N^2)하면 쉽게 풀리지만, N = 100,000이므로 불가능

구글링

 시작점과 끝점의 배열을 각각 구한다
 각각 오름차순으로 정렬한다
 시작점 배열을 기준으로 탐색하며, 활성화된 원의 개수를 하나씩 추가한다
     다음 순서 원을 탐색할 때,
     현재 원의 시작점 < 이전까지 가장 큰 원의 끝점인지 확인한다.
         아니라면 조건을 성립할 때까지 탐색하며 활성화된 원을 제거한다.
     기존 활성화된 원의 개수를 정답에 더한다.
     정답이 조건을 넘어서면 -1을 반환한다.

참고한 풀이

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    let size = A.count
    var starts = [Int]()
    var ends = [Int]()

    for i in 0..<size {
        starts.append(i - A[i])
        ends.append(i + A[i])
    }

    starts.sort()
    ends.sort()

    var intersections = 0
    var activeDiscs = 0
    var endIdx = 0

    for start in starts {
        while endIdx < size && ends[endIdx] < start { // 겹치지 않는 상황
            activeDiscs -= 1
            endIdx += 1
        }
        intersections += activeDiscs // 지금까지 활성화된 디스크 수를 더하고
        activeDiscs += 1 // 디스크 수 + 1

        if intersections > 10_000_000 {
            return -1
        }
    }

    return intersections
}

회고

꽤 어려웠다. 코딜리티 문제는 난도가 들쭉날쭉하다.

시작점과 끝점 만을 고려한다는 것에는 접근을 했다.

그러나 정렬을 해도 된다는 생각을 하지 못 했다.

순서쌍을 구하는 것이 아니라, 카운트만 하면 되니까 정렬을 해서 따져도 문제가 없다.

점화식 만드는 훈련을 지속하자.

참고

https://study-ihl.tistory.com/175