1. Hash Table
탐색
worst case : O(n)
average : O(1)
2. 가변 크기 배열
원소 삽입 : O(1)
크기를 두 배로 늘리는 시간 : O(n)
3. 문자열
이어붙이기 : O(n**2)
면접 문제
1.1 문자열에 같은 문자가 중복되어 등장하는가?
ans:
해시 테이블을 만들어서, 문자열을 순회한다.
문자열을 키로 가지도록 한다. 이미 존재하는 키인 경우 동일한 문자열이 존재한다.
시간 복잡도 : O(n) - 한번 순회하면 끝남 * 삽입과 탐색은 O(1)
공간 복잡도 : O(n)
1.1-1) 추가 자료 구조를 사용하지 않으려면?
for (i=0;i<s.length()-1;i++){
for(j=i+1;j<s.length();j++){
if s[i] == s[j] :
return True
}
}
return False
시간 복잡도 : O(n**2)
공간 복잡도 : X
1.2 두 문자열이 서로 순열 관계인지 확인하는 메서드
s1.sort()
s2.sort()
return s1 == s2
시간 복잡도 : 정렬 방식에 의해 결정
공간 복잡도 : X
2) hash table을 만들어서 각 문자열의 출현 빈도를 세서 비교한다.
1.3
모든 공백을 %20으로 바꾸어주는 메서드
s.replace(' ', '%20)
import re
pat = re.compile(' ')
re.sub(pat, '%20', s)
1.4
회문 순열
주어진 문자열이 회문의 순열인지 확인하는 함수
문자열을 순회하면서 각 문자를 키로 갖는 Hash Table을 만든다.
모든 문자가 짝수개 존재하거나, 하나만 홀수개 존재하고 나머지는 짝수개 존재해야한다.
1.5
문자 삽입/삭제/교체를 한 번 이내 수행해서 같은 문자열로 만들 수 있는지 확인하는 함수
if len(s1)==len(s2):
flag = False
for i in range(len(s1)):
if flag : return False
if s1[i] != s2[i]:
flag = True
return True
elif len(s1) < len(s2):
j=0
flag = False
for i in range(len(s1)):
if s1[i] != s2[j]:
if flag : return False
j += 1
flag = True
return True
else:
i=0
flag = False
for j in range(len(s2)):
if s1[i] != s2[j]:
if flag : return False
i += 1
flag = True
return True
1.6 문자열을 압축하자
aabcccaaa -> a2b1c5a3
만약 압축된 문자열이 더 길다면 기존 문자열을 반환하자
pre = None
zipped = []
c = 0
for i in range(len(s)):
if s[i] == pre:
c += 1
else:
zipped.append(pre + str(c))
pre = s[i]
zipped = ''.join(zipped)
if len(zipped) > len(s): return s
return zipped
1.7 행렬을 90도 회전시키는 메소드
행렬을 추가로 사용하지 않고도 가능한가?
temp = M[i][j]
W = len(M[0])
H = len(M)
for i in range(len(M)//2):
for j in range(i,len(M[0])//2-i):
temp = M[i][j]
for k in range(4):
M[i][j] = M[j][W-1-i]
1.8 0 행렬
m x n행렬의 한 원소가 0일 때, 해당 원소가 속한 행과 열의 모든 원소를 0으로 설정하는 알고리즘
1.9
s2를 두 번 이어붙이고, s1이 s2를 이어붙인 문자열의 substring인지 확인한다