HTTP:! HTTP:!

Queue를 이용해서 Stack을 구현하는 문제 python에서는 list에서 stack도 가능하고 queue도 가능하지만, list를 queue처럼 사용할 경우 속도가 느리다. O(1)을 보장하기 위해 Queue를 사용한다. 문제에서는 일단 list를 사용해서 myStack을 만들었고, 통과를 했음 class MyStack: def __init__(self): self.q = [] def push(self, x: int) -> None: self.q.append(x) def pop(self) -> int: return self.q.pop() def top(self) -> int: return self.q[-1] def empty(self) -> bool: return len(self.q) == 0 하지..

주어진 배열의 값이 화씨이고, 몇번째 뒤에 나보다 큰 온도가 나오는지 확인하는 문제 [73, 74, 75, 71, 69, 72, 76, 73] 만약 [0]번째인 73은 바로 1일 뒤에 74가 온다. 따라서 1일 뒤에 더 따뜻한 날씨가 나온다. [1, 1, 4, 2, 1, 1, 0, 0] 1) 이중 for문으로 풀어봤지만, 시간 초과 def dailyTemperatures(self, T: [int]) -> [int]: # 기본값이 0인 배열을 만드는 방법 2가지 # ans = [0] * len(T) # ans = [0 for _ in range(len(T))] ans = [0] * len(T) for i in range(len(T)): cnt = 1 for j in range(i+1, len(T)): if..

주어진 문자열에서 중복을 제거하고, 사전순으로 배치하는 문제 위 문제 처음 봤을 때는 for문으로 진행하면서 stack에 들어 있는지 파악하고, 없으면 push 중복 문자면 pop을 하면 된다고 생각했다. 그리고 sort해서 출력하면 되겠지 했다. 왜냐하면 예제 1번을 보면 그렇게 해석될 수밖에 없었다. Input: s = "bcabc" Output: "abc" 하지만 예제 2번에서 내가 생각한 방법대로 하면 절대로 값이 안나오는 것이다. Input: s = "cbacdcbc" Output: "acdb" 만약 내가 생각한대로 했다면 abcd가 된다. (사전순으로 정렬하므로) 2번 예제로 풀어보면, for문으로 s를 돌면서 1) 현재 값이 이미 포함되어 있는지 확인한다 -> 후순위로 밀리면 사전순에서 밀림..

오늘부터는 stack, queue 파트를 풀어본다. 문제 난이도는 쉬움 들어오는 문자열에서 기호의 쌍이 맞는지 확인하는 문제이다. ex) {}[]() -> True ] -> False ][ -> False 여는 기호가 있고, 닫는 기호가 있는데, stack에는 항상 여는 기호를 넣어두고, 닫힌 기호를 만나면 stack의 top과 비교해서 같으면 pop을 하고, 다르면 프로그램을 종료시키면 된다. 오늘 배운점은 not stack이면 empty stack을 의미한다. (빈배열) c not in table에서 table은 key값들만 검사를 한다. (value는 values()라는 함수를 이용하면된다.) python에서 삼항 연산자 사용은 다음과 같다 value if 조건 else value 예를 들어서 a가..

이 문제는 책에 나와 있는 풀이는 어려운편인것 같다. (내 이해도가 문제인가) Linked List문제는 손으로 그려보면 답은 보인다. 이 문제 역시 책으로 이해하려고 해보다가 손으로 그려서 해결한 문제이다. 특정 범위가 주어지고, 그 범위 안에 있는 Linked List를 뒤집는 문제이다. 1) Reverse 후에 앞, 뒤 연결은 어떻게 할것인가? 2) Reverse는 어떤 방법으로 할것인가? 2번 질문부터 답해보자, -> 나는 head앞에 prev라는 Linked List를 두고 기억하게 했다. 1번에 대해서는 cnt라는 변수를 두어, 세어 나가면서 m과 같을때 prev.next 를 reverse된 Linked List와 연결 시켰다. code는 더러운 편이다 def reversebetween(sel..

Linked List 순서를 홀,짝으로 구분해서 홀수 먼저 출력하고, 이후 짝수를 출력하는 문제 예를 들어, 1->2->3->4->5->NULL이면 홀수 자리는 1->3->5가 있고, 짝수 자리는 2->4가 있다, 따라서 결과 값은 1->3->5->2->4->NULL 1) 홀수와 짝수를 구분하여 넣는 Linked List를 만들고 2)홀수 마지막과 짝수 처음을 연결한다. 그림으로 설명을 해보면, 처음 odd와 even이라는 ListNode에 각 첫번째 홀수와 짝수 자리를 가르키도록 한다. 반복문이 진행때마다 2칸씩 건너뛰면서 다음 자료를 가르키도록 만들면 된다. 1) 처음에는 odd, even만 있고, while문을 통해서 계속 해서 연결해나간다. 2) 마지막에 odd와 even_first를 연결한다. ..

ListNode를 2개씩 짝지어서 swap하는 문제 주의할 점은 1) 두개씩 짝을 만든 ListNode가 있는지 확인(head, head.next가 None인지 아닌지 확인) 2) 주소값까지 확인하는것은 아닌거 같고, 값만 바꾸면 될것 같다. - 값만 교환하는 경우 def swapPairs(self, head: ListNode) -> ListNode: cur = head while cur and cur.next: cur.val, cur.next.val = cur.next.val, cur.val cur = cur.next.next return head - 리스트 자체를 교환하는 경우 리스트를 교환하려면 리스트가 가지고 있는 다음 값도 같이 교환해줘야된다. 그림에서 3->4를 교환한다고 하면 3의 next를..

홀수면 1을 빼고, 짝수면 2로 나눠가면서 0을 만드는 문제 def numberOfSteps(self, num: int) -> int: cnt = 0 while num != 0: if num % 2 == 0: num //= 2 cnt += 1 else: num -= 1 cnt += 1 return cnt