[프로그래머스/Swift] 178870번 - 연속된 부분 수열의 합

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/178870

💡 구현 아이디어

s, e, sum을 선언하고 k보다 sum이 크면 s를 증가시키고 그렇지 않다면 e를 증가 시키면서 k와 sum이 같은 s와 e를 찾는다

찾았다면 기존의 result와 문제에서 제시된 조건을 기준으로 비교한다.

💻 코드

import Foundation

func solution(_ sequence:[Int], _ k:Int) -> [Int] {
  var s: Int = 0
  var e: Int = 0
  var sum = sequence[s]
  var result: (Int, Int) = (0, sequence.count+1)
  while s < sequence.count && e < sequence.count {
    if sum > k {
      sum -= sequence[s]
      s += 1
    }else {
      if sum == k {
        if result.1 - result.0 > e - s {
          result = (s, e)
        }else if result.1 - result.0 == e - s {
          if result.0 > s { result = (s, e) }
        }
      }
      e += 1
      if e < sequence.count { sum += sequence[e] }
    }
  }
  return [result.0, result.1]
}

❌ 틀린 이유 및 틀린 부분

합을 찾아야하니 완탐일거라 생각했다..

• 입력이 백만개의 요소를 가지니 O(n) 방법을 써야한다
• 시간초과 코드(완전탐색)

import Foundation

func solution(_ sequence:[Int], _ k:Int) -> [Int] {
  var sum: [Int] = [Int](repeating: -1, count: sequence.count)
  var result: (Int, Int) = (0, sequence.count+1) // $0: s, $1:e
  sum[0] = sequence[0]
  for i in 1..<sum.count {
    sum[i] = sum[i-1] + sequence[i]
  }
  for e in 0..<sequence.count {
    for s in 0...e {
      let value = (s == 0 ? sum[e] : sum[e] - sum[s-1])
      if value == k {
        if result.1-result.0 > e-s {
          result = (s,e)
        }else if result.1-result.0 == e-s {
          if result.0 > s { result = (s,e) }
        }
      }
      
    }
  }
  return [result.0, result.1]
}

⏳ 시간 복잡도

O(n) - s와 e가 sequence를 한번 순회

📌 풀이 또는 기억할 정보

투 포인터

• 해당 문제는 전형적인 투포인터 문제였지만 투포인터 방식을 몰랐기에 풀 수가 없었다… 비슷한 문제는 이젠 틀리지 않는다..

https://butter-shower.tistory.com/226

https://velog.io/@heyggun/Algorithm-Two-Pointers-Algorithm-투-포인터-알고리즘