Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[Algorithm] 문자열 압축 #10

Closed
2 tasks done
hwangJi-dev opened this issue Aug 3, 2022 · 0 comments
Closed
2 tasks done

[Algorithm] 문자열 압축 #10

hwangJi-dev opened this issue Aug 3, 2022 · 0 comments

Comments

@hwangJi-dev
Copy link
Owner

hwangJi-dev commented Aug 3, 2022

📌 TODO

  • 문제 풀이
  • 정리

🍉 문자열 압축

💬 Idea

  • 처음에 생각했던 방향

    • for문에서 stride를 사용해서 i에 일정 값을 더해서 문자열을 자른 다음 배열에 append해서 자른 문자열을 배열로 얻자!

      → 딱 떨어지는 수가 아닐 경우 out of range가 발생하는 문제가 생겼음

  • string을 length만큼 split할 수 있도록 extension을 만들어 사용하자!

    1. s.count + 1 만큼 for문을 돌며 extension으로 만든 split함수를 이용하여 s를 length만큼 자른 배열을 얻는다.
    2. 얻어진 배열을 탐색하며
      1. 이전 element와 같은 값의 element일 때
        1. 이전 element와 같은 값의 element라는 의미는 이전에 이미 문자열이 압축되어 count가 증가된 element가 append되었다는 의미이므로 append하기 이전에 removeLast()함수를 호출하여 가장 마지막 요소를 제거한다.
        2. count를 증가시키고 최종 string 배열에 증가된 count와 element를 합쳐 append한다.
      2. 이전 element와 다른 새로운 값의 element일 때
        1. count를 1로 초기화한다.
        2. 문자가 반복되지 않아 한번만 나타난 경우 1은 생략한다는 조건이 있기 때문에 count를 붙이지 않고 element만 최종 string 배열에 append한다.
      3. resultCnt의 초기값을 s의 최대 길이인 1000으로 두고, 최종 string 배열인 resultArr를 문자열로 합친 길이가 resultCnt보다 작을 때마다 resultCnt의 값을 바꿔 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return할 수 있도록 한다.

💬 풀이

func solution(_ s:String) -> Int {
    var resultCnt: Int = 1000
   
    for i in 1..<s.count + 1 {
        let arr: [String] = s.split(by: i)
        var temp: String = ""
        var count: Int = 1
        var resultArr: [String] = []
        
        for j in arr {
            if temp == j {
                count += 1
                resultArr.removeLast()
                resultArr.append("\(count)" + j)
            } else {
                count = 1
                resultArr.append(j)
            }
            temp = j
        }
        
        if resultCnt > resultArr.joined().count {
            resultCnt = resultArr.joined().count
        }
    }
    
    return resultCnt
}

extension String {
    func split(by length: Int) -> [String] {
        var startIndex = self.startIndex
        var results = [Substring]()

        while startIndex < self.endIndex {
            let endIndex = self.index(startIndex, offsetBy: length, limitedBy: self.endIndex) ?? self.endIndex
            results.append(self[startIndex..<endIndex])
            startIndex = endIndex
        }

        return results.map { String($0) }
    }
}

소요시간 : 2시간


💬 알게된 것

✅ stride(from: to: by:)

  • 시작 값에서 끝 값까지의 시퀀스를 지정된 양만큼 스테핑하여 반환한다.

  • from // start

  • to // end

  • by // stride (stepping)

    for countdown in stride(from: 3, to: 0, by: -1) {
        print("\(countdown)...")
    }
    // 3...
    // 2...
    // 1...

✅ indices

  • 안전하게 배열을 순회할 수 있도록 배열을 확장하여 안전하게 배열에서 값을 얻을 수 있도록 함
  • iOS 8 이상부터 사용가능하므로 firstIndex, endIndex를 사용하는 것을 더 추천!

✅ joined()

  • 배열을 문자열로 합칠 수 있는 메서드

    let ranges = [0..<3, 8..<10, 15..<17]
    
    // A for-in loop over 'ranges' accesses each range:
    for range in ranges {
      print(range)
    }
    // Prints "0..<3"
    // Prints "8..<10"
    // Prints "15..<17"
    
    // Use 'joined()' to access each element of each range:
    for index in ranges.joined() {
        print(index, terminator: " ")
    }
    // Prints: "0 1 2 8 9 15 16"

✅ index(_:offsetBy:limitedBy:)

  • 거리가 지정된 제한 인덱스를 벗어나지 않는 한 지정된 인덱스에서 지정된 거리인 인덱스를 반환합니다.

    // Declaration
    
    func index(
        _ i: String.Index,
        offsetBy distance: Int,
        limitedBy limit: String.Index
    ) -> String.Index?
    • 인덱스가 이동 방향으로 제한을 벗어나지 않는 한 인덱스 i에서 거리만큼 오프셋된 인덱스입니다.

      • 인덱스가 이동 방향으로 제한을 벗어나는 경우 메서드는 nil을 반환합니다.
      let s = "Swift"
      if let i = s.index(s.startIndex, offsetBy: 4, limitedBy: s.endIndex) {
          print(s[i])
      }
      // Prints "t"
      
      let j = s.index(s.startIndex, offsetBy: 6, limitedBy: s.endIndex)
      print(j)
      // Prints "nil"
  • 시간복잡도 : O(n) // n은 distance의 절대값

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant