20922 겹치는 건 싫어 / c++ / Silver1 / 38분
문제 및 코드
접근 방식
투 포인터
- N개의 원소를 가진 주어진 수열의 부분 수열 중, 같은 원소가 K개 이하인 최장 부분 수열의 길이를 출력하는 문제
- 처음 생각한건 새로운 원소 A가 들어왔고, 방금 들어온 A로 인해 현재 부분 수열 안에 A의 개수가 K개를 넘은 경우, 부분 수열에서 가장 처음 발견된 A를 빼는 것이었다.
- 이를 위해, 각 원소의 삽입된 위치를 입력받기 위해 map<int, queue> 형식으로 기록했다. (원소의 개수는 queue 의 size)
- 현재 입력받은 A의 개수가 K개를 넘은 경우, map[A].front() 가 제거해야 하는 A의 위치를 나타낸다.
- 그럼 부분 수열이 시작한 부분부터 map[A].front() 까지의 원소를 제거하고, 부분 수열의 길이를 재계산하면 됐다.
- 이렇게 일단 문제를 해결하긴 했다. 하지만 시간, 공간 복잡도가 다른 C++을 사용한 풀이들에 비해 너무 높게 나왔다. (74360KB, 220ms)
- 더 최적화 된 풀이를 찾기 위해 생각한 것이, 우선 queue로의 삽입 삭제가 코스트가 높을 것으로 생각했다. 어차피 부분 수열의 길이를 계산하기 위해 시작 위치를 기억하고 있는거면, 그냥 시작 위치부터 다시 A가 나올 때까지 제거하면 되지 않을까 생각했고, 이렇게 제출하니 공간 복잡도는 10배, 시간 복잡도는 거의 2.5배 효율적으로 바뀌었다. (7556KB, 96ms)
- 하지만 그럼에도 빠른 사람들의 풀이에 비하면 비효율적이었고, 더 최적화를 진행해보았다.
- 다음으로 생각한 부분은, 1~100’000으로 연속된 원소에 접근하는데, 원소의 개수를 카운팅 하는 변수를 map으로 정했다는 점이엇다.
- 이 부분을 배열로 통으로 선언했고, 마침내 다른 사람들과 비슷한 수준의 시간 및 공간 복잡도로 문제를 해결할 수 있었다. (3192KB, 16ms)
다시 생각해 볼 점
- map 과 queue 같은 자료형은 꼭 필요할 때에만 사용해야겠다고 다시금 생각했다. 배열과 다른 자료형들의 시공간 복잡도의 차이를 여실히 체감할 수 있었다.
