코테 이렇게 푸는 게 맞나?... '투 포인터'로 시간초과 해결
코딩 테스트 문제 하나가 계속 시간초과로 통과가 안 돼서 다른 사람 풀이를 봤는데, 거의 다 '투 포인터'라는 기법을 쓰더라. 이중 for문으로 O(n^2)이던 걸 O(n)으로 줄이는 방법.
배열 정렬하고 왼쪽, 오른쪽 인덱스를 조절하면서 찾는 건 알겠는데... 이렇게 하면 '최적을 보장'할 수 있는 이유가 직관적으로 잘 이해가 안 된다. 혹시 이 개념 키워드로 검색하거나 유튜브 영상 추천해줄 수 있는 분?
작성자 문과출신개발자149
3 개의 답변
ㅇㅇ 투 포인터 기본 중 기본이지 ㅋㅋ
작성자 클라우드러버365 · ▲0
나도 처음에 이해 안 됐는데, 직접 그림 그려보면 왜 O(n)인지 느낌 옴. left/right가 이동하는 횟수가 각각 n번이라 총 2n이니까 O(n)인 거고, 정렬돼 있으니까 조건에 따라 한쪽만 움직여도 답이 보장되는 구조. 영상보다는 'Two Pointer Two Sum'으로 검색해서 예제 하나 손으로 따라가 보셈. 코테에서 자주 나오니 익혀두면 좋음.
작성자 알고리즘고수234 · ▲0
글쎄... 그거 정렬이 된 배열에서나 성립하는 얘기 아닌가? 원본 순서 유지해야 하거나 정렬 못 하는 문제면 투 포인터 못 쓰는데. 문제가 뭔지에 따라 다른 거지, 이중 for문이 무조건 느린 것도 아님. 보장이 안 된다고 느끼는 게 오히려 맞는 직감일 수도 있음.
작성자 프롬프트장인345 · ▲0