[Two pointer] 16472번 고냥이

투포인터 고냥이 문제

 

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

16472번: 고냥이

 

투포인터와 Map으로 해당 문제를 풀수있다.

처음에 버벅였던게 크다.... 이문제는 진짜 혼자 오래동안 풀었다...열심히좀 해야겠다...(자기반성)

 

 

 

우선 소스에서 크게 볼부분이 있다. 투포인터는 탐색의 경우, 아주 유용하다 (부분합 구할때랑 동일)

투포인터는 문제를 풀때 항상 유념해야되는 부분이있다. 즉, index를 1크게 생각을 해야한다.

예를 들어보자

처음에 00으로 시작했다. 그리고, ed를 체크해서 ed에 1을 +해준다.

이때 ed는 1이지만, 아직 하위 로직에서 list는 , ++된 ed의 정보를 가지고있지않다.

즉, ed던, st던 미리 +1이 되고, 체크한다.

 

 

1. while문으로, 끝 부분이 배열의 길이와 같거나, 같지 않을때까지 돌린다.

2.answer은 최대 정답의 개수니까, list.size() <= num일때 체크를 해준다. (정답의 개수보다 적은 문자열이 나올수 있다)

3. map에서 get을할때 null 포인트 Exception이 떨어질수있을것을 대비해서 getOrDefault라는 메소드가 있다. 해당 메소드를 하면 없으면 0을 출력하고 있으면 그값을 출력한다.

 

list는 Map이다. 해당 알파벳의 카운트를 가진 String , Integer형태이다.

 

st가 증가해야할때는 st의 값을 빼주고 ++해주고

해당 문자열이 여러개일수있기 떄문에 1이면 제거를 해주고

아닌 경우에는 해당 값을 -1 해준다.

ed가 증가해야할때는 추가로 지금 가르키고있는 ed를 추가해주고, ++해준다.

 

해당 케이스에서 st-1, ed+1을 처리해야된다고 생각할수도있지만, 해당 index는 아직 list에 넣지 않은 ++된 값이다.

다음에 처리할 데이터라고 생각하면 편하다