[실수 분석] 2021 카카오 인턴 3번, 문자열

제목: [실수 분석] 2021 카카오 인턴 3번, 문자열  

단순 구현 문제였다.  

정확도는 통과가 되었지만, 효율성에서 반타작이 나왔다.

다른 사람 후기를 보아도 비슷하게 푼 것 같아 계속 원인을 찾아보다가 실수한 부분을 찾았다.

 

(2021. 5. 15 수정)

처음에는 split, component 메서드부분이 원인이라고 생각했지만,

다른 분과 이야기를 하면서 이 부분은 메서드 변경할때마다 성능차이가 나는정도의 성능향상이라면 큰 의미가 없는것 같다고 판단되었다.

커서가 100만개의 첫부분과 맨끝부분을 계속 이동하게 될 때 문제를 해결하는 방향으로 해결해야 했던 것 같다..

즉 세그먼트 트리, 펜윅 트리 + 이진탐색 등으로 커서 위치를 이동하는 부분을 해결해야 했던 것 같다.

 

(2021. 12. 22  수정)

세그먼트 트리 같은 알고리즘을 사용하지 않아도 이중연결리스트로 풀면 되는 문제였다.

 

도중에 테스트한 결과는 아래와 같다.

[split, component, String index접근에 각각 걸리는 시간 비교]

component: 3914.0666246414185 ms
String index분리: 2102.8331756591797 ms
split: 3291.561245918274 ms

걸린시간은 component > split > index분리 순으로 오래걸렸다.

 

아래 부터는 split, component 메서드부분이 원인이라고 생각했을 때 쓴 내용을 남겨둔다.

---

 

 

하나의 문자열을 여러개의 문자열로 분리하는 부분이 오래 걸리는게 원인이었는데,

 

예) 문자열 "U 12345" 을 각각  ["U", "12345"] 으로 분리해야 하는 상황

위 상황에서는 공백(" ") 이 단 1번만 나오는 경우라서

components<>(separatedBy:) 대신 다른 방법으로 구현하는게 더 효율적이었던 것이었다.

아마 components<>(separagtedBy:)로 구현한거였으면 원소 전체를 순회해야하니 O(n)이 필요했을 것이다.

 

위 문제의 부분을 아래처럼 수정했다.

// operation은 String
///  수정전
let split = operation.components(separatedBy: " ")
let op = split[0]
let n = Int(split[1])!
  
/// 수정후
let start = operation.index(operation.startIndex, offsetBy: 2)
let range = start..<operation.endIndex
let op = operation[operation.startIndex]
let n = Int(operation[range])!

 

수정한 후, 실행시간은 아래처럼 약 50% 단축되었다...ㅠㅠ

 

 

 

실수한 원인:

 

문자열을 다루는게 익숙하지 않아서 몇몇 강력한 메소드에 의존하던게 원인이었던 것 같다.

자주써버리는 메서드에 대해서 알아두는게 필요한 것 같다.