silvertaker   2년 전

이 문제 관련해서 스위프트 질문이 하나도 없어서 질문 올립니다.

제가 구현한 방식은 쌍방향 연결 리스트입니다. 모든 명령, L, D, B, Push 는 O(1) 이고 마지막에 결과를 출력해주는 것만 O(N)입니다. 혹시 아시는 고수 있으시면 도움을 한번 부탁 드립니다. 참고로 Stack 으로는 이미 풀었습니다.


nhg1113   2년 전

Swift의 readLine()함수는 거대한 하나의 데이터를 읽어오는데에는 시간이 얼마 들지 않습니다. 예) 길이가 10000인 string 하나

하지만 자잘하게 쪼개진 많은 개수의 데이터를 읽어오는데에는 시간이 눈에 띄게 많이 듭니다. 예) 길이가 1인 string 10000개

그렇지만 Swift에는 읽어오는 함수가 readLine()밖에 없습니다.

이런 경우 더 빠르게 읽어올 수 있게 라이노님께서 fileHandle을 이용해 새로 fileIO 클래스를 제작하셨습니다.

이 클래스를 이용하면 많은 개수의 자잘한 데이터들을 더 빠르게 입력받을 수 있습니다.

아래 링크에 라이노님의 fileIO 클래스 코드가 있습니다.

https://github.com/CrazyImSoFl...


이렇게 답과 직접적인 정보를 주면 안되는거 같긴 한데,(정확한 규칙은 잘 모르겠습니다.)

그런데 Swift는 이런 식으로 입력이 너무 느린데 그 해결법을 모르는 상황이 발생하기도 하고,

스탠다드 라이브러리의 제공도 없어서 직접 구현해야하는 경우가 대부분입니다.

특히 큐와 스택, 덱, 힙 이런 자료구조들도 나중에 직접 만들어서 사용해야할 것입니다.

(힙 까지는 라이노님이 클래스로 만들어두신걸로 압니다.)


그리고 Swift에 관한 블로그나 알고리즘 관련 글이 너무 적어서 이렇게 하루 걸러 정보를 얻게 되는 경우가 많아서 정보를 바로 올려드렸습니다.

silvertaker   2년 전

Swift 사용하시는 분들이 굉장히 적어서.. 답변이 아예 없을까 걱정했는데 정성스러운 답변 감사드립니다. 사실 C++로 그대로 구현하면 무난하게 통과될 것 같아서 답답했는데 그런 부분을 간과 했군요.. 시간 제한 있는 웹사이트 특성상 더 저수준 언어를 써야하나 싶기도 하고..ㅠㅠ 좋은 하루 보내세요!!

wapas   2년 전

빠른 입출력과 별개로 스택 풀이와 비교했을 때, 연산량이 많아서 그렇습니다.

직접 풀면서 스택 방법으로 44ms까지 단축이 되지만, 연결리스트로 하니까 시간 초과가 나네요.

Stack에서 1번 연산당 append, remove(혹은 pop) 하는데 O(1) 시간복잡도가 1번 일어납니다.

하지만 연결리스트는 1번 연산당 O(1) 시간복잡도가 7번 이상 일어난다면 44ms시간이 44*7로 308ms로 시간초과나게됩니다.

wapas   2년 전

위에 주먹구구식으로 계산하긴 했지만

쉽게 설명하자면

editor.back() 과 stack.popLast() 연산 수행 시간을 비교하면 stack.popLast()이 더 빠르기 때문에, editor.back()을 사용했을 때 시간 초과날 여지가 있다고 생각하면 될 것 같습니다.

사실 이와 별개로 Swift가 입출력 수행 시간이나 연산 수행 시간이 빨랐다면 C++처럼 연결리스트 풀이가 가능했을 것 같네요.

silvertaker   2년 전

44ms * 7에서 7은 아마 계산을 하나씩 계산했을떄 가장 오래걸리는 경우를 하신것 같고 (당연히 big O notation이니까) 아마도? 하나의 계산당 44ms씩 할당하신 것 같군요 (여기서 ?는 옵셔널입니다ㅋㅋㅋ). 어느 정도 어떤 말씀하시는지 이해한 것 같습니다. Swift로 풀이할 떄는 이런 부분도 계속 생각해줘야하는 것 같군요ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.