자바 6137 자바 - 문자열 생성 (BOJ 6137 JAVA)

문제 : https://www.acmicpc.net/problem/6137

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/06100/BOJ_6137.java

 

  문제에 제시된 '예제 입력 1'을 기준으로 그림을 그려보면 다음과 같다.

위와 같이 문자열이 있고, head가 앞쪽 tail이 뒤쪽을 가르키는 포인터라 생각하면 된다.

그리고 head는 우측으로, tail은 좌측으로 진행하면서 사전순으로 더 작은 character를 선택하면 된다. (A<B<C<D)

 

 

우선 그럼 모든 문자가 다른경우를 한번 봐보자. 문자가 ADBC 라고 하자.

1. head는 'A', tail은 'C'다. 'A'가 더 작으므로 head를 선택하고, head는 오른쪽으로 한 칸 전진한다.

2. 'D'와 'C' 이므로 tail쪽이 더 작다. tail을 선택하고 왼쪽으로 한 칸 전진한다.

3. 'D'와 'B' 이므로 'B'를 선택한다.

4. head와 tail이 동일하므로 아무꺼나 선택한다.

 

그냥 이렇게 진행하면 되는 간단한 투 포인터 문제이다.

 

 

다만 head와 tail이 가르키는 곳이 동일한 문자일 때가 문제다.

다시 예제 입력 1을 보자. 위의 설명으로 여기까진 쉽게 올 수 있다. A와 B가 선택된 모습이다. 이제 head와 tail이 동일한 문자를 가르킨다.

이 때 어떤걸 선택해야 하냐면, head에서 i번 우측으로 간 문자와 tail에서 i번 좌측으로 간 문자를 비교해서 미래에 더 빠르게 작은 문자가 나오는 쪽을 선택하면 된다. (i=1이상). 이 때 둘이 같다면 i를 더 늘려서 진행해본다. head와 tail이 겹칠 때까지 진행하면 되므로, i의 범위는 [1 ~ (tail-head+1)/2] 이 된다(혹은 while(tail>head) 처럼도 가능하다)

만약 위의 과정으로 봐도 모든 head+i와 tail-i가 동일했다면 아무거나 선택하면 된다!

왜 그렇냐면 CABC가 있을 때, 만약 tail쪽의 C를 먼저 선택하면 최종 결과는 CBAC가 되기 때문이다. 정답은 head쪽의 C를 먼저 선택한 CABC 이다. 몇 가지 예제를 진행해보면 쉽게 이해할 수 있을 것이다.

 

 

그럼 이하 ACDBCB에 해당하는 그림을 추가 설명 없이 쭉 그리겠다.

 

이제 이걸 코드로 구현하면 된다. 제 경우엔 16line처럼 매번 (tail-head+1)/2 번 확인하면서 head와 tail의 값이 서로 다른 문자일 때 까지 확인하고, 22~26line에서 선택된 문자를 출력하는 방식으로 진행했다.

 

한 가지 주의점은 80글자마다 새로운 줄로 출력해야 한다는 점이다. 이 때 만약 StringBuilder 같은곳에 담고 한 번에 출력하려고 한다면, '\n'을 80글자 마다 append 해주려 할 것이다. 이 때 \n 도 글자가 추가되는 것이니, 그 다음은 81번을 세야 한다는 점을 주의해야 한다. 아니면 제 코드처럼 그냥 바로바로 80글자씩 출력해주면 된다.