“괜찮아! 아직 코딩테스트까지 3일이나 남았어” 프로젝트 (1)

SoniaComp

·

Follow

2 min read

·

Mar 31, 2021

--

Share

2020 카카오 인턴십

1. 키패드 누르기
2. 수식 최대화
3. 보석 쇼핑
4. 경주로 건설

공식해설

문제 링크

참고

1. 문제분해

• 전체문제
  input: 보석 배열
  output: 시작 인덱스, 끝 인덱스
• 모든 보석을 하나 이상 포함하는 가장 짧은 구간을 찾기

2. 자료표현

• 배열의 크기는 최대 100000 이기 때문에 O(n²) 의 완전 탐색 알고리즘을 적용할 경우, 실패
• O(n)으로 탐색할 수 있는 투 포인터 알고리즘을 사용
• 모든 종류의 보석을 포함했는지 여부 확인: 딕셔너리 자료구조 사용
  (딕셔너리의 키 값 개수로 체크)

3. 일반화

• end 이동조건: 모든 종류의 보석을 포함하는 구간이 될 때까지
• start 이동조건: 모든 종류의 보석을 포함하는 동안
• start, end가 배열 인덱스보다 작은 동안 수행

4. 구현