[백준] 20442 ㅋㅋ루ㅋㅋ - 투 포인터 (Python)

문제링크

https://www.acmicpc.net/problem/20442

[20442번: ㅋㅋ루ㅋㅋ

어떤 문자열에서 몇 개의 문자를 지워서 부분 수열을 만들 수 있다. 예를 들어, ABC의 부분 수열은 ABC, AB, BC, AC, A, B, C와 빈 문자열이다.

www.acmicpc.net](https://www.acmicpc.net/problem/20442)

문제 총평

- 투 포인터를 사용하여 문자열을 탐색하는 문제이다.

- 문제는 어렵지 않으나 문자열의 길이를 보고 바로 투포인터를 생각하지 못한다면 어렵다고 생각이 든다.

문제 접근방식

- 처음에는 문자열의 최대 길이가 300만 이라는 것을 보고 당황을 하였는데 이렇게 범위가 클 때는 항상 알고있는 자료구조를 떠올리면서 접근을 하면 풀이법을 생각할 수 있습니다.

- 여기서 투 포인터를 생각할 수 있는 요소는 바로 문제 두 번째 조건입니다.

- 이 조건을 보면 문자열 양 끝 에 K를 붙인 문자열은 ㅋㅋ루ㅋㅋ 문자열이라고 나오는데 이 것을 보고 양 옆에서 접근을 하면 된다는 것을 알 수 있고 이것은 투 포인터를 사용하면 되겟구나 라는 힌트가 됩니다.

- 실제로도 투 포인터를 사용하면 O(N) 안에 문제를 풀어낼 수 있고 N의 최대가 300만이니 충분히 통과할 수 있을 것이라는 판단을 하였습니다.

정답코드

arr = [*input()]
ans = arr.count('R')
st,fi = 0, len(arr)-1
lst = {'R' : ans, 'K' : len(arr)-ans}
if ans == len(arr) or lst['R'] == 0: pass
else:
    cnt = 0
    while st < len(arr) and fi >=0 and st < fi:
        cnt += 1
        while st < len(arr) and arr[st] != 'K':
            lst['R'] -= 1
            st += 1
        while fi >= 0 and arr[fi] != 'K':
            lst['R'] -= 1
            fi -= 1
        if not st < len(arr) or not  fi >=0 or not st < fi or lst['R'] <= 0: break
        ans = max(ans,lst['R'] + cnt * 2)
        st += 1
        fi -= 1
print(ans)

1. 먼저 전체 문자열의 R의 개수를 세줍니다. 이렇게 하면 K를 사용하지 않은 최대 문자열을 바로 얻을 수 있습니다.
2. 두 번째로는 lst라는 R과 K의 개수를 세는 딕셔너리를 만들어 주는데 이것은 이후 투 포인터에서 특정 K 사이의 R의 개수를 즉시 알 수 있게 해줍니다.
3. 첫 번째 조건문에서 ans가 문자열의 길이가 같음을 비교하는 것은 문자열에 R만 있다면 그거 자체로 정답이기 때문입니다.
4. 그 뒤의 R의 갯수가 0인 상황은 ㅋㅋ루ㅋㅋ 문자열이 없는 것이므로 마찬가지로 뒤의 코드는 진행하지 않습니다.
5. else 구문으로 가보면 st,fi 두 변수로 문자열의 앞뒤를 체크하는데, 여기서 중요한 점은 구하는 ㅋㅋ루ㅋㅋ 문자열 에서 앞 뒤로 붙어 있는 K의 개수를 정하고 가는 것입니다. 이렇게 하면 이미 lst에서 K 사이의 R의 갯수를 알고 있기 때문에 바로 ㅋㅋ루ㅋㅋ 문자열의 길이를 알 수 있습니다.
6. 이제 K의 개수를 한개 씩 늘려가면서 K의 개수와 그 사이의 R의 개수를 더하여 미리 구해 놓은 ans와 비교하여 정답을 구하게 됩니다.

문제 풀이 후 생각

- 2번의 오답 후 정답을 내었는데 이 이유는 조건을 정확히 따지지 않았기 때문입니다.

- 투 포인터 자체는 잘 적용 하였는데 첫번째 실패에서는 st와 fi가 엇갈렸을 때 ans를 구하는 것이 아니라 종료를 해야하는데 그 점을 적용하지 않아서 실패 하였고 두번째 실패에서는 R이 0보다 작아 졋을 때 종료하는 것을 하지 않았습니다.

- 전반적으로는 쉬운 문제 였지만 투 포인터라는 것을 떠올리기 힘든점과 딕셔너리에 R과 K의 개수를 미리 구해 놓는다는 발상이 떠올리기 힘들어 골드 2 이지 않나 생각이 듭니다.

모르는게 있다면 댓글 남겨 주시면 바로 답해드리겟습니다 ^^