Programmer's Digest

위는 빠른 버전이고 아래는 느린버전이다. 최대 8자리수의 합을 구할때 빠른버전의 경우 최대 8번의 반복문을 돈다. 느린버전의 경우 Math.pow 내부에서 지수부분만큼 반복문을 돌게되므로 1+2+3+4+...+8 = 36번 돌게 된다. 위 문제를 백트레킹 방식으로 풀이할경우, 빠른버전의 경우 시간 복잡도는 10! * (8*10)*8이 되고 느린버전의 경우 시간 복잡도는 10! * (8*10)*36이 된다. 시간 제한이 2초 이기 때문에 시간이 아슬아슬하게 통과된다. 이 경우 무리하게 백트레킹으로 풀이하려고 하기 보다는 다른 풀이를 생각하는것이 안전하다고 생각한다.

   위 문제를 풀때, visited에 해쉬값을 다음과 같이 적용하여 계속 오답이 났다. String key = String.format("%s%s", front.row, front.col);  위와 같이 visited를 갱신하면 셀을 유일하게 구분할수 없는 경우가 생긴다. 예를들면, (1,11) 과 (11,1)의 경우에 둘다 key값이 "111" 이 되기 때문이다. 따라서 둘사이에 구분자를 추가하여 1 | 11 , 11 | 1이 서로 다른 key를 갖도록 수정하여야한다. 그리고 2차원 배열을 선언하는것이 괜찮다면 이차원 boolean 배열로 visited를 선언하는 것도 방법이다.

Python 풀이시 시간초과 발생이유 및 해결책 BFS시 que에 넣는 동시에 visited 배열을 갱신하지 않으면 동일 노드가 큐에 들어간다. queue를 사용시 list를 사용 append,pop을 할때 O(n) 시간 소요\ 해결법은 deque를 사용한다. 그외에 여러 해결책은 다음글 을 읽어보면 도움이된다.

이문제를 풀면서 특히 시간이 오래걸렸고, 왜 시간이 오래걸렸고 뇌정지가 왔는지에 대해서 생각해보았다. 내가 보기에 가장 큰 이유는 구현하기전에 확실하게 구현의 방향과 문제에 대해서 명확하게 머리속에 정리하지 않았기 때문이다. 보통 시뮬레이션 문제를 풀때, 시간을 아낄수 있는 방법은 풀기전에 구현에 대하여 명확하게 생각을 정리하는 것이다. 시뮬레이션 문제들은 정보량이 많고 개념도 낯선 경우가 많기때문에 문제를 먼저 정확하게 이해하는것이 중요하다. 문제를 정확하게 이해했다면 그에따라서 풀이를 어떻게 할지 고민해야하는데, 이때 어떤 자료구조,변수를 사용할것인지, 왜 사용할것인지 확실하게 머리에 정리해야한다. 그렇지 않으면 코딩을 하다가 구현의 방향을 바꿔야 하는 경우가 생기고 시간을 엄청 낭비하게 된다. 위 단계를 충실하게 수행했다면 실행결과가 예상과 다르더라도 머리속에 구현에 방향을 확실하게 정리했다면, 디버깅을하는데 시간이 덜 걸릴것이다. 또한 여러 예외사항을 생각할 여유가 생기게 된다.