더보기
주석 포함 코드
class Node:
def __init__(self, key):
self.left = None # 맨 처음 생성시 빈상태가 맞음
self.right = None # 맨 처음 생성시 빈상태가 맞음
self.val = key
class BST:
def __init__(self):
self.root = None
def insert(self, key):
if not self.root: #루트
self.root = Node(key)
else: # 루트가 있는 경우, 루트를 지정해주고
curr = self.root
while True:
# 루트보다 클것이냐 작을것이냐를 확인해보면,
# 루트의 왼쪽부터 봐야하는지 오른쪽 부터 봐야하는지 알 수 있음
if key < curr.val:
if curr.left:
# 존재시 딱 현 위치 내려주는 것 까지만 하면됨.
# leaf노드 까지 가기위해서 이 작업을 하는 것임
curr = curr.left
else:
#leaf노드 도달 시 노드를 지정해줌
curr.left = Node(key)
break
else:
if curr.right:
curr = curr.right
else:
curr.right = Node(key)
break
def search(self, key):
# 서치도 루트부터 시작함. 현위치 잡는 변수를 항상 만들것.
curr = self.root
while curr and curr.val != key:
if key < curr.val:
curr = curr.left
else:
curr = curr.right
return curr
def solution(lst, search_lst):
# 이진 탐색 트리 생성
# search_lst의 각 노드를 이진 탐색트리에서 찾을 수 있는지 여부 반환 리스트 반환
result = []
bst = BST() # 객체 생성
for key in lst:
bst.insert(key) # bst객체가 insert메서드 호출
for search in search_lst:
if bst.search(search):
result.append(True)
else:
result.append(False)
print(result)
return result
class Node: #노드
def __init__(self, key):
self.left = None
self.right = None
self.val = key
class BST: # 이진트리 클래스
def __init__(self):
self.root = None
def insert(self, key):
if not self.root:
self.root = Node(key)
else:
curr = self.root
while 1:
if curr.val > key:
if curr.left:
curr = curr.left
else:
curr.left = Node(key)
break
else:
if curr.right:
curr = curr.right
else:
curr.right = Node(key)
break
def search(self, key):
curr = self.root
print('curr', curr)
while curr and curr.val != key:
if curr.val > key:
curr = curr.left
else:
curr = curr.right
return curr
def solution(lst, search_lst):
bst = BST()
for key in lst:
bst.insert(key)
result = []
for searchVal in search_lst:
if bst.search(searchVal):
result.append(True)
else:
result.append(False)
return result'코딩테스트 > 문제 풀이 - Python' 카테고리의 다른 글
| [프로그래머스 lv3]미로 탈출 (0) | 2024.03.20 |
|---|---|
| [프로그래머스 lv3]다단계 칫솔 판매 (0) | 2024.03.20 |
| 트리 순회 코드 작성하기 (0) | 2024.03.20 |
| [프로그래머스 lv2]예상 대진표 (0) | 2024.03.19 |
| [프로그래머스 lv2]메뉴 리뉴얼 (1) | 2024.03.18 |