백준 21941 자바 - 문자열 제거 (틀린 풀이 - 새로 작성한 풀이 링크 포함)

-- 이하 틀린 풀이이다. --

새로 작성한 풀이 : 링크

 

 

 

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

 

  풀고보니 DP로만 분류되있어서(알고리즘 분류 켜놓으면 너무 치트라 꺼놨음) 약간 의아했다. 내 경우엔 그리디로 풀었다. 물론 DP를 더 간단하게 생각하는 분들이 많겠지 ㅠ

 

1. 일단 a의 길이가 x보다 크거나 같다면 버린다. 예제 입력2의 경우를 처리하기 위해서이다.

 

2. 그다음 가장 점수를 많이 주는 녀석부터 하나씩 빼낼껀데, 단순히 'x'만 판단하면 안된다. 왜냐면 다음과 같은 경우가 있을 수 있다.

abcdefg 10
a 9

둘 다 '1'에서 걸러지지 않지만, 누가봐도 'a 9'를 쓰는게 이득임을 알 수 있다.

따라서 [ x / a의길이 ] 가 높은 순서대로 먼저 s에서 제거하면 된다. (따라서 그리디)

 

3. 뭐 char 배열로 직접 위치 찾아가며 연산하면 더 빠르겠지만, 일단 로직이 맞는지 확인하기 위해 문자열 연산(자바의 문자열 연산은 매우 느린편이다)으로 넣고 돌렸는데 130ms 정도 나와서 그냥 최적화는 안하고 넘어가기로 했다.

 

4. 코드의 's = s.replaceFirst(cur.a, "_");' 부분은, 예를들어 첫 번째 예제인 'abcxyzxabc'에서 xyz를 제거했다면 'abc_xabc' 처럼 만들기 위함이다. 저렇게 처리하지 않으면 다음과 같은 문제가 생긴다.

 

abcabc

2

ca 10

bb 5

 

예를들어 위와 같다면, 원래대로면 저 bb는 매칭되는 문자열이 없으니 사용 불가하다. 하지만 ca가 사라지면서 'abbc'가 되어 bb도 찾아지게 되버린다. 따라서 'ab_bc'와 같이 필요없는 문자를 넣어줘야 한다.