[백준 28270] Marked-Numbered [Python]

백준 28270 - 문제

백준 28270 - 입/출력

---

풀이

트리로 주어지는 목차의 정보를 글머리 번호 형태로 바꾸면 되는 문제다.

 

아래 조건에 따라 변환할 수 있다.

• i 번째 수가 i - 1번째 수보다 작다면, 상위 글머리 번호부터 변환해주어야 한다.
• i 번째 수가 i - 1번째 수보다 크다면, 글머리 번호 형태에 따라 1로 변해야 한다.
• i 번째 수가 i - 1번째 수와 동일하다면, 이미 존재하는 목차이므로 i - 1번째 수의 글머리 번호 형태 + 1로 변해야 한다.

 

먼저 i번째 수가 i - 1번째 수보다 작은 경우다.

상위 글머리 번호부터 변환해주어야 하기에 이전에 기록된 하위 글머리 번호에 대해 누적된 수들을 0으로 초기화 하는 과정이 시간초과의 원인이 되었다.

 

이번 기회에 알게 된 사실인데, 문제를 틀렸거나 부분점수를 얻은 경우 '내 제출' 란에서 언어를 클릭하면

아래 그림처럼 뭐 때문에 AC를 못 받은건지 알 수 있다. 이 사실을 몰라서 Mi <= 2에 대해 한참을 허탕쳤다.

나머지의 경우에 대해서는 아래처럼 풀이할 수 있다.

위의 조건에서 시간초과가 발생한 부분을 나머지 i번째 수가 i - 1번째 수보다 큰 경우에만 이전 값을 초기화하기위해 0으로 변환 후 값을 증가시켜 기록하는 방법이다.

 

이제는 올바르지 않은 보고서에 대한 처리를 해야한다.

보고서에 존재하는 번호가 C보다 크거나, 시작하는 보고서의 번호가 1이 아니라면 올바른 보고서가 아니므로 -1을 출력해야 한다.

---

소스코드

소스코드 보기

---

출처

28270번: Marked-Numbered