In [3]:
# 1.1
# 시간 복잡도 O(n)
# 공간 복잡도 O(n)
# 문자열에 포함된 문자열이 전부 유일한지 검사하는 알고리즘을 작성하라
# 다른 자료구조를 사용할수 없는 상황이라면 어떻게 하겠는가?
"""
ex)
abcd -> True
abad -> False
질문을 먼저 하라!
각각의 문자들을 일일히 비교 해야 하는가? 이러면 시간복잡도는 O(n^2)이 된다.
다른 방법으로 생각해 봐야 한다.
해시를 이용해 보면 어떨까? 해시는 O(1)이다.
각 알파벳을 지나가면서 해시에 해당 위치를 True로 변경한다. 그럼 o(n)이다
해시값을 알아내서 그위치의 값을 True로 변경 할려고 보니 이미 True이다. 그럼 이건 중복이란 소리이다.
자! 아스키는 256개이다.
그런데 우리가 가지고 있는 문자열의 length가 256을 넘는다면 그건 보나마나 중복된 알파벳이 있다는 것이다.
그럼 이런거에 한해서는 위의 해시 로직을 안타도 된다.
"""
def isUniqChars(str):
if len(str) > 256:
return False
hash = [False] * 256
for ch in str:
if hash[ord(ch)] is True:
return False
else:
hash[ord(ch)] = True
return True
print(isUniqChars('abc'))
print(isUniqChars('aba'))
In [9]:
"""
아래는 set을 이용하는 방법이다.
"""
def isUniqCharsUsingSet(str):
if len(str) > 256:
return False
s = set()
for ch in str:
s.add(ch)
if len(str) != len(s):
return False
return True
print(isUniqCharsUsingSet('abc'))
print(isUniqCharsUsingSet('aba'))
In [12]:
# 1.2
"""
문자열을 뒤집어라
ex) "abc" -> "cba"
아래처럼 파이썬을 사용하면 금방 끝나지만
다른 방법을 사용해서도 해본다.
"""
def reverse_string(str):
return str[::-1]
print(reverse_string("abc"))
In [14]:
"""
스택을 이용할거다
먼저 스택을 준비하고
그 스택에 문자열의 각 엘리먼트들을 푸시한다.
팝을 하면서 스택이 빌때까지 뺀다
"""
def reverse_string_by_stack(str):
stack = []
for e in str:
stack.append(e)
result = ""
while len(stack) > 0:
result += stack.pop()
return result
print(reverse_string_by_stack("abc"))
In [27]:
print(chr(90))
print(chr(0))
print(ord('ÿ'))
print(hex(ord('ÿ')))
for i in range(0,257):
print(chr(i), end="")
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]: