가장 가까운 같은 글자(c++)

입력 : 문자열 s ( 1 ≤ 길이 ≤ 10,000, 소문자 )

sol

1. 글자 위치를 표시하는 벡터 v 만들기 (a ~ z)

vector<int> v('z' - 'a' + 1, -1);

• 'z' : 122
• 'a' : 97
• 알파벳 숫자는 총 26개, 122 - 97 = 25 → 1 추가

2. s 알파벳 하나씩 확인하며 v값, answer값 작성

고민

• map을 사용한다면?

vector	map
벡터의 index로 값을 접근하는 시간복잡도 : O(1) 현재 풀이로는 s의 길이만큼 for문이 돌아감 → 시간복잡도 : O(s의 길이) = O(n) 공간복잡도 : s의 길이(answer) + 26(알파벳 개수) = O(n + 26) = O(n)	map 참조 : O(logn), 삽입 : O(logn) for문 내부에서 map 참조 및 삽입을 해야함 map에 값 존재 o → 시간복잡도 : O(nlogn) map에 값 존재 x → 시간복잡도 : O(2nlogn) = O(nlogn) 공간복잡도 : s의 길이(answer) + map크기(최대 26) = O(n + 26) = O(n)
시간복잡도 : O(n) 공간복잡도 : O(n)	시간복잡도 : O(nlogn) 공간복잡도 : O(n)

 

vector가 시간복잡도 상으로는 더 나아보인다..

 

C++ STL container 시간 복잡도 .. : 네이버블로그 (naver.com)

알고리즘 ) Red-Black Tree (tistory.com)

shin0112/programmers_cpp: programmers' coding test solutions (github.com)

출처 : 프로그래머스 코딩 테스트 연습 - 가장 가까운 같은 글자, https://school.programmers.co.kr/learn/courses/30/lessons/142086