[백준 16719] ZOAC [Java]

 

문제

http://boj.ma/16719

요약

• 주어진 문자열을 만들기 위해, 문자를 추가해 만들어진 문자열들의 순서가 사전순이 되도록 만들자.
• 문자열의 길이 ≤ 100

---

풀이 과정

아이디어

만들어지는 문자열들의 순서가 사전순이 되기 위해서는, 사용하지 않은 문자 중 적절한 문자를 선택하는 기준은 아래와 같다.

• 전체 문자 중 사전순으로 가장 앞서는 문자
• 사전 순으로 동일한 문자 중 문자열의 앞에 위치한 문자

int idx = left;
for (int i = left + 1; i <= right; ++i) {
  if (S[i] < S[idx]) {
    idx = i;
  }
}

visited[idx] = true;

• 이전에 선택한 문자보다 뒤에 있는 문자
• 이전에 선택한 문자보다 앞에 있는 문자

recursive(idx + 1, right);
recursive(left, idx - 1);

문자열의 길이는 최대 100이므로, 완전 탐색이 가능하다. 재귀를 통해 이전에 선택한 문자열의 뒤/앞을 반복해서 탐색해주자.

최적화

주어진 조건에서 위 풀이가 유의미하게 개선될 여지는 없어보인다.

Map<Character, Set<Integer>>으로 문자와 동일한 문자들의 위치들을 미리 구해도, 적절한 문자 선택 기준 (3), (4)번에 의해 탐색 구간이 달라지므로 결국 완전 탐색이 필요하다.

성능 분석

• 시간 복잡도: $O(N^2)$
• 제출결과: Accepted / 104ms / 14156KB

---

회고

이미 정해로 문제를 풀어서 더욱 개선의 여지가 없지 않을까 생각했지만, 진짜로 최적화의 여지가 없을까 고민하다보니 Map과 Set으로 중복 문자를 효율적으로 처리하는 새로운 방법을 떠올리게 되었다.

하지만 탐색 구간이 유동적이므로 중복 문자의 위치를 미리 구하는 것이 의미 없다는 것을 알게되었다. 이를 통해 개선의 여지가 없다는 생각에 대해 구체적인 근거를 마련할 수 있었다.

주어진 환경을 의심없이 수용하기 보다, 스스로의 근거를 가지고 논리적으로 사고하는 과정이 재미있었다.

---

참고

문제

http://boj.ma/16719

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/16719.java