[백준] 문자열 게임 2

유승선 ·2022년 6월 11일
0

백준

목록 보기
18/64

꽤 흥미롭다고 생각한 문제를 풀어보았다. K만큼의 정수와 함께 문자열이 주어지는데 내용에 나와있는 3번과 4번의 조건을 잘 생각해서 출력을 해야하는 문제이다.

첫번째, abaaaba 라는 문자열이 주어졌을때 K는 3이다. 한 문자가 3만큼 반복되는 연속되는 문자열의 길이를 구하고 그 후에는 첫번째 글자와 마지막 글자가 일치하는 가장 긴 연속 문자열의 길이를 구해야한는데 첫 예시같은 경우에는 abaa 가 가장 길게 구할수있는 연속 문자열 답중 하나고 가운데에 있는 aaa 가 3번의 조건을 만족하는 K만큼의 문자를 가지고 있는 가장 짧은 문자열의 길이다.

이 문제는 어떻게 해결할수있을까? 나는 sliding window 방식이 맞다 생각했고 이 전에 리트코드에서 풀었었던 "Longest string without repeating characters" 문제가 떠올랐다. 리트코드에서 봤던 그 문제와 정말 유사하다고 생각했지만 다른 점을 뽑자면은 리트코드 문제에서는 문자가 한번 이라도 반복되면 repeating 에 속하기때문에 그 순간 바로 계산을 하면 됐었다. 그 후에는 기존에 있었던 위치를 계산을 했던 마지막 위치로 옮기면 됐었는데. 이 문제 같은경우는 K의 숫자가 다르고 계산을 했다 하더라도 바로 마지막 위치로 옮기는게 아닌 중간에 같은 문자가 발생한 어떤 위치로 옮기는 작업도 필요했기에 조금 더 어려운 문제가 아니였나 싶다. 물론 리트코드 문제같은 경우는 테스트 케이스 987개라는 악랄한 억지를 보여줬던거에 비해 이번 문제는 조금 더 수월한걸수도 있다.

개인적으로 구성을 잘했다고 생가하는 문제이다. 문자열이 담긴 벡터를 읽으면서 sliding window 방식을 기용했고 슬라이딩 윈도우 함수에서는 right 포인터를 움직이면서 계산을 다 했다. HashMap 을 벡터 형태로 만든게 눈에 띄는데 이것은 문자의 위치를 저장하기 위해서 생각해봤었다. 계산을 끝내더라도 해당 문자의 위치를 다음 위치로 옮길수있는 작업을 진행해보고 싶었고 결과적으로 잘 먹혔던거같다. 만약 해당 문자가 가지고있는 위치가 K의 도달 할경우 제일 처음 발견된 위치에 left를 올린다음에 가장짧은 구간과 가장 긴 구간을 전부 계산해주었다. 그 후에는 더 이상 처음 발견된 위치는 필요없기에 과감하게 지워줬다.

점점 성장하는게 보여서 뿌듯하다.

배운점:
1. sliding window의 기본
2. hashMap 의 다양한 활용

profile
성장하는 사람

0개의 댓글