1. 배열과 문자열

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인지 확인한다