[SWEA] 실전 문제 풀이

No1. 메모장 프로그램

실제 메모장 처럼 원래 있는 텍스트 문자열을 읽어들인 다음 커서의 위치에 삽입, 커서 옮기기, 그리고 커서 뒤에있는 특정 원소의 개수 찾기 총 3가지의 기능을 만드는 문제였다. 구상을 최소 한시간 그리고 1시간 반까지도 해도 된다는 코치님들의 말을 실천하고자 우선 펜 부터 잡았다.

처음에는 메모장의 최대 크기가 300*300 이여서 배열을 2배 사이즈로 놓고 짝수 인덱스는 커서 홀수 인덱스는 문자로 놓고 풀려고 했다. 하지만 조금만 더 생각 해보니 삽입 연산을 추가하면 문자들이 한칸 씩 뒤로 밀리게 되어 배열을 사용하면 절대 안될 것 같았다. 만약 구상을 하지 않았다면 배열로 열심히 구현하다가 눈물을 머금고 지울뻔 했다. 

그래서 삽입 연산에 유리한 링크드 리스트를 활용하려 하였고 우선은 답을 먼저 내기 위해 커서를 옮길때 현재 커서보다 뒤에 있다면 커서의 위치에서 바로가고 그렇지 않다면 처음으로 돌아오는 방법과 커서 뒤에 있는 문자를 셀 때 커서 위치부터 한 칸 씩 옮겨가며 확인하는 방법을 사용하였다. 그랬더니 총 25개의 테스트케이스 중 21개만 맞아 최적화를 하여야 했다.

커서의 접근을 편하게 하려면 중간에 특정 위치 정보를 저장하면 되겠다고 생각해서 임계값을 얼마로 하면 좋을지 생각하던 중 메모장이라는 것이 다시 눈에 들어왔고 행의 시작 위치 정보를 저장하면 되겠다고 생각했다. head 가 첫 행을 가리키고 있으니 전행의 마지막 주소값을 행의 시작 위치 정보로 저장해두면 되겠다고 생각했다. 그리고 삽입 연산이 이루어 질때 한칸 씩 밀려 주소값을 옮겨주어야 했는데 이때 전 노드의 주소값을 알고 있어야 하므로 자료구조를 이중 링크드 리스트로 바꿔주었다. 그랬더니 23패스가 떴다.

이제 부터는 커서를 옮기는 것을 최적화를 더 하기 힘들고 특정 원소의 개수를 찾는 것이 요령없이 다 하는 것 같아 이것도 행별로 찾으면 좋겠다고 생각했는데 행별로 일일이 다 확인한다면 별반 다르지 않을 것 같았다. 그래서 자고 일어나서 다시 문제를 보니 행 별로 원소의 개수를 저장하고 있으면 쉽겠다는 생각이 들어 추가를 하였고 상당히 짧은 실행시간으로 문제를 통과할 수 있었다.

사전 문제 풀이 부터 연습 문제 main 과 user 프로그램이 나뉘어있는 규모가 큰 문제들은 쉽게 풀 엄두가 안났는데 구상을 먼저 하니 그래도 갈피가 잡히는 것 같다. 앞으로도 이정도로만 원활하게 풀렸으면 좋겠다!  

 

---

 

거짓말같이 그 다음 10문제는 풀지 못했다고 한다..