백준 1294 자바 - 문자열 장식 (BOJ 1294 JAVA)

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

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01200/BOJ_1294.java

 

  쉬운줄 알고 덤볐는데 생각보다 어려웠지만, 결국 다 풀고보니 또 그렇게 어렵진 않았던 문제.

 

1. 기본 로직은 어렵지 않게 생각해볼 수 있다.

3
ABC
BCD
CDE

만약 입력이 위와 같다고 하자. 각 문자열의 순서를 해치지 않으면서 전체 문자열이 사전순으로 앞서게 하려면 결국 각 문자열에 pointer를 뒀다고 생각하고, 해당 문자열의 pointer가 가르키는 문자 중 가장 작은걸 순서대로 빼내면 된다.

즉, 위의 경우 다음과 같이 진행된다.

 

1.1 시작은 아래와 같다. 화살표가 현재 각 문자열에서 보고 있는 문자이다.

A,B,C 중 'A'가 가장 작으므로 'A'를 빼내서 출력하고, 빼낸쪽은 포인터를 전진한다.

1.2 그럼 아래와 같이 된다. 마찬가지로 B,B,C 중 'B'가 작으므로 B를 빼내자.

일단은 첫번째와 두번째 문자열 중 두번째 문자열에서 B를 뺐다고 치자.

1.3 그럼 다음과 같이 된다. 마찬가지로 'B'를 뺀다.

1.4 아래와 같이 되고, C,C,C 중에 일단은 맨 아래껄 뺐다고 하자.

1.5 다음과 같이 된다.  

이후 과정은 동일하게 진행되므로 글 없이 쭉 그려보겠다.

 

위의 과정을 통해 차례대로 'ABBCCCDDE' 라는 문자열이 출력되었다. 이 과정이 코드의 24~27 line에 해당한다. 이 때 포인터는 코드의 idxs[]에 해당한다.) 하지만 사실 위의 로직만 단순하게 진행해서는 답을 구할 수 없다.

( 그래서 많이 틀렸음 ㅋㅋㅋ )

 

 

2. 그럼 더 생각해봐야하는게 무엇이 있는지 다음의 예시를 확인해보자.

2
BA
BB

2.1 시작은 다음과 같다. 동일한걸 바라보고 있으니, 아무꺼나 빼보자. 일단 두번째껄 빼겠다.

2.2 다음과 같이 된다.  다시 둘 다 'B'를 보고 있으니 아무꺼나 빼보자. 아래껄 뺐다.

2.3 이미 이상함을 눈치챘을 것이다. 어쨌든 남은건 빼야하니, B와 A를 차례대로 뺀다.

최종적으로 출력은 'BBBA'가 됬다. 물론 이 입력의 정답은 'BABB'이다.

그럼 여기서, 맨 처음 '2.1'처럼 동일한 문자를 만날 경우, 그 뒤의 문자들을 비교해서 그 뒤가 더 사전순으로 작은 쪽을 선택해야 함을 알 수 있다.

마찬가지로 CBBBBBA와 CBBBBBB가 있다면 전자를 선택해야 한다. 따라서 바로 뒤 문자만이 아니라, 그 뒤로 끝까지 모든 문자를 비교해야 한다. (이 과정이 코드의 28~42 line에 해당한다.)

 

 

3. 근데 여기서 하나 더 있다. '2'에서 확장되는 얘기인데, 각 문자열의 포인터 뒤의 문자열의 길이가 다르게 남았을 때이다. 다음의 입력을 보자.

2
ZA
ZAA

와 같은 입력이 들어왔다.

 

3.1 시작은 다음과 같다. '2'의 과정에 따라 비교해보니 비교 가능한 곳 까지 비교해봐도 'A'로 동일하다.

그러니 일단 첫번째껄 빼보기로 했다.

3.2 다음과 같이 된다. 마찬가지로 'Z'를 뺀다.

3.3 이제 다시 동일한 문자를 본다. 역시 비교해보니 비교 가능한 위치까지는 전부 동일하다! 위에껄 빼보자.

3.4 다음과 같다. 이제 나머지 'A'들을 뺀다.

그럼 최종적으로 'ZAZAA'가 출력된다. 하지만 이 문제의 출력은 'ZAAZA'가 되야 정답이다. 즉, 비교 가능한 위치까지(두 문자열 중 남은 길이가 짧은쪽까지) 비교해봐도 동일한 경우에도 아무거나 빼면 안된다. 이 경우 '남은' 길이가 긴 쪽을 선택해야 함을 알 수 있다. (문제열 전체 길이가 아니다. 남은 길이가 긴 쪽을 선택해야 한다. 코드의 44~46 line에 해당한다.)

 

 

그럼 위의 설명을 코드로 구현하면 된다!

처음엔 대충 인덱스 각각 따로 잡아서 투포인터 문제들처럼 포인터 움직여가며 선택하면 될꺼라 생각했다. 그래서 뭐 끽해야 골드 하위정도의 그리디 문제라 생각했는데, 좀 더 깊게 생각해야 하는 부분이 있었던 문제였다. 풀고보니 플2였는데 플2받기엔 또 좀 쉬운것 같기도 하다.