날짜: 2022년 3월 11일 오후 11:09
코드
Algorithm/67258.py at main · Junroot/Algorithm
풀이
투 포인터로 문제를 풀면 된다.
start와 end 인덱스를 두고 start부터 시작하여 모든 보석을 가질 수 있는 end를 1씩 늘리면서 찾는다.
그 다음 start를 1늘리고 end를 다시 1씩 늘리며 찾는다.
보석의 개수를 세기위해 dictionary를 사용했다. 모든 보석이 있는지 확인하기 위해 dictionary의 모든 value 값을 곱해서 0이 아닌지 확인했는데 시간초과가 발생해서, 현재 dictionary에 value가 0인 보석을 저장하는 set을 별도로 만들어서 관리했다.
다른 사람 풀이를보니 value가 0인경우는 그냥 key까지 삭제 시켜서 모든 key가 있는지 확인하는 방법도 있었다.