문제 출처 : https://www.acmicpc.net/problem/1987
사고 과정
그래프 탐색이라는 심플한 방식으로 해결 가능한 문제라 생각했다. 맞네? 내 코드가 어떤 경우를 간과하고 해결 불가능.
결론은 내 조건이 잘못됐다.
초기에 작성했던 조건은 잘못된 조건으로 아예 삭제하여 코드를 수정했다.
하지만, 그럼에도 계속해서 시간초과 발생.
백트래킹을 이용한 문제로 여러 상황에 대한 적절한 가지치기가 올바르게 수행되어야 한다. 알파벳의 존재여부를 판단하기 위해 탐색시간이 작은 SET을 이용하여 작성하기로 했다.
놓친 부분
저번과 마찬가지로 문제의 조건을 이용해 예외 처리를 고려하자. ( 알파벳은 26개니까 26개가 됐다면 더 이상 진행할 필요 X )
좌측은 2%에서 틀렸습니다 발생. 우측은 그 이후도 돌아가다가 시간 초과 발생.
이건 또 시간초과가 발생하면서 다른거지... 혹시나 list 조회가 조금 더 시간의 지연을 발생시킬까봐 for문에서 in dic을 in range(4)로 바꿨지만 여전히 시간 초과가 발생한다.
2차원 형태의 list라 조회하는 데 시간이 더 걸리는 걸까?
-
2차원 형태의 list를 분해해서 하니 통과했다!! "2차원 형태의 리스트 조회는 시간이 더 걸리는 게 자명", 하지만 그럼에도 불구하고 시간이 많이 차이난다. 어디서 나는 걸까?
-
두 개로 나뉘어져 있던 if문을 and 구문을 이용하여 한 줄로 풀어내니 시간이 또 줄었다! 불필요한 부분은 생략하고 합치는 게 시간에 있어 효율적
별도로 문제에 대해 이모저모 공부한다고 안 이야기. dictionary의 탐색,삽입,삭제는 O(1)의 시간이 걸리지만 PYTHON dictionary는 hash table 기반으로 값을 변경하는 데 있어서는 overhead가 있어 최악의 경우 O(n)의 시간이 걸린다고 한다.
정말 많은 양의 데이터를 수없이 반복할때는 정말 작은 효율도 큰 결과를 낳는다는 의미를 생각하게 해 준 문제. 이런 사소한 효율 조차도 무시하지 않고 정확히 알아야 나중에 더 개선된 방식으로 코드를 짤 수 있다. 차근차근 여러 방식들을 적용시키며 시간 변화를 관찰할 수 있게 해준 문제. 그렇지만 다신 보고싶진 않다 ( 그래도 나중에 공부할 겸 다시 봐야지 )
