반응형 1시간30분1 [BaekJoon/백준] 1620번 C++ C++ 을 연습하는 중인데 이 문제 덕분에 pair와 vector에 대해 조금 더 공부하고 이해하는 시간을 가질 수 있었다. 다만 덕분에 시간을 좀 많이 투자했다 ㅜㅜ 이 문제는 아무런 조치 없이 선형검색으로 하다가는 시간초과가 나게 된다. N , M의 범위가 100,000 이기 때문에 주어진 2초 안에서 얼핏보면 O(n)에서시간초과가 일어나지 않을 것 같지만 테스트케이스 단위가 아니라 한번에 받는 것이기 때문에 아마 주어진 시간은 모든 검색에 대한 사항인 것 같고, 게다가 문자열의 길이가 20이기 때문에 시간복잡도가 상당히 길어질 것이라는 것을 종합적으로 생각해줘야 한다. 이 문제는 검색에 있어서 문자열 검색 : O(log n) 숫자 검색 : O(1) 로 구현하면 된다. 문자열 검색을 위해서 vecto.. 2021. 3. 26. 이전 1 다음 반응형