공부하는 개발 블로그

1. 1개의 배열로 3개의 스택

index가 나머지가 0,1,2

2. 최솟값을 반환하는 min 연산 추가

push, pop, min 은 O(1)

스택 하나 더 선언(M)

def push(x):
	if x<S.top():
    	M.append(x)
    else:
    	M.append(S.top())
    S.append(x)
    
    
def pop():
	if len(S) > 0:
      x = S.pop()
      M.pop()
      return x
    
def min():
	if len(M) > 0:
      return M[-1]

3. 일정 용량을 초과하는 경우 새로운 스택 생성

class stackList():
	def __init__(lim):
    	self.stacks = [[]]
        self.stacknum = 0
        self.limit = lim
        
    def push(x):
    	if len(self.stacks[-1]) > self.limit :
        	self.stacks.append([])
            self.stacknum += 1
    	
        self.stacks[-1].append(x)

	def pop():
        if len(self.stacks[-1]) > 0:
        	x = self.stacks[-1].pop()
        if self.stacks[-1] == 0:
        	self.stacks.pop()
          	self.stacknum -= 1
        return x


SetOfStack = stackList(M)

4. stack 2개로 큐 하나 구현

class Q:
	def __init__():
    	self.S1 = []
        self.S2 = []
        
    def push(x):
    	self.S1.append(x)
        
    def pop():
    	for i in range(len(S1)-1):
        	self.S2.append(self.S1.pop())
        x = S1.pop()
        for j in range(len(S2)):
        	self.S1.apppend(self.S2.pop())
        return x

5. 스택 정렬

def getMax(S, sorted):
	if not S: return sorted
    M = 0
	for i in range(len(S)):
    	x = S.pop()
    	if M < x:
        	M = x
            sorted.append(x)
        else:
        	S.append(x)
	getMax(S, sorted)

6. cat and dog queue

큐 2개 이용

큐에 넣을 때 들어온 시간도 같이 저장.

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