20.07.20 개발일지 - 무어 기계(cont)

https://www.acmicpc.net/problem/3300

3300번: 무어 기계

어제도 상당히 복잡해서 하다가 말았는데 오늘도 역시 복잡했습니다.

꽤 시간을 투자 한 끝에서야 대략적인 구조를 완성 할 수 있었습니다.

 

일단 가정은 다음과 같습니다.

1. 비어있는 심볼에 공백 문자는 들어올 수 없다.

2. 비어있는 심볼 없이 일치하는 문장이 완성된다면 비어있는 심볼을 유일하게 유추할 수 없다.

 

사실 중요한건 2번입니다.

만약 2번이 성립하지 않으면 지금보다 더 복잡할 것입니다.

 

제가 생각하는 방식은 대략 다음과 같습니다.

1. 괄호가 열리면 높이를 1 증가시킨다.

2. 괄호가 닫히면 높이를 1 감소시킨다. 변화된 높이가 저장된 높이보다 1 작을 경우 입력 트리거를 킨다.

3. 알파벳('_' 포함)이 입력된 경우, 입력 트리거가 켜져 있으면 입력된 값을 Stack에 담는다.

4. '|'이 입력 되면 index를 저장하고 입력 트리거를 끈다.

5. 마지막 문자까지 연산이 마친 뒤 값을 비교한다.

문장에 '_'이 포함되어 있지 않고 예시 문자와 동일하다면 결과에 '_'를 저장하고 탈출한다.

문장에 '_'이 포함되어 있고 나머지 문자들이 예시 문자와 동일하다면 결과에 '_'에 대응하는 문자를 저장한다.

이 외에는 저장된 '|' index로 iterator를 이동시킨다.

 

현재 4번까지는 정리 되었고 5번만 구현해서 테스트를 하면 됩니다.

이렇게 구상한 이유와 기타 주의사항 등은 정답을 맞춘 뒤 작성하겠습니다.