스위프트로 알고리즘 문제 풀다가 시간초과가 났다

시간 초과

틀렸습니다! 는 단념할 수 있겠는데, 시간초과 혹은 메모리초과를 보면 단념이 안 된다.

내 문제가 아니라 스위프트 언어의 문제인 것 같고… 실제로 입출력을 받을 때 내장된 함수가 문제였던 경우가 있긴 했지만, 사실은 내 알고리즘 자체의 문제가 더…

그렇기에 일단 내가 다시 이 글을 보게 된다면 가슴에 손을 얹고! 먼저 체크할 사항이 있다.

• 반복문 종료 조건 제대로 확인 했냐
• dfs/bfs/dp 방문 했는지 체크 제대로 했냐

가슴에 손을 얹고 생각 해 봤는데 아무래도 조세호라면 아래를 읽어보자..

입력

map 대신 compactMap

입력을 받을 때 보통 readLine()!.split(separator: " ").map{Int($0)!} 이렇게 받는데, 여기서 사용하는 map을 compatMap으로 바꾸어보자.

map 과 동일하게 각 요소에 특정한 변화를 (ex - String to Int) 줄 수 있는 메소드지만, 다른 점이라면 nil 값에 대한 강제 변환을 해야 했던 map 과 다르게 메소드 자체에서 nil 값을 건너뛰어버린다. 내부적으로 어떻게 처리하는지는 구현된 코드를 봐야 알겠지만, 그만 알아보도록 하자.

여튼 다른 코드는 100% 똑같은데 딱 map을 compactMap으로 바꾸어 맞았습니다!! 를 본 문제는 백준-나무자르기(2805)다. (21.07.12 기준)

Int($0) 대신 Int(String($0))

compactMap을 썼는데도 그런다!? 근데 나는 입력받은 문자열을 숫자 배열로 변환하고싶다!? 라면 Int 대신 String->Int를 해 보자.

스위프트 문법보다 문제에 머리를 더 빨리 갖다박았던 과거의 나는 문자열 다루기가 이렇게 어려운 줄 몰랐다. 그냥 char형만 알아서 인덱스로 각 문자에 접근했던 C 쪼렙의 나는 스위프트에 정신을 잃었다…(String, Character, Substring… 그리고 얘는 그냥 배열처럼 쓰면 안 된다. 따로 범위도 있고… 아직도 잘 모름 ㅜㅜ 공부해야겠다,,,)

여튼 map을 통해 문자열을 각 문자로 쪼개는 작업을 통해 우리는 Substring을 얻는다. 이게 뭐냐 싶어서 검색 해 봤는데, String의 부분이라고 한다.(공식문서)

그래서 왜 Substring을 String으로 변환한 뒤 Int로 바꾸는 게 바로 Int로 타입캐스팅 하는 것보다 빠르냐?!는 사실 다른 분의 블로그를 보고 어렴풋하게만 이해했다. 대충 내부적으로 String -> Int가 빠르게 구현되어 있고, String protocol -> Int가 느리게 구현되어있기 때문이다. 실제로 위 블로그에서 내부 코드를 분석 해 주었는데, 그 안에서 fastpath, slowpath와 같이 네이밍 자체도 저렇게 돼있었다.

이것도 다른 코드는 100% 똑같은데 딱 Int($0) 를 Int(String($0))로 바꾸어 맞았습니다!!를 본 문제는 백준-퇴사2(15486)이다. (21.08.11 기준)

FileIO

진짜_최종_안될때.github

이건 최종보스때나 쓸 것 같아서(그리고 코드 이해를 하지 못해서) 링크로 대체한다. 라이노님이 구현한 FileIO

세상엔 정말 똑똑하고, 자신이 가진 지식을 아낌 없이 나눌 줄 아는 사람들이 많다. 공부하기 좋은 세상이다. 감사합니다…

자료구조, 알고리즘

솔직히 이건 내 알고리즘의 문제가 9할일 거라 생각하지만, 그래도 혹시나 해결의 실마리가 된다면 좋으니 공유한다!

큐 구현해서 쓰기

스위프트에는 내장 큐가 없다. 그래서 내가 직접 구현해서 써야 한다. 그렇기 때문에 안 썼다가 시간초과가 난 문제가 있다. 백준-토마토(7576) (21.07.24 기준)

일단 다른 건 또옥같은데 딱 큐를 배열 + removeFirst()로 쓰다가 구현해서 쓰니까 맞았습니다!!가 떴기 때문에 이렇게 지레짐작 한 것이다. 근데 또 다른 문제들을 풀 땐 오히려 이중 배열이나 딕셔너리 배열이 더 빨랐기 때문에 확신할 수 없다.

여튼 나는 큐를 이렇게 구현해서 사용했다.

다른 탐색법 찾기

제곧내…

예를 들어 이진탐색이라거나… 이진탐색이라거나…

공부가 필요해!

문제를 풀면서, 또 이 글을 쓰면서 다시 한 번 나의 한계를 느꼈다!

어설프지만 문제에서 어느정도의 시간복잡도를 가질까 고민해보기도 하고, 다른 방식을 계속 찾아보기도 하지만 결론은 내 능력 부족이 가장 크다.

조금 더 많은 문제를 풀고 더 좋은 풀이를 보고 조금 더 구체적으로 구현된 방식이나 이런 걸 파다 보면 좋아지겠지? 싶다. 또 다른 유형의 시간 초과가 뜨면 업데이트 하러 와야겠다.

잘못된 부분이나 더 나은 방향이 있다면 언제든 알려주세요!