import json
from typing import Counter
from django import views
import django
# import requests

from django.views         import View
from django.http.response import JsonResponse



class GrammerView(View):
    def get(self, request):
        '''
        [ 값 교환 ]
        =======================
        a, b = 10, 20
        a, b = b, a
        print(a, b)
        => 결과 : 20, 10
        
        [ 출력 ] 
        =======================
        print("number : ", a, b, c)
        => number : 1, 2, 3
        
        print(i, sep=', ')
        => 1, 2, 3
        
        print(i, sep='')
        => 123
        
        print(i, sep='\n')
        =>
        1
        2
        3
        
        print(i, end=' ')
        => 결과 : 1 2 3 6 7 14 21 42
        
        =======================
            
        [ 반복문 ]
        
        @ For
        =======================
        1) i 증가
            for i in range(10):
                print(i)
            
            => 결과 : 0~9
            
        2) i 감소
            for i in range(10, 0, -2):
                print(i)
            => 결과 : 10, 8, 6, 4, 2
    
        2) 특정 조건에 해당하면 다시 반복문 처음으로 돌아가게하기
            for i in range(10):
                if i%2 == 0:
                    continue
                print(i) # 홀수만 출력됨
                i=i+1
                
                
            3) 특정 상황에서 반복문 멈추게 하기
            ** for ~, else~ 구문 : for 문에서 break가 걸리면, 실행되지 않는다. break가 걸리지 않을 때만 실행된다. 
            
                for i in range(1,11):
                    print(i)
                    if i>15:
                        break
                else:
                    print(11)

                    
                    
        @ While : 조건이 들어간다. i<=10이 참일 때, 반복문 중지
        =======================
        1) i 증가
            i=1
            while i<=10:
                print(i)
                i=i+1
            
        2) i 감소     
            i=10
            while i>=1:
                print(i)
                i=i-1
            
        3) 무한반복을 멈추게 하거나, 특정 상황에서 반복문 멈추게 하기
            i=1
            while True:
                print(i)
                if i == 4:
                    break
                i=i+1         
            
        4) 특정 조건에 해당하면 다시 반복문 처음으로 돌아가게하기
            ** 주의 while문에서 적용할 때는 i의 증감 연산자가 continue보다 먼저 오지 않으면, 반복문이 계속 돌게된다. 
            i = 1
            while i<10:
                i=i+1
                if i % 2 == 0:
                    continue
                print(i)
            
            => 결과 : 3, 5, 7, 9
            
            
        
        [ 반복문을 이용한 문제풀이 ]
        ==========================
        1) 1부터 N까지 홀수 출력하기
            input() :  값을 입력 받는다. ** 타입은 문자가 되므로 연산을 하고싶다면, int형으로 바꿔주어야함.
            
            n=int(input()) 
            for i in range(1, n+1):
                if i%2==1:
                    print(i)
                
        2) 1부터 N까지의 합 구하기
        
            sum=0
            n=int(input()) 
            for i in range(1, n+1):
                sum=sum+i
            print(sum)
        
        3) N의 약수 출력하기// 약수 : 1 부터 나 자신의 수까지, 나 자신과 나눠서 0이 되는 어떤 수 .
        
        n=int(input()) 
        for i in range(1,n+1):
            if n%i==0:
                print(i, end=' ')
        => 1 2 3 6 7 14 21 42
        
       
        
        [ 중첩 반복묵(2중 for 문) ]
        ============================
        for i in range(5):
            for j in range(5):
                print('*', end=' ')
            print()                                                                                
        
        * * * * *
        * * * * *
        * * * * *
        * * * * *
        * * * * *
        
        for i in range(5):
            for j in range(i+1):
                print('*', end=' ')
            print()    
                        
        *
        * *
        * * *
        * * * *
        * * * * *
        
        for i in range(5):
            for j in range(5-i):
                print('*', end=' ')
            print()        
            
        * * * * *
        * * * *
        * * *
        * *
        *      
        
        
        [ 문자열과 내장함수 ]
        ================================
           
        1) upper()  : 문자열 모두 대문자 전환 
            msg = "It is Time"
            print(msg.upper())      
            => IT IS TIME   
        2) lower()  :  문자열 모두 소문자 전환
            msg = "It is Time"
            print(msg.lower())   
            => it is time   
        3) find('T') : 처음 발견되는 T의 인덱스 번호
            msg = "It is Time"
            print(msg.find('T'))  
            => 6 
        4) count('T') : T의 갯수
            msg = "It is Time"
            print(msg.count('T'))  
            => 1
        5) [:2] : 0~1인덱스까지의 문자열 추출
            msg = "It is Time"
            print(msg[:2])  
            => It
        6) [3:5] : 3~4덱스까지의 문자열 추출
            msg = "It is Time"
            print(msg[3:5])  
            => is
        7) len(msg) : 문자열의 길이(공백 포함)    
            msg = "It is Time"
            for i in range(len(msg)):
                print(i, end=' ')
            => 0 1 2 3 4 5 6 7 8 9
        9) 문자열 리스트의 문자 하나하나 반환
        
        (방법1)
            msg = "It is Time"
            for i in range(len(msg)):
                print(msg[i], end=' ')
            print()
            =>I t   i s   T i m e
        
        (방법2)
            msg = "It is Time"
            for x in msg:
                print(x, end=' ')
            print()
            =>I t   i s   T i m e
        
        10) isupper() : 대문자면 true // 대문자만 출력
            msg = "It is Time"
            for x in msg:
                if x.isupper():
                    print(x, end=' ')    
            =>I T
        
        11) islower() : 소문자면 true // 소문자만 출력
            msg = "It is Time"
            for x in msg:
                if x.islower():
                    print(x, end=' ')    
            =>t i s i m e
            
        11) isalpha() : 공백은 X, 오직 알파벳일 때만
        msg = "It is Time"
        for x in msg:
            if x.isalpha():
                print(x, end='')    
        =>ItisTime
        
        12)  ord() : 아스키 넘버 출력(A ~ Z : 65 ~ 90, a ~ z : 97~122)
        
        tmp='AZ'
        for x in tmp:
            print(ord(x))
            
        tmp='az'
        for x in tmp:
            print(ord(x))
            
        
        13)  chr() : 아스키 넘버에 대응되는 문자 출력(A ~ Z : 65 ~ 90, a ~ z : 97~122)
        tmp=65
        print(chr(tmp))
        
        
        [리스트와 내장함수]
        ======================
        - 리스트 : 변수 하나하나를 나열하여 인덱스를 붙인 것. a1,a2,a3.. =>a[0], a[1], a[2]
        1) 빈리스트 만들기
                a = []
                print(a)
                b=list()
                print(b)       
                =>[], [] 
        
        
        2) 값이 있는 리스트 만들기 
            (1) a = [1,2,3,4,5]
            
            (2) b = list(range(1,11))
            
            (3) c=a+b
        
        
        3) a.append(6) # 리스트 멘 마지막에 값 6을 추가
            print(a)
        
        4) a.insert(3,7)# 3번 인덱스에 7을 추가, 나머지는 뒤로 밀림
            print(a)
        
        5) a.pop() # 리스트에서 마지막 값을 제거
            print(a)
        
        6) a.pop(3) # 3번 인덱스의 값을 제거
            print(a)
        
        7) a.remove(4) # 리스트에서 값 4 를 제거, 앞으로 당겨짐
            print(a)
        
        8) a.index(5) # 5라는 값이 몇번 인덱스에 있는지
            print(a.index(5))
            
            a=list(range(1,11))
        
        9) print(sum(a)) # 1~10의 모든 수의 합
        
        10) print(max(a)) # 최대값
        
        11) print(min(a)) # 최소값 
            print(min(7,5)) # 인자들 중 최소값       
            print(min(7,3,5)) # 인자들 중 최소값       
            print(max(7,5)) # 인자들 중 최대값    
        
        12) 무작위로 섞기
        
            import random as r
            
            r.shuffle(a) # 무작위로 섞기
            print(a)   
        
        13) a.sort() #오름차순
            print(a)   
        
        14) a.sort(reverse=True) # 내림차순
            print(a)   

        15) a.clear() # 빈리스트로 만들기
            print(a)   
            
        
        리스트와 내장함수(2)
        ========================
        a=[23, 12, 36, 53, 19]
        print(a[:3])
        print(a[1:4])
        
        1.  리스트 값 출력
        =====================
        방법 1)
            for i in range(len(a)):
                print(a[i], end=' ')
            print()
            =>23 12 36 53 19
        
            for x in a:
                print(x, end=' ')
            print()
            =>23 12 36 53 19
        
        방법 2)
            for x in a:
                if x%2==1:
                    print(x, end=' ')
            print()
        
        방법 3) enumerate()
            for x in enumerate(a):#(인덱스, value)의 형태로 튜플 반환
                print(x)
            =>  (0, 23)
                (1, 12)
                (2, 36)
                (3, 53)
                (4, 19)
        
            ** 튜플의 구조는 리스트와 같으나, 값을 변경할 수 없다.
                a = [23, 12, 36, 53, 19]
                a[0] = 43
                print(a)
                =>[43, 12, 36, 53, 19]
                
                a = (23, 12, 36, 53, 19)
                a[0] = 43
                =>TypeError: 'tuple' object does not support item assignment
            
        방법 4) x[0], x[1]
            for x in enumerate(a):
                print(x[0], x[1]) # x=(인덱스, value)이므로 x[0]은 인덱스 , x[1]은 값 
            =>
            0 23
            1 12
            2 36
            3 53
            4 19
        
        방법 5) 가장 많이 쓰는 enumerate 사용
            for index, value in enumerate(a):
                print(index, value)
            print()
            =>
            0 23
            1 12
            2 36
            3 53
            4 19
        
        방법 6) 가장 많이 쓰는 enumerate 사용
            if all(60>x for x in a): # 모두 충족하면 참
                print("YES")
            else:
                print("NO")

            if any(15>x for x in a): # 한가지라도 충족하면 참
                print("YES")
            else:                    # 모두가 충족안할때, 거짓
                print("NO")
            
        
        
        [2차원 리스트 생성과 접근]
        =========================
        a = [0] * 10 # 인덱스 번호가 0~9까지인 크기가 10인 일차원 리스트    
        a = [0] * 3 # 인덱스 번호가 0~2까지인 크기가 3인 일차원 리스트
        
        1)  for _ in range(3) // _를 하면 변수없이 반복문이 3번 돈다.
            a=[[0]*3 for _ in range(3)] # [0]*3 가 3번 반복됨.    
            print(a)
            =>[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
            열       
            행    0  1  2
            0 [0, 0, 0]
            1 [0, 0, 0]
            2 [0, 0, 0]
            
            열       
            행    0  1  2
            0 [0, 1, 0]
            1 [0, 2, 0]
            2 [0, 0, 0]
            
            a=[[0]*3 for _ in range(3)] # [0]*3 가 3번 반복됨.    
            a[0][1]=1
            a[1][1]=2
            print(a)
            =>[[0, 1, 0], [0, 2, 0], [0, 0, 0]]
            
        
        2) 2차원 리스트 표로 출력하기
            for x in a:
                print(x)
            =>
            [0, 1, 0]
            [0, 2, 0]
            [0, 0, 0]
            
        
        3) 대괄호없이 2차원 리스트 출력하기
            a=[[0]*3 for _ in range(3)] # [0]*3 가 3번 반복됨.    
            for x in a:
                for y in x:
                    print(y, end=' ')
                print()
            =>
            0 0 0   
            0 0 0
            0 0 0    
            
        
        
        [함수 만들기]
        =================
        # 함수는 값을 return 하며, 함수를 종료 한다.
            def add(a,b):
                c=a+b
                return c
            print(add(3,2))
            =>5
        # 파이썬에서는 2개이상의 값을 튜플로 반환할 수 있다.
            def add(a,b):
                c=a+b
                d=a-b
                return c, d
            print(add(3,2))
            =>(5, 1)
        
        # 소수(나누어 떨어지지 않는 수 )만 출력하는 함수 만들기(1~자기자신까지의 수중 1,과 자기자신을 제외하고 나누어서 떨어지지 않는 수)
            def isPrime(x):
                for i in range(2,x):
                    if x%i==0:
                        return False # 여기서 함수가 종료됨.
                return True


        a=[12, 13, 7, 9, 19]
        for y in a:
            if isPrime(y):
                print(y, end=' ')
        
        
            
        [람다함수]
        ====================
        - 람다함수 : 익명의 함수 또는 표현식
        
        def plus_one(x):
            return x+1
        print(plus_one(1))
        =>2
        
        # 람다함수(익명의 함수)로 표현하기(변수에 담아서 호출해주어야함)
        plus_two=lambda x: x+2
        print(plus_two(1))
        =>3
        
        
        * map(함수, 함수를 적용할 자료)
            a=[1,2,3]
            print(list(map(plus_one, a)))
            =>[2, 3, 4]
        
        * 함수 이름이 필요없이 익명의 함수를 사용하여 바로 사용할수있음.
            print(list(map(lambda x: x+1, a))) 
            =>[2, 3, 4]
        
            
        [선형 탐색, x의 위치 찾기]
        ====================
            L = [3,8,2,7,6,10,9]
            x = 6
            def linear_search(S, x):
                i=0
                while i<len(L) and L[i] != x:
                    i+=1
                if i < len(L):
                    return i
                else:
                    return -1    
                
            def linear_search(S, x):
                return S.index(x)
        
        
        [재귀 알고리즘]
        =============== 
        1) 잘못된 예시 -  종결 조건이 없음   
            def sum1(n):
                print(n)
                return n + sum1(n -1) # 자신을 재귀호출하고있음.
            # a = int (input("Number:"))
            # print(sum(a))
            Number:30
            30
            29
            28
            27
            26
            25
            24
            23
            22
            21
            -995..
            ..... 에러가 남....
            
            def sum2(n):
                print(n)
                if n<= 1:
                    return n
                else:
                    return n+ sum2(n-1)
            n=10일때 콘솔에 찍히는 결과 
            10
            9
            8
            7
            6
            5
            4
            3
            2
            1
            
            sum2(10) = 55
            a = int(input("Number:"))
            print(sum2(a))
            
        '''
        return JsonResponse({"MESSAGE": "Hello"}, status=200)
# 2. 선형 배열 알고리즘 풀이
class ProgrammersExample2View(View):
    def get(self, request):
        '''(02) 정렬된 리스트에 원소 삽입
        리스트 L 과 정수 x 가 인자로 주어질 때, 리스트 내의 올바른 위치에 x 를 삽입하여 그 결과 리스트를 반환하는 함수 solution 을 완성하세요.

        인자로 주어지는 리스트 L 은 정수 원소들로 이루어져 있으며 크기에 따라 (오름차순으로) 정렬되어 있다고 가정합니다.

        예를 들어, L = [20, 37, 58, 72, 91] 이고 x = 65 인 경우, 올바른 리턴 값은 [20, 37, 58, 65, 72, 91] 입니다.

        힌트: 순환문을 이용하여 올바른 위치를 결정하고 insert() 메서드를 이용하여 삽입하는 것이 한 가지 방법입니다.

        주의: 리스트 내에 존재하는 모든 원소들보다 작거나 모든 원소들보다 큰 정수가 주어지는 경우에 대해서도 올바르게 처리해야 합니다.
        '''
        x = 65
    
        L = [20, 37, 58, 72, 91]
        
        def solution1(L, x): # 풀이 실패 -> 시간 초과 및 반복문 멈추는 것 고려하지 않음
            answer = []
            for y in L:
                if x > y:
                    if L.index(y) != len(L)-1:
                        L.insert(L.index(y)+1,x)
                    else: L.append(x)
                elif x < y:
                    if L.index(y) == 0:
                        L.insert(0,x)
                    else:
                        L.insert(L.index(y)-1,x)
                        
            answer = L        
            return answer
        
        def solution2(L, x): # 풀이 실패 -> enumerate를 사용하였으나, 역시 시간 초과 및 반복문을 멈추는 것을 고려하지 않음.
            answer = []
            for index, value in enumerate(L) :
                if x > value:
                    if index != len(L)-1:
                        L.insert(index+1,x)
                    else: L.append(x)
                elif x < value:
                    if index == 0:
                        L.insert(0,x)
                    else:
                        L.insert(index,x)
            answer = L        
            return answer
        
        def solution3(L, x): # PASS!!!
            # 반복문이 계속 도는 것이 문제였으며, 이로인해 시간이 초과되는 것을 깨달음. 이를 잡아주니 풀이 성공!!!!! 
            for index, value in enumerate(L) :
                if x > value:
                    if index == len(L)-1:
                        L.append(x)
                        break
                    else:
                        continue
                else: 
                    L.insert(index,x)
                    break
            return L 
        
        def solution4(L, x): # 나와 비슷한 풀이
            for idx, num in enumerate(L):
                if num > x:
                    L.insert(idx,x)
                    break

                if L[-1] < x: # L[-1]은 리스트 맨 끝에 있는 수를 지칭 한다!!, 맨 끝자리이면서, x가 값이 크다는 것을 모두 충족함.
                    L.append(x)
                else:
                    pass
            return L
        
        def solution5(L, x): # 오름차순이라는 문제의 함정을 이용한 문제 풀이
            L.append(x)
            L.sort()
            return L

        return JsonResponse({"RESULT": solution3(L,x)}, status=200)

    def post(self, request):
        
        '''
        문제 설명
        인자로 주어지는 리스트 L 내에서, 또한 인자로 주어지는 원소 x 가 발견되는 모든 인덱스를 구하여 
        이 인덱스들로 이루어진 리스트를 반환하는 함수 solution 을 완성하세요.

        리스트 L 은 정수들로 이루어져 있고 그 순서는 임의로 부여되어 있다고 가정하며, 동일한 원소가 반복하여 들어 있을 수 있습니다. 
        이 안에 정수 x 가 존재하면 그것들을 모두 발견하여 해당 인덱스들을 리스트로 만들어 반환하고, 
        만약 존재하지 않으면 하나의 원소로 이루어진 리스트 [-1] 를 반환하는 함수를 완성하세요.

        예를 들어, L = [64, 72, 83, 72, 54] 이고 x = 72 인 경우의 올바른 리턴 값은 [1, 3] 입니다.
        또 다른 예를 들어, L = [64, 72, 83, 72, 54] 이고 x = 83 인 경우의 올바른 리턴 값은 [2] 입니다.
        마지막으로 또 다른 예를 들어, L = [64, 72, 83, 72, 54] 이고 x = 49 인 경우의 올바른 리턴 값은 [-1] 입니다.

        힌트 1: 리스트의 index() 메서드와 리스트 슬라이싱을 활용하는 것이 한 가지 방법이 됩니다. 리스트 슬라이싱은 아래와 같이 동작합니다.

        L = [6, 2, 8, 7, 3] 인 경우
        L[1:3] = [2, 8]
        L[2:] = [8, 7, 3]
        L[:3] = [6, 2, 8]

        힌트 2: 리스트의 index() 메서드는, 인자로 주어지는 원소가 리스트 내에 존재하지 않을 때 ValueError 를 일으킵니다. 
        이것을 try ... except 로 처리해도 되고, "if x in L" 과 같은 조건문으로 특정 원소가 리스트 내에 존재하는지를 판단해도 됩니다.
        '''
        x= 72
        L= [64, 72, 83, 72, 54]
        def solution1(L,x): # 나의 풀이 ) PASS!!
            answer =[]
            validate=True
            for indx, num in enumerate(L):
                if x == num:
                    answer.append(indx)
                    validate=False
            if validate:
                answer=[-1]   
            return answer
        
        def solution2(L, x): # 다른 풀이 : 리스트 컴프리헨션으로 깔끔하게!
            if x in L:
                return [i for i, y in enumerate(L) if y == x] # 조건문이 만족 할 떄, i를 리스트에 담는다.
            else:
                return [-1]
            
        
        
        return JsonResponse({"RESULT": solution1(L,x)}, status=200)
    
  
# 3. 정렬, 탐색 알고리즘 풀이
class ProgrammersExample3View(View):
    
    def get (self, request):
        '''
        (03) 이진탐색
        
        문제 설명
        리스트 L 과, 그 안에서 찾으려 하는 원소 x 가 인자로 주어질 때, 
        x 와 같은 값을 가지는 원소의 인덱스를 리턴하는 함수 solution() 을 완성하세요. 
        만약 리스트 L 안에 x 와 같은 값을 가지는 원소가 존재하지 않는 경우에는 -1 을 리턴합니다. 
        리스트 L 은 자연수 원소들로 이루어져 있으며, 크기 순으로 정렬되어 있다고 가정합니다. 
        또한, 동일한 원소는 두 번 이상 나타나지 않습니다.

        예를 들어,
        L = [2, 3, 5, 6, 9, 11, 15]
        x = 6
        의 인자들이 주어지면, L[3] == 6 이므로 3 을 리턴해야 합니다.

        또 다른 예로,
        L = [2, 5, 7, 9, 11]
        x = 4
        로 주어지면, 리스트 L 내에 4 의 원소가 존재하지 않으므로 -1 을 리턴해야 합니다.

        이 연습문제에서는 알고리즘의 효율성도 평가합니다. 만약 순차 (선형) 탐색 알고리즘을 구현하는 경우에는
        제한 시간 요구사항을 만족하지 못하여 효율성 테스트 케이스들을 통과하지 못할 수도 있습니다.

        '''
        L = [2, 3, 5, 6, 9, 11, 15]
        #L = [] 
        x = 15
        #x = 20
        
        def solution1(L, x):
            indx = -1 
            if len(L) == 0:
                return indx

            lower=0
            upper=len(L)-1
            tmp =[]
            
            while lower <= upper:
                middle=(lower+upper)//2
               
                if x > L[middle]:
                    lower=middle+1
                elif x < L[middle]:
                    upper=middle-1
                elif x == L[middle]:
                    indx = middle
                    return indx
                tmp = L[lower:upper+1] # 뭔가 이 과정에서 시간을 많이 잡아 먹는 다는 생각이 들었고, 최종 lower와 upper 만을 사용하여 , tmp 리스트를 구하면 될것같았다.
            
            if x not in tmp:
                return indx
                    
                #L=L[lower:upper+1] # L를 슬라이싱 해버리면, 인덱스가 0부터 시작하므로 IndexError: list index out of range가 계속 뜬다는 점 유의!!!
            return indx
        
              
        def solution2(L, x): # PASS!!!! 
            # [1] 빈 리스트가 들어올 때와 [2] 리스트에 없는 값이 들어올 때의 예외 처리에 유의 하여야겠다.
            '''
            정확성: 55.6
            효율성: 44.4
            합계: 100.0 / 100.0
            '''
            indx = -1 
            lower=0
            upper=len(L)-1
            
            if len(L) == 0:
                return indx

            while lower <= upper:
                middle=(lower+upper)//2
               
                if x > L[middle]:
                    lower=middle+1
                elif x < L[middle]:
                    upper=middle-1
                elif x == L[middle]:
                    indx = middle
                    return indx
            
            if x not in L[lower:upper+1]:
                return indx
        
        def solution3(L, x): # PASS!!!! 
            # -1의 중복을 줄어 효율성을 높여보자.
            '''
            정확성: 55.6
            효율성: 44.4
            합계: 100.0 / 100.0
            '''
            lower=0
            upper=len(L)-1

            while lower <= upper:
                middle=(lower+upper)//2
               
                if x > L[middle]:
                    lower=middle+1
                elif x < L[middle]:
                    upper=middle-1
                else:
                    return middle
            return -1
                    
        return JsonResponse({"RESULT": solution3(L,x)}, status=200)
    
class ProgrammersExample4View(View):
    
    def get (self, request):
    
        '''
        (04) 피보나치 순열
        문제 설명
        인자로 0 또는 양의 정수인 x 가 주어질 때, 
        Fibonacci 순열의 해당 값을 구하여 반환하는 함수 solution() 을 완성하세요.

        Fibonacci 순열은 아래와 같이 정의됩니다.
        F0 = 0
        F1 = 1
        Fn = Fn - 1 + Fn - 2, n >= 2

        재귀함수 작성 연습을 의도한 것이므로,
        재귀적 방법으로도 프로그래밍해 보고, 반복적 방법으로도 프로그래밍해 보시기 바랍니다.
        '''
        n=int(input("Number"))
        
        # 1) 재귀함수로 풀기
        def solution1_F(n):
            if n <=1:
                return n
            else:
                return solution1_F(n-1) + solution1_F(n-2)   
        
        def solution2_F(x):
            return n if n <=1 else solution2_F(n-1) + solution2_F(n-2) 
        
        # 2) 반복함수로 풀기 난이도 ⭐️⭐️⭐️⭐️⭐️
        def solution3_F(n):
            answer=0 # n=3
            fa = 0
            fb = 1
            # if n == 0: return 0 //  answer가 0으로 초기화 되어있으므로 안써줘도 상관없음. 
            while n>0:
                n-=1
                fa, fb = fb(1), fa+fb(0+1) # 값변경 사용
                answer = fa
            return answer       
         
        return  JsonResponse({"RESULT": solution2_F(n)}, status=200)
    
class ProgrammersExample5View(View):
    '''
    # (05) 재귀적 이진탐색

    문제 설명

    리스트 L 과, 그 안에서 찾으려 하는 원소 x 가 인자로 주어지고, 
    
    또한 탐색의 대상이 되는 리스트 내에서의 범위 인덱스가 l 부터 u 까지로 (인자로) 정해질 때, 
    
    x 와 같은 값을 가지는 원소의 인덱스를 리턴하는 함수 solution() 을 완성하세요. 
    
    만약 리스트 L 안에 x 와 같은 값을 가지는 원소가 존재하지 않는 경우에는 -1 을 리턴합니다. 
    
    리스트 L 은 자연수 원소들로 이루어져 있으며, 크기 순으로 정렬되어 있다고 가정합니다. 또한, 동일한 원소는 두 번 이상 나타나지 않습니다.

    인덱스 범위를 나타내는 l 과 u 가 인자로 주어지는 이유는, 이 함수를 재귀적인 방법으로 구현하기 위함입니다. 
    
    빈 칸에 알맞은 내용을 채워서 재귀 함수인 solution() 을 완성하세요.

    예를 들어,L = [2, 3, 5, 6, 9, 11, 15]x = 6l = 0u = 6의 인자들이 주어지면, L[3] == 6 이므로 3 을 리턴해야 합니다.

    또 다른 예로,L = [2, 5, 7, 9, 11]x = 4l = 0u = 4로 주어지면, 리스트 L 내에 4 의 원소가 존재하지 않으므로 -1 을 리턴해야 합니다.
    '''
    def get (self, request):
        '''
        정확성: 55.6
        효율성: 0.0
        합계: 55.6 / 100.0
        '''
        L = [2, 5, 7, 9, 11]
        x = 4
        l = 0
        u = 4
        def solution1(L, x, l, u):
            if "x not in L":
                return -1
            mid = (l + u) // 2
            if x == L[mid]:
                return mid
            elif x < L[mid]:
                return "solution1(L, x, l, mid-1)" 
            else:
                return "solution1(L, x, mid+1, u)"
        
        
        def solution2(L, x, l, u):
            '''
            난이도 ⭐️⭐️⭐️⭐️⭐️ 효율성 생각하기!!!
            채점 결과
            정확성: 55.6
            ⭐️ 효율성: 44.4  
            합계: 100.0 / 100.0
            '''
            if "l>u":  # ⭐️ x가 리스트 L에 없다면,  
                        #x=10 L=[11,15]일때, lower는 0, mid=0.5, upper=1로 까지 가게 되므로, u=-0.5, l=1.5가 된다. => 뒤바뀜. 
                        #x=16 L=[11,15]일때, lower는 0, mid=0.5, upper=1로 까지 가게 되므로, u=1, l=1.5가 된다. => 뒤바뀜. 
                return -1
            mid = (l + u) // 2
            if x == L[mid]:
                return mid
            elif x < L[mid]:
                return "solution2(L, x, l, mid-1)" 
            else:
                return "solution2(L, x, mid+1, u)"
        
        return  JsonResponse({"RESULT": solution2(L, x, l, u)}, status=200)

class ProgrammersExample7View(View):
    '''
    (07) 연결 리스트 순회
    문제 설명
    제 7 강에서 소개된 추상적 자료구조로 LinkedList 라는 이름의 클래스가 정의되어 있다고 가정하고, 이 리스트를 처음부터 끝까지 순회하는 메서드 traverse() 를 완성하세요.

    메서드 traverse() 는 리스트를 리턴하되, 이 리스트에는 연결 리스트의 노드들에 들어 있는 데이터 아이템들을 연결 리스트에서의 순서와 같도록 포함합니다. 예를 들어, LinkedList L 에 들어 있는 노드들이 43 -> 85 -> 62 라면, 올바른 리턴 값은 [43, 85, 62] 입니다.

    이 규칙을 적용하면, 빈 연결 리스트에 대한 순회 결과로 traverse() 메서드가 리턴해야 할 올바른 결과는 [] 입니다.

    [참고] "실행" 을 눌렀을 때 통과하는 것은 아무 의미 없습니다. 
    '''
    def get (self, request):
        class Node:
            def __init__(self, item):
                self.data = item
                self.next = None

        class LinkedList:
            def __init__(self):
                self.nodeCount = 0
                self.head = None
                self.tail = None

            def getAt(self, pos):
                if pos < 1 or pos > self.nodeCount:
                    return None
                i = 1
                curr = self.head
                while i < pos:
                    curr = curr.next
                    i += 1
                return curr

            def traverse(self):
                answer=[]
                a = self.head
                while a != None:            # 빈 리스트라면 head와 tail이 None
                    answer.append(a.data) 
                                            # 빈 리스트가 아니라면 헤더가 존재하므로 추가, 
                                            # a는 노드의 순서만 의미하므로, 노드이 데이터에 접근하려면 a.data를 해주어야함. 
                    a = a.next              # 헤드의 다음 연결 노드로 접근
                return answer

            def solution(x):
                return 0
        
        return  JsonResponse({"RESULT": []}, status=200)
 
class ProgrammersExample8View(View):
    '''
    문제 설명
    제 8 강에서 소개된 추상적 자료구조 LinkedList 클래스의 메서드로서 popAt() 메서드를 강의 내용에 소개된
    요구조건을 만족시키도록 구현하세요.

    초기 코드로 들어 있는 것은 solution() 함수를 포함하여 다른 부분은 수정하지 말고, 
    def popAt(self, pos): 의 메서드 몸체만 구현하세요.

    만약, 인자로 주어진 pos 가 올바른 범위의 값을 가지지 않는 경우에는 IndexError exception 을 발생시키도록 합니다. 
    이렇게 하기 위한 코드는 raise IndexError 입니다.
'''
    def get (self, request):
        class Node:
            
            def __init__(self, item):
                self.data = item
                self.next = None


        class LinkedList:

            def __init__(self):
                self.nodeCount = 0
                self.head = None
                self.tail = None


            def getAt(self, pos):
                if pos < 1 or pos > self.nodeCount:
                    return None

                i = 1
                curr = self.head
                while i < pos:
                    curr = curr.next
                    i += 1

                return curr


            def insertAt(self, pos, newNode):
                if pos < 1 or pos > self.nodeCount + 1:
                    return False

                if pos == 1:
                    newNode.next = self.head
                    self.head = newNode

                else:
                    if pos == self.nodeCount + 1:
                        prev = self.tail
                    else:
                        prev = self.getAt(pos - 1)
                        newNode.next = prev.next
                        prev.next = newNode

                if pos == self.nodeCount + 1:
                    self.tail = newNode

                self.nodeCount += 1
                return True

            # 1차 작성 코드
            def popAt_1(self, pos):
                #인덱스 벗어났을 때,
                if pos < 1 or pos > self.nodeCount: 
                    raise IndexError
                '''
                1) head를 없애는 경우, pos == 1
                2) tail을 없애는 경우, pos == nodeCount
                3) nodeCount ==1, pos ==1,  유일한 노드를 없애는 경우 + 2) tail을 없애는 경우, pos == nodeCount
                4) nodeCount > 1 1<post<nodeCount
                '''
                
                if pos == self.nodeCount: # tail의 노드를 없앨 경우  + 빈리스트
                    prev = self.getAt(pos-1)
                    curr = self.tail
                    self.tail = prev

                if pos == 1: # head의 노드를 없앨 경우 +  빈리스트
                    curr = self.head
                    self.head = curr.next
                else:
                    prev = self.getAt(pos-1)
                    if pos == self.nodeCount:
                        curr = self.tail
                        self.tail = prev
                    else:
                        curr = prev.next
                        prev.next = curr.next
                        
                    if self.nodeCount == 1:

                        curr = self.head

                self.nodeCount -=1

                return curr.data
            
            # 2차 작성 코드
            def popAt_2(self, pos):
                '''
                테스트 1 〉	통과 (0.05ms, 16.8MB)
                테스트 2 〉	통과 (0.06ms, 16.6MB)
                테스트 3 〉	통과 (0.04ms, 16.6MB)
                테스트 4 〉	통과 (0.08ms, 16.7MB)
                채점 결과
                정확성: 100.0
                합계: 100.0 / 100.0
                '''
                if pos < 1 or pos > self.nodeCount :
                    raise IndexError
                
                # head 제거
                if pos == 1:
                    # 유일한 원소 head + tail 제거  
                    if self.nodeCount == 1:
                        curr = self.tail
                        self.head = None
                        self.tail = None # ⭐️ tail도, head도 None
                    # 여러원소 중 head 제거  
                    else:
                        curr = self.head
                        self.head = curr.next
                        curr.next = None # ⭐️ 잘라낸 curr의 next는 끊겨있으므로 None!
                else : 
                    # tail 제거
                    if pos == self.nodeCount:
                        prev = self.getAt(pos-1)
                        self.tail = prev
                        curr = prev.next
                        prev.next = None  # ⭐️ prev가 꼬리가 되므로 prev.next는 None
                        curr.next = None 
                    # head와 tail사이의 원소 제거
                    else:
                        prev = self.getAt(pos-1)
                        curr = prev.next
                        prev.next = curr.next
                        curr.next = None
                
                self.nodeCount -= 1
                return curr.data 


            def traverse(self):
                result = []
                curr = self.head
                while curr is not None:
                    result.append(curr.data)
                    curr = curr.next
                return result

            def solution(x):
                return 0
    
        return  JsonResponse({"RESULT": []}, status=200)
    
class ProgrammersExample9View(View):
    '''
    (09) dummy head 를 가지는 연결 리스트 노드 삭제
    문제 설명
    제 9 강에서 소개된 추상적 자료구조 LinkedList 는 dummy head node 를 가지는 연결 리스트입니다.
    이 클래스의 아래와 같은 메서드들을, 강의 내용에 소개된 요구조건을 만족시키도록 구현하세요.

    popAfter()
    popAt()
    이 때, popAt() 메서드의 구현에서는 popAfter() 를 호출하여 이용하도록 합니다. 
    (그렇게 하지 않을 수도 있지만, 여기에서는 popAfter() 의 이용에 의해서 코드 구현이 보다 쉬워지는 것을 확인하기 위함입니다.)

    초기 코드로 들어 있는 것은 solution() 함수를 포함하여 다른 부분은 수정하지 말고, 
    def popAfter(self, prev): 와 def popAt(self, pos): 의 메서드 몸체만 구현하세요.

    만약, popAt() 메서드에 인자로 주어진 pos 가 올바른 범위의 값을 가지지 않는 경우에는 
    IndexError exception 을 발생시키도록 합니다. 이렇게 하기 위한 코드는 raise IndexError 입니다.
    '''
    def get (self, request):
        class Node:
            
            def __init__(self, item):
                self.data = item
                self.next = None


        class LinkedList:

            def __init__(self):
                self.nodeCount = 0         # ⭐️ nodeCount는 dumyNode를 제외함.
                self.head = Node(None) 
                self.tail = None           # ⭐️ 노드 삭제시  tail None이어야함. 
                self.head.next = self.tail # ⭐️ head와 tail의 연결관계 생성


            def traverse(self):
                result = []
                curr = self.head
                while curr.next:
                    curr = curr.next
                    result.append(curr.data)
                return result


            def getAt(self, pos):
                if pos < 0 or pos > self.nodeCount:
                    return None

                i = 0
                curr = self.head
                while i < pos:
                    curr = curr.next
                    i += 1

                return curr


            def insertAfter(self, prev, newNode):
                newNode.next = prev.next
                if prev.next is None:
                    self.tail = newNode
                prev.next = newNode
                self.nodeCount += 1
                return True


            def insertAt(self, pos, newNode):
                if pos < 1 or pos > self.nodeCount + 1:
                    return False

                if pos != 1 and pos == self.nodeCount + 1:
                    prev = self.tail
                else:
                    prev = self.getAt(pos - 1)
                return self.insertAfter(prev, newNode)

            
            '''
            테스트 1 〉	통과 (0.06ms, 16.6MB)
            테스트 2 〉	통과 (0.05ms, 16.6MB)
            테스트 3 〉	통과 (0.05ms, 16.8MB)
            테스트 4 〉	통과 (0.06ms, 16.6MB)
            테스트 5 〉	실패 (0.15ms, 16.7MB)
            '''
            # 초기 나의 풀이
            def popAfter_1(self, prev):
                # prev가 끝일때,
                if prev.next is None:
                    return None
                curr = prev.next
                # post가 1일때,
                if prev == self.head:#******
                    prev.next = curr.next
                    if curr.next is None:
                        prev.next = None
                        self.tail = prev
                elif curr.next is None: # pos가 끝일때
                    prev.next = None
                    self.tail = prev
                else:# 중간
                    prev.next = curr.next
                curr.next = None
                self.nodeCount -=1
                return curr.data


            def popAt_1(self, pos):
                if pos < 1 and pos >= self.nodeCount:
                    raise IndexError
                # pos == 1

                if pos == 1:
                    prev = self.head
            # 1<pos<nodeCount
                else:
                    prev = self.getAt(pos-1)
                return self.popAfter(prev)
            
            
            '''
            테스트 1 〉	통과 (0.05ms, 16.6MB)
            테스트 2 〉	통과 (0.07ms, 16.7MB)
            테스트 3 〉	통과 (0.05ms, 16.5MB)
            테스트 4 〉	통과 (0.07ms, 16.6MB)
            테스트 5 〉	통과 (0.05ms, 16.6MB)
            '''
            # 진화된 나의 풀이 - # ⭐️ ⭐️  dummy head 를 가지는 연결 리스트에서는 pos가 끝일 때만 유의하면됨.
            def popAfter_2(self, prev):
                # 빈 리스트 일때, count=0
                if prev.next is None:
                    return None
                curr = prev.next
                    
                if curr.next == None:    # 👈 pos가 끝자리 일때 유의
                    if self.nodeCount == 1:
                        self.tail = None
                    else:
                        self.tail = prev
                prev.next = curr.next
                curr.next = None
                self.nodeCount -=1
                return curr.data


            def popAt_2(self, pos):
                if pos < 1 or pos > self.nodeCount: # ⭐️ or 주의 하기 ,  nodeCount는 dumyNode를 제외
                    raise IndexError
                prev = self.getAt(pos-1)
                return self.popAfter_2(prev)    
            
            def solution(x):
                return 0
    
        return  JsonResponse({"RESULT": []}, status=200)
    
    
    
class ProgrammersExample10_1View(View):
    
    '''
    (10-1) 양방향 연결 리스트 역방향 순회
    문제 설명
    제 10 강에서 소개된 추상적 자료구조 DoublyLinkedList 에 대하여, 또한 강의 내용에서 언급한 reverse() 메서드를 구현하세요.

    이 reverse() 메서드는 양방향 연결 리스트를 끝에서부터 시작해서 맨 앞에 도달할 때까지 (tail 방향에서 head 방향으로) 순회하면서, 
    방문하게 되는 node 에 들어 있는 data item 을 순회 순서에 따라 리스트에 담아 리턴합니다.

    예를 들어, DoublyLinkedList L 에 들어 있는 노드들이 43 -> 85 -> 62 라면, 올바른 리턴 값은 [62, 85, 43] 입니다.

    이 규칙을 적용하면, 빈 연결 리스트에 대한 역방향 순회 결과로 reverse() 메서드라 리턴해야 할 올바른 결과는 [] 입니다.

    '''    
    def get(self,request):
        
        '''
        테스트 1 〉	통과 (0.04ms, 16.6MB)
        테스트 2 〉	통과 (0.04ms, 16.6MB)
        '''
        
        class Node:
            
            def __init__(self, item):
                self.data = item
                self.prev = None
                self.next = None


        class DoublyLinkedList:

            def __init__(self):
                self.nodeCount = 0
                self.head = Node(None)
                self.tail = Node(None)
                self.head.prev = None
                self.head.next = self.tail
                self.tail.prev = self.head
                self.tail.next = None

            # 나의 풀이
            def reverse(self):
                result = []
                
                curr = self.tail
                while curr.prev.prev !=None:            
                    curr = curr.prev
                    result.append(curr.data)
                    
                return result


            def getAt(self, pos):
                if pos < 0 or pos > self.nodeCount:
                    return None

                if pos > self.nodeCount // 2:
                    i = 0
                    curr = self.tail
                    while i < self.nodeCount - pos + 1:
                        curr = curr.prev
                        i += 1
                else:
                    i = 0
                    curr = self.head
                    while i < pos:
                        curr = curr.next
                        i += 1

                return curr


            def insertAfter(self, prev, newNode):
                next = prev.next
                newNode.prev = prev
                newNode.next = next
                prev.next = newNode
                next.prev = newNode
                self.nodeCount += 1
                return True


            def insertAt(self, pos, newNode):
                if pos < 1 or pos > self.nodeCount + 1:
                    return False

                prev = self.getAt(pos - 1)
                return self.insertAfter(prev, newNode)


        def solution(x):
            return 0
        
        return  JsonResponse({"RESULT": self.reverse(self)}, status=200)
    
class ProgrammersExample10_2View(View):
    
    '''
    (10-2) 양방향 연결 리스트 노드 삽입
    문제 설명
    제 10 강에서 소개된 추상적 자료구조 DoublyLinkedList 의 메서드로 insertBefore() 를 구현하세요.

    이 insertBefore() 메서드에는 두 개의 인자가 주어지는데, next 는 어느 node 의 앞에 새로운 node 를 삽입할지를 지정하고, 
    newNode 는 삽입할 새로운 node 입니다.

    강의 내용에서 소개된 insertAfter() 메서드의 구현과 매우 유사하게 할 수 있습니다.
    '''    
    def get(self,request):
        '''
        테스트 1 〉	통과 (0.06ms, 16.8MB)

        '''
        
        class Node:
        
            def __init__(self, item):
                self.data = item
                self.prev = None
                self.next = None

        class DoublyLinkedList:

            def __init__(self):
                self.nodeCount = 0
                self.head = Node(None)
                self.tail = Node(None)
                self.head.prev = None
                self.head.next = self.tail
                self.tail.prev = self.head
                self.tail.next = None

            def traverse(self):
                result = []
                curr = self.head
                while curr.next.next:
                    curr = curr.next
                    result.append(curr.data)
                return result

            #나의 풀이
            def insertBefore(self, next, newNode):
                # if next == self.head:
                #     return False
                prevNode = next.prev
                nextNode = next
                nextNode.prev  = newNode
                prevNode.next = newNode   
                newNode.next  = nextNode
                newNode.prev  = prevNode 
                self.nodeCount +=1
                return True

            def solution(x):
                return 0
        
        return JsonResponse({"RESULT": self.insertBefore(self,1)}, status=200)
        
class ProgrammersExample10_3View(View):
    
    '''
    (10-3) 양방향 연결 리스트 노드 삭제
    문제 설명
    제 10 강에서 소개된 추상적 자료구조 DoublyLinkedList 에 대하여 node 의 삭제 연산에 관련한 아래와 같은 메서드들을 구현하세요.

    popAfter()
    popBefore()
    popAt()
    popAfter(prev) 는 인자 prev 에 의하여 주어진 node 의 다음에 있던 node 를 삭제하고, popBefore(next) 는 인자 next 에 의하여
    주어진 node 의 이전에 있던 node 를 삭제합니다. 그리고 삭제되는 node 에 담겨 있던 data item 을 리턴합니다.

    popAt(pos) 는 인자 pos 에 의하여 지정되는 node 를 삭제하고 그 node 에 담겨 있던 data item 을 리턴하는데,
    위 popAfter() 또는 popBefore() 를 호출하여 이용하는 방식으로 구현하세요. 또한, 만약 인자 pos 가 올바른 범위 내에 있지 않은 경우에는
    raise IndexError 를 이용하여 IndexError exception 을 일으키도록 구현하세요.

    테스트 케이스 1-3 은 각각 (1) popAfter(), (2) popBefore(), (3) popAt() 메서드의 올바른 동작을 검증하는 케이스입니다.

    '''    
    def get(self,request):
        
        '''
        테스트 1 〉	통과 (0.07ms, 16.7MB)
        테스트 2 〉	통과 (0.06ms, 16.6MB)
        테스트 3 〉	통과 (0.07ms, 16.7MB)

        '''
        
        class Node:
    
            def __init__(self, item):
                self.data = item
                self.prev = None
                self.next = None


        class DoublyLinkedList:

            def __init__(self):
                self.nodeCount = 0
                self.head = Node(None)
                self.tail = Node(None)
                self.head.prev = None
                self.head.next = self.tail
                self.tail.prev = self.head
                self.tail.next = None


            def traverse(self):
                result = []
                curr = self.head
                while curr.next.next:
                    curr = curr.next
                    result.append(curr.data)
                return result


            def getAt(self, pos):
                if pos < 0 or pos > self.nodeCount:
                    return None

                if pos > self.nodeCount // 2:
                    i = 0
                    curr = self.tail
                    while i < self.nodeCount - pos + 1:
                        curr = curr.prev
                        i += 1
                else:
                    i = 0
                    curr = self.head
                    while i < pos:
                        curr = curr.next
                        i += 1

                return curr


            def insertAfter(self, prev, newNode):
                next = prev.next
                newNode.prev = prev
                newNode.next = next
                prev.next = newNode
                next.prev = newNode
                self.nodeCount += 1
                return True


            def insertAt(self, pos, newNode):
                if pos < 1 or pos > self.nodeCount + 1:
                    return False

                prev = self.getAt(pos - 1)
                return self.insertAfter(prev, newNode)

            # 나의 풀이
            def popAfter(self, prev):       
                curr = prev.next
                nextN = curr.next
                nextN.prev = prev
                prev.next = nextN
                self.nodeCount -=1        
                return curr.data  

            # 나의 풀이
            def popBefore(self, nextN):      
                curr = nextN.prev
                prev = curr.prev
                prev.next = nextN
                nextN.prev = prev
                self.nodeCount -=1
                return curr.data

            # 나의 풀이
            def popAt(self, pos):
                if pos <1 or pos>self.nodeCount:
                    raise IndexError
                prev = self.getAt(pos-1)
                return self.popAfter(prev)
        
        return  JsonResponse({"RESULT": self.popAt(self,1)}, status=200)
    
    
        
class ProgrammersExample10_4View(View):    
    '''
   (10-4) 양방향 연결 리스트의 병합
    문제 설명
    제 10 강에서 소개된 추상적 자료구조 DoublyLinkedList 에 대하여 두 개의 양방향 연결 리스트를 앞뒤로 이어 붙이는 메서드 concat() 을 구현하세요.

    예를 들어, 양방향 연결 리스트 L1 에는 1 -> 2 -> 3 의 원소가 순서대로 들어 있고, 또다른 양방향 연결 리스트 L2 에는 4 -> 5 의 순서로 원소가 들어 있을 때,
    메서드 호출 L1.concat(L2) 의 결과로 L1 은 1 -> 2 -> 3 -> 4 -> 5 의 양방향 연결 리스트가 됩니다. 물
    론, L1 또는 L2 또는 둘 다가 비어 있는 양방향 연결 리스트인 경우도 고려되도록 코드를 작성해야 합니다.
    '''
    def get(self,request):
        '''
        테스트 1 〉	통과 (0.05ms, 16.7MB)
        테스트 2 〉	통과 (0.07ms, 16.6MB)
        테스트 3 〉	통과 (0.05ms, 16.6MB)
        '''

        class Node:
            
            def __init__(self, item):
                self.data = item
                self.prev = None
                self.next = None


        class DoublyLinkedList:

            def __init__(self):
                self.nodeCount = 0
                self.head = Node(None)
                self.tail = Node(None)
                self.head.prev = None
                self.head.next = self.tail
                self.tail.prev = self.head
                self.tail.next = None

            # 나의 풀이 - 양방향 연결리스트에서는 각각의 리스트가 빈리스트일때를 고려하지 않아도 해결된다.  
            def concat(self, L):
                L1Last = self.tail.prev
                L2First = L.head.next
                L1Last.next = L2First
                L2First.prev = L1Last
                self.tail = L.tail
                L.head = self.head
                self.nodeCount +=L.nodeCount
                return self


            def traverse(self):
                result = []
                curr = self.head
                while curr.next.next:
                    curr = curr.next
                    result.append(curr.data)
                return result

            
            def getAt(self, pos):
                if pos < 0 or pos > self.nodeCount:
                    return None

                if pos > self.nodeCount // 2:
                    i = 0
                    curr = self.tail
                    while i < self.nodeCount - pos + 1:
                        curr = curr.prev
                        i += 1
                else:
                    i = 0
                    curr = self.head
                    while i < pos:
                        curr = curr.next
                        i += 1

                return curr

            def insertAfter(self, prev, newNode):
                next = prev.next
                newNode.prev = prev
                newNode.next = next
                prev.next = newNode
                next.prev = newNode
                self.nodeCount += 1
                return True


            def insertAt(self, pos, newNode):
                if pos < 1 or pos > self.nodeCount + 1:
                    return False

                prev = self.getAt(pos - 1)
                return self.insertAfter(prev, newNode)


        def solution(x):
            return 0
        
        return JsonResponse({"RESULT": self.concat(self,1)}, status=200)
        
        
class ProgrammersExample11View(View):    
    '''
    (11) 수식의 괄호 검사 (스택)
    문제 설명
    소괄호: ( )
    중괄호: /{ /}
    대괄호: [ ]
    를 포함할 수 있는 수식을 표현한 문자열 expr 이 인자로 주어질 때, 이 수식의 괄호가 올바르게 여닫혀 있는지를 판단하는 함수 solution() 을 완성하세요. 이 함수는 수식의 괄호가 유효하면 True 를, 그렇지 않으면 False 를 리턴합니다.

    스택을 활용하여 수식 내의 괄호 여닫음의 유효성을 검사하는 알고리즘에 대해서는 동영상 강의 내용을 참고하세요.
        '''
    def get(self,request):
        '''
        테스트 1 〉	통과 (0.01ms, 10.2MB)
        테스트 2 〉	통과 (0.01ms, 10.2MB)
        테스트 3 〉	통과 (0.01ms, 10.3MB)
        테스트 4 〉	통과 (0.01ms, 10.4MB)
        테스트 5 〉	통과 (0.01ms, 10.2MB)
        테스트 6 〉	통과 (0.01ms, 10.2MB)
        '''
        class ArrayStack:

            def __init__(self):
                self.data = []

            def size(self):
                return len(self.data)

            def isEmpty(self):
                return self.size() == 0

            def push(self, item):
                self.data.append(item)

            def pop(self):
                return self.data.pop()

            def peek(self):
                return self.data[-1]


        def solution(expr):
            match = {
                ')': '(',
                '}': '{',
                ']': '['
            }
            S = ArrayStack()
            for c in expr:
                if c in '({[':
                    S.push(c)

                elif c in match:
                    if S.isEmpty():
                        return False
                    else:
                        t = match[c]

                        if t != S.pop():
                            return False
            return S.isEmpty()
        
        return JsonResponse({"RESULT": solution(self.expr)}, status=200)
    
class ProgrammersExample12View(View):    
    
    '''
        (12) 중위표현 수식 --> 후위표현 수식
    문제 설명
    중위 표기법을 따르는 수식 S 가 인자로 주어질 때, 이 수식을 후위 표기법을 따르는 수식으로 변환하여 반환하는 함수 solution() 을 완성하세요.

    인자로 주어지는 수식 문자열 S 는 영문 대문자 알파벳 한 글자로 이루어지는 변수 A - Z 까지와 4칙연산을 나타내는 연산자 기호 +, -, *, /, 그리고 여는 괄호와 닫는 괄호 (, ) 로 이루어져 있으며 공백 문자는 포함하지 않는 것으로 가정합니다. 또한, 올바르게 구성되지 않은 수식은 인자로 주어지지 않는다고 가정합니다. (수식의 유효성은 검증할 필요가 없습니다.)

    문제에서 미리 주어진, 연산자의 우선순위를 표현한 python dict 인 prec 을 활용할 수 있습니다.

    또한, 스택의 기초 강의에서 이미 구현한, 배열을 이용한 스택의 추상적 자료 구조 코드가 이미 포함되어 있으므로 그대로 이용할 수 있습니다.

    (참고) 테스트 케이스를 보완하여 문제가 2019년 9월 24일에 수정되었습니다.
    (추가 참고) 테스트 케이스를 또 보완하여 문제가 2021년 7월 21일에 수정되었습니다. 추가된 테스트 케이스들은 9번부터 12번까지입니다. 관련하여 질문과 답변 (https://programmers.co.kr/questions/19360) 을 참고할 수 있습니다.
    '''
    def get(self,request):
        class ArrayStack:
    
            def __init__(self):
                self.data = []

            def size(self):
                return len(self.data)

            def isEmpty(self):
                return self.size() == 0

            def push(self, item):
                self.data.append(item)

            def pop(self):
                return self.data.pop()

            def peek(self):
                return self.data[-1]

        prec = {
            '*': 3, '/': 3,
            '+': 2, '-': 2,
            '(': 1
        }

        ## 처음 접근 방식(오답)
        def solution(S):
            opStack = ArrayStack()
            answer = ''
            
            for a in S:
                if a in prec:# 딕셔너리에 있을 때
                    opStack.push(a)
                    opStack.peek()
                elif a == ')': # 닫기 괄호를 만났을 때,
                    while not opStack.isEmpty:
                        b = opStack.pop()
                        if prec[b] > 1:
                            answer+=b
                else:# 피연산자일때
                    answer+=a
            return answer
        
        
        '''
        테스트 1
        입력값 〉	"(A+B)*(C+D)"
        기댓값 〉	"AB+CD+*"
        실행 결과 〉	테스트를 통과하였습니다.
        테스트 2
        입력값 〉	"A*B+C"
        기댓값 〉	"AB*C+"
        실행 결과 〉	테스트를 통과하였습니다.
        테스트 3
        입력값 〉	"A+B*C"
        기댓값 〉	"ABC*+"
        실행 결과 〉	테스트를 통과하였습니다.
        테스트 4
        입력값 〉	"A+B+C"
        기댓값 〉	"AB+C+"
        실행 결과 〉	테스트를 통과하였습니다.
        테스트 5
        입력값 〉	"(A+B)*C"
        기댓값 〉	"AB+C*"
        실행 결과 〉	테스트를 통과하였습니다.
        테스트 6
        입력값 〉	"A*(B+C)"
        기댓값 〉	"ABC+*"
        실행 결과 〉	테스트를 통과하였습니다.
        '''
        ## 나의 풀이
        def solution(S):
            opStack = ArrayStack()
            answer = ''
            
            for a in S:
                if a in prec:# 딕셔너리에 있을 때
                    if opStack.isEmpty():
                        opStack.push(a)
                    elif a == '(':
                        opStack.push(a)
                    elif prec[opStack.peek()] < prec[a]:
                        opStack.push(a)
                    else:
                        while not opStack.isEmpty() and prec[opStack.peek()]>=prec[a]:
                            answer += opStack.pop()
                        opStack.push(a) # 우선순위가 peek보다 낮을 때, stack의 데이터 꺼내고 새로 담아주기
                            
                elif a == ')': # 닫기 괄호를 만났을 때,
                    while not opStack.isEmpty():
                        top = opStack.peek()
                        opStack.pop()
                        if top != '(': 
                            answer+=top
                            
                else:# 피연산자일때
                    answer+=a
                    
            while not opStack.isEmpty():
                answer += opStack.pop()
                
            return answer
        
        # 다른 풀이1
        def solution(S):
            opStack = ArrayStack()
            answer = ''
            #tmp=[]

            for var in S:
                # <prec>에 있을때
                if var in prec:
                    # 비어있을때
                    if opStack.isEmpty():
                        opStack.push(var)
                    # 스택에서 이보다 높거나 같은 우선순위는 pop
                    elif var == '(':
                        opStack.push(var)
                    # 스택에서 이보다 작은 priority를 갖는다면 push
                    elif prec[opStack.peek()] < prec[var]:
                        opStack.push(var)
                    # 스택에서 이보다 큰 priority를 갖는다면 pop
                    else:
                        while not opStack.isEmpty() and prec[opStack.peek()]>=prec[var]:
                            answer += opStack.pop()
                        opStack.push(var)
                # <괄호닫기>일때
                # elif var == ')':
                #     while opStack.peek() != '(':
                #         answer += opStack.pop()
                #     opStack.pop()
                    
                elif var == ')':
                    topToken = opStack.pop()
                    while topToken != '(':
                        answer += topToken
                        topToken = opStack.pop()
                
                # <인수>일때
                else:
                    answer += var
            # 남은 인자 출력        
            while not opStack.isEmpty():
                answer += opStack.pop()
                
                
        # 다른 풀이2
        def solution(S):
            opStack = ArrayStack()
            answer = ''
            for c in S:
                if c not in "*+-/()":
                    answer += c
                if c == "(":
                    opStack.push(c)
                if c == ")":
                    while opStack.peek() != "(":
                        answer += opStack.pop()
                    opStack.pop()
                if c in "*+/-":
                    if opStack.isEmpty():
                        opStack.push(c)
                    else:
                        while prec[opStack.peek()] >= prec[c]:
                            answer += opStack.pop()
                            if opStack.isEmpty():
                                break
                        opStack.push(c)
            while not opStack.isEmpty():
                answer += opStack.pop()
            return answer
        
        return JsonResponse({"RESULT": solution("(A+B)*(C+D)")}, status=200)
    
    
class ArrayStack:
        
        def __init__(self):
            self.data = []

        def size(self):
            return len(self.data)

        def isEmpty(self):
            return self.size() == 0

        def push(self, item):
            self.data.append(item)

        def pop(self):
            return self.data.pop()

        def peek(self):
            return self.data[-1]

class ProgrammersExample13View(View):  
    '''
    # (13) 후위표현 수식 계산

    ### **문제 설명**

    인자로 주어진 문자열 expr 은 소괄호와 사칙연산 기호, 그리고 정수들로만 이루어진 중위 표현 수식입니다. 함수 `solution()` 은 
    이 수식의 값을 계산하여 그 결과를 리턴하도록 작성되어 있습니다. 이 함수는 차례로 `splitTokens()`, `infixToPostfix()`, 
    그리고 `postfixEval()` 함수를 호출하여 이 수식의 값을 계산하는데,

    - `splitTokens()` - 강의 내용에서와 같은 코드로 이미 구현되어 있습니다.
    - `infixToPostfix()` - 지난 강의의 연습문제에서 작성했던 코드를 수정하여, 문자열이 아닌 리스트를 리턴하도록 작성합니다.
    - `postfixEval()` - 이번 강의의 연습문제입니다. 함수의 내용을 완성하세요.

    즉, 두 개의 함수 `infixToPostfix()` 와 `postfixEval()` 을 구현하는 연습입니다. 스택을 이용하기 위하여 `class ArrayStack` 이 정의되어 있으므로 그것을 활용하세요.

    [참고] Python 에는 `eval()` 이라는 built-in 함수가 있어서, 이 함수에 문자열을 인자로 전달하면, 
    그 문자열을 그대로 Python 표현식으로 간주하고 계산한 결과를 리턴하도록 되어 있습니다. 이 built-in 함수 `eval()` 을 이용하면 
    이 연습문제는 전혀 직접 코드를 작성하지 않고도 정답을 낼 수 있을 것이지만, 스택을 이용하여 중위표현식을 계산하는 프로그래밍 연습을 위한 것이니, 
    강의 내용에서 설명한 절차를 수행하도록 코드를 작성해 보세요.
   
    '''
      
    def get(self,request):

        def splitTokens(exprStr):
            tokens = []
            val = 0
            valProcessing = False
            
            # (5+3)*(5-4)
            # ['(', 5, '+', 3, ')' ,*, '(', 5, '-', 4, ')']
            for c in exprStr:
                if c == ' ':
                    continue
                if c in '0123456789':
                    val = val * 10 + int(c)
                    valProcessing = True
                else:
                    if valProcessing:
                        tokens.append(val)
                        val = 0
                    valProcessing = False
                    tokens.append(c) 
            if valProcessing:
                tokens.append(val)

            return tokens


        def infixToPostfix(tokenList):
            prec = {
                '*': 3,
                '/': 3,
                '+': 2,
                '-': 2,
                '(': 1,
            }

            opStack = ArrayStack()
            postfixList = []
            
            for token in tokenList:
                if type(token) is int:# 피연산자가 올 때, 
                    postfixList.append(token)
                elif token == '(': # 여는 괄호가 올때, 
                    opStack.push(token)
                    
                elif token == ')':# 닫는 괄호가 올때, 
                    while not opStack.peek() == '(':
                        postfixList.append(opStack.pop())
                    opStack.pop()
                    
                else:# 연산자가 올 때, 
                    while not opStack.isEmpty():
                        if prec[opStack.peek()] >= prec[token]:
                            postfixList.append(opStack.pop())
                        else : break #*** 반복문 끊어주기
                    opStack.push(token)
                
            while not opStack.isEmpty():
                postfixList.append(opStack.pop())

            return postfixList


        def postfixEval(tokenList):
            valStack = ArrayStack()
            
            for token in tokenList:
                if type(token) is int:
                    valStack.push(token)
                elif token == '*':
                    val1 =valStack.pop()
                    val2 =valStack.pop()
                    valStack.push(val2*val1)
                elif token == '/':
                    val1 =valStack.pop()
                    val2 =valStack.pop()
                    valStack.push(val2/val1)
                elif token == '+':
                    val1 =valStack.pop()
                    val2 =valStack.pop()
                    valStack.push(val2+val1)
                elif token == '-':
                    val1 =valStack.pop()
                    val2 =valStack.pop()
                    valStack.push(val2-val1)
                    
            return valStack.pop()

        def solution(expr):
            tokens = ProgrammersExample13View.splitTokens(expr)
            postfix = ProgrammersExample13View.infixToPostfix(tokens)
            val = ProgrammersExample13View.postfixEval(postfix)
            return val
        
        '''
         테스트 1
        입력값 〉	"5 + 3"
        기댓값 〉	8
        실행 결과 〉	테스트를 통과하였습니다.
        출력 〉	[5, '+', 3]
        테스트 2
        입력값 〉	"(1 + 2) * (3 + 4)"
        기댓값 〉	21
        실행 결과 〉	테스트를 통과하였습니다.
        출력 〉	['(', 1, '+', 2, ')', '*', '(', 3, '+', 4, ')']
        테스트 3
        입력값 〉	"7 * (9 - (3+2))"
        기댓값 〉	28
        실행 결과 〉	테스트를 통과하였습니다.
        출력 〉	[7, '*', '(', 9, '-', '(', 3, '+', 2, ')', ')']
        '''
        return JsonResponse({"RESULT": solution("(5+4)*(6-7)")}, status=200)
    
class ProgrammersExample14View(View):  
        '''
        (14) 양방향 연결 리스트로 구현하는 큐
        문제 설명
        양방향 연결 리스트를 활용하여 큐 (queue) 의 추상적 자료구조 (abstract data structure) 구현을 완성하세요.

        정의하고자 하는 큐의 추상적 자료구조는 class LinkedListQueue 로 구현됩니다. 
        이 문제는 해당 클래스의 메서드들의 구현을 빈칸 채우기 형태로 완성하는 것으로 되어 있으며, 이 클래스의 구현은 L120 부터 시작합니다.

        그 위에는 (LL1-117) 이 추상적 자료구조를 구현하기 위해서 이용할 class DoublyLinkedList 와, 
        또한 여기서 이용하는 class Node 의 구현이 정의되어 있습니다. 이 코드는 이전의 "양방향 연결 리스트" 강의에서 다루어진 것과 완전히 동일합니다.

        정확성 테스트는 class LinkedListQueue 의 각 메서드가 올바르게 구현되어 있는지를 검사합니다. 
        "코드 실행" 을 눌렀을 때 예시 테스트 케이스를 통과하는 것은 아무런 의미가 없습니다.

        '''
        
def get(self,request):
        class Node:

            def __init__(self, item):
                self.data = item
                self.prev = None
                self.next = None


        class DoublyLinkedList:

            def __init__(self):
                self.nodeCount = 0
                self.head = Node(None)
                self.tail = Node(None)
                self.head.prev = None
                self.head.next = self.tail
                self.tail.prev = self.head
                self.tail.next = None


            def __repr__(self):
                if self.nodeCount == 0:
                    return 'LinkedList: empty'

                s = ''
                curr = self.head
                while curr.next.next:
                    curr = curr.next
                    s += repr(curr.data)
                    if curr.next.next is not None:
                        s += ' -> '
                return s


            def getLength(self):
                return self.nodeCount


            def traverse(self):
                result = []
                curr = self.head
                while curr.next.next:
                    curr = curr.next
                    result.append(curr.data)
                return result


            def reverse(self):
                result = []
                curr = self.tail
                while curr.prev.prev:
                    curr = curr.prev
                    result.append(curr.data)
                return result


            def getAt(self, pos):
                if pos < 0 or pos > self.nodeCount:
                    return None

                if pos > self.nodeCount // 2:
                    i = 0
                    curr = self.tail
                    while i < self.nodeCount - pos + 1:
                        curr = curr.prev
                        i += 1
                else:
                    i = 0
                    curr = self.head
                    while i < pos:
                        curr = curr.next
                        i += 1

                return curr


            def insertAfter(self, prev, newNode):
                next = prev.next
                newNode.prev = prev
                newNode.next = next
                prev.next = newNode
                next.prev = newNode
                self.nodeCount += 1
                return True


            def insertAt(self, pos, newNode):
                if pos < 1 or pos > self.nodeCount + 1:
                    return False

                prev = self.getAt(pos - 1)
                return self.insertAfter(prev, newNode)


            def popAfter(self, prev):
                curr = prev.next
                next = curr.next
                prev.next = next
                next.prev = prev
                self.nodeCount -= 1
                return curr.data


            def popAt(self, pos):
                if pos < 1 or pos > self.nodeCount:
                    raise IndexError('Index out of range')

                prev = self.getAt(pos - 1)
                return self.popAfter(prev)


            def concat(self, L):
                self.tail.prev.next = L.head.next
                L.head.next.prev = self.tail.prev
                self.tail = L.tail

                self.nodeCount += L.nodeCount

        # 나의 풀이
        class LinkedListQueue:

            def __init__(self):
                self.data = DoublyLinkedList()

            def size(self):
                return self.data.getLength()

            def isEmpty(self):
                return self.size()==0

            def enqueue(self, item):
                node = Node(item)
                self.data.insertAt(self.size()+1, node)

            def dequeue(self):
                return self.data.popAt(1)

            def peek(self):
                return self.data.getAt(1).data

        def solution(x):
            return 0
        
        '''
        정확성  테스트
        테스트 1 〉	통과 (0.06ms, 16.7MB)
        테스트 2 〉	통과 (0.04ms, 16.7MB)
        테스트 3 〉	통과 (0.06ms, 16.8MB)
        테스트 4 〉	통과 (0.06ms, 16.8MB)
        '''

        return JsonResponse({"RESULT": "Sucess"}, status=200)
    
    
class ProgrammersExample15View(View):  
    def get(self,request):
        '''
        # (15) 환형 큐 구현

        ### **문제 설명**

        Python 의 내장 데이터형인 리스트 (list) 를 이용하여 환형 큐의 추상적 자료 구조를 구현한 클래스 `CircularQueue` 를 완성하세요.

        [참고] 함수 `solution()` 은 이 클래스의 구현과는 관계 없는 것이지만, 문제가 올바르게 동작하는 데 필요해서 넣어 둔 것이니 무시해도 좋습니다. 
        또한, "실행" 을 눌렀을 때 예시 테스트 케이스를 통과한다고 출력되는 것은 아무런 의미가 없습니다.
        '''
        class CircularQueue:
            
            def __init__(self, n):
                self.maxCount = n
                self.data = [None] * n
                self.count = 0
                self.front = -1
                self.rear = -1


            def size(self):
                return self.count

            def isEmpty(self):
                return self.count == 0

            def isFull(self):
                return self.count == self.maxCount
            # 나의 풀이
            def enqueue(self, x):
                if self.isFull():
                    raise IndexError('Queue full')
                self.rear = (self.rear+1)%self.maxCount

                self.data[self.rear] = x
                self.count += 1

            # 나의 풀이
            def dequeue(self):
                if self.size()==0:
                    raise IndexError('Queue empty')
                self.front = (self.front+1)%self.maxCount
                # front는 첫 원소의 바로 앞을 지칭하기 때문에 먼저 자릿수를 한자리 위로 옮긴 다음 x를 출력해낸다.
                x = self.data[self.front]

                self.count -= 1
                return x

            # 나의 풀이
            def peek(self):
                if self.isEmpty():
                    raise IndexError('Queue empty')
                return self.data[(self.front+1)%self.maxCount]
                # front는 첫 원소의 바로 앞을 지칭함.

        CQ = CircularQueue(5)
        
        return JsonResponse({"RESULT": CQ.peek()}, status=200)
    
class ProgrammersExample16View(View):  
    def get(self,request):
        '''
        # (16) 우선순위 큐의 enqueue 연산 구현

        ### **문제 설명**

        앞선 강의에서 소개된 양방향 연결 리스트의 추상적 자료구조 구현인 클래스 `DoublyLinkedList` 를 이용하여 우
        선순위 큐의 추상적 자료구조인 클래스 `PriorityQueue` 의 구현을 완성하세요.

        코드의 윗부분은 양방향 연결 리스트를 이용하기 위한 클래스 `Node` 와 `DoublyLinikedList` 의 구현입니다. 
        그대로 둔 채, 아래에 있는 `class PriorityQueue` 의 메서드들 중 `enqueue()` 메서드의 구현을 위한 
        빈 칸 채우기만 완성하면 됩니다.

        [참고] 함수 `solution()` 은 이 클래스의 구현과는 관계 없는 것이지만, 문제가 올바르게 동작하는 데 필요해서 
        넣어 둔 것이니 무시해도 좋습니다. 또한, 실행 을 눌렀을 때 예시 테스트 케이스를 통과한다고 출력되는 것은 아무런 
        의미가 없습니다.

        '''
        class Node:
    
            def __init__(self, item):
                self.data = item
                self.prev = None
                self.next = None

        class DoublyLinkedList:

            def __init__(self):
                self.nodeCount = 0
                self.head = Node(None)
                self.tail = Node(None)
                self.head.prev = None
                self.head.next = self.tail
                self.tail.prev = self.head
                self.tail.next = None


            def __repr__(self):
                if self.nodeCount == 0:
                    return 'LinkedList: empty'

                s = ''
                curr = self.head
                while curr.next.next:
                    curr = curr.next
                    s += repr(curr.data)
                    if curr.next.next is not None:
                        s += ' -> '
                return s


            def getLength(self):
                return self.nodeCount


            def traverse(self):
                result = []
                curr = self.head
                while curr.next.next:
                    curr = curr.next
                    result.append(curr.data)
                return result


            def reverse(self):
                result = []
                curr = self.tail
                while curr.prev.prev:
                    curr = curr.prev
                    result.append(curr.data)
                return result


            def getAt(self, pos):
                if pos < 0 or pos > self.nodeCount:
                    return None

                if pos > self.nodeCount // 2:
                    i = 0
                    curr = self.tail
                    while i < self.nodeCount - pos + 1:
                        curr = curr.prev
                        i += 1
                else:
                    i = 0
                    curr = self.head
                    while i < pos:
                        curr = curr.next
                        i += 1

                return curr


            def insertAfter(self, prev, newNode):
                next = prev.next
                newNode.prev = prev
                newNode.next = next
                prev.next = newNode
                next.prev = newNode
                self.nodeCount += 1
                return True


            def insertAt(self, pos, newNode):
                if pos < 1 or pos > self.nodeCount + 1:
                    return False

                prev = self.getAt(pos - 1)
                return self.insertAfter(prev, newNode)


            def popAfter(self, prev):
                curr = prev.next
                next = curr.next
                prev.next = next
                next.prev = prev
                self.nodeCount -= 1
                return curr.data


            def popAt(self, pos):
                if pos < 1 or pos > self.nodeCount:
                    return None

                prev = self.getAt(pos - 1)
                return self.popAfter(prev)


            def concat(self, L):
                self.tail.prev.next = L.head.next
                L.head.next.prev = self.tail.prev
                self.tail = L.tail

                self.nodeCount += L.nodeCount


        class PriorityQueue:

            def __init__(self):
                self.queue = DoublyLinkedList()


            def size(self):
                return self.queue.getLength()

            def isEmpty(self):
                return self.size() == 0
            
            # 나의 풀이(빈칸채우기)
            # 주의 할 것, enqueue시 숫자가 낮은 것이 우선이 되도록!!
            def enqueue(self, x):
                newNode = Node(x)
                curr = self.queue.head
                while curr.next.data != None and x < curr.next.data:
                    curr = curr.next
                self.queue.insertAfter(curr, newNode)

            # 주의 할 것, dequeue시 숫자가 낮은 것이 먼저 나오며, 앞이 아니라 뒤에서 나온다!!!!!
            def dequeue(self):
                return self.queue.popAt(self.queue.getLength())

            def peek(self):
                return self.queue.getAt(self.queue.getLength()).data


        def solution(x):
            return 0
        
        PQ = PriorityQueue()
        
        return JsonResponse({"RESULT": PQ.enqueue(2)}, status=200)
    
    
    
    '''
    (18-01) 이진트리의 depth() 연산 구현
    문제 설명
    이미 주어진 코드 (class Node 와 class BinaryTree 에 의하여) 의 구조를 따르는 이진 트리 (binary tree) 에 대하여, 트리의 깊이 (depth) 를 구하는 연산의 구현을 완성하세요.

    초기 코드에 pass 로만 되어 있는 class Node 의 depth() 메서드와 class BinaryTree 의 depth() 메서드를 구현합니다. 코드의 다른 부분은 수정할 필요가 없습니다.

    참고로 할 수 있도록, 강의에서 소개한 size() 메서드들 (class Node 와 class BinaryTree 에 대해서) 을 그대로 두었습니다. 문제로 주어진 depth() 연산도 매우 비슷한 식으로 구현할 수 있으니 참고로 삼으세요.

    [참고] 실행 을 눌렀을 때 통과하는 것은 아무 의미 없습니다.
    또한, solution() 함수는 테스트에 영향을 미치므로 수정하지 말고 그대로 두세요.
    '''
    class Node:
    
        def __init__(self, item):
            self.data = item
            self.left = None
            self.right = None


        def size(self):
            l = self.left.size() if self.left else 0
            r = self.right.size() if self.right else 0
            return l + r + 1


        # 나의 풀이
        def depth(self):
            l = self.left.depth() if self.left else 0
            r = self.right.depth() if self.right else 0
            return (l if l >= r else r) + 1
            


    class BinaryTree:
    
        def __init__(self, r):
            self.root = r

        def size(self):
            if self.root:
                return self.root.size()
            else:
                return 0
        # 나의 풀이
        def depth(self):
            if self.root:
                return self.root.depth()
            else:
                return 0
            
        '''
        테스트 1 〉	통과 (0.05ms, 16.5MB)
        테스트 2 〉	통과 (0.04ms, 16.4MB)
        테스트 3 〉	통과 (0.05ms, 16.6MB)
        테스트 4 〉	통과 (0.04ms, 16.3MB)
        테스트 5 〉	통과 (0.05ms, 16.3MB)    
        '''        
def solution(x):
    return 0


'''
(18-02) 이진트리의 전위순회 연산 구현
문제 설명
이미 주어진 코드 (class Node 와 class BinaryTree 에 의하여) 의 구조를 따르는 이진 트리 (binary tree) 에 대하여, 트리를 전위 순회 (preorder traversal) 하는 연산의 구현을 완성하세요.

초기 코드에 pass 로만 되어 있는 class Node 의 preorder() 메서드와 class BinaryTree 의 preorder() 메서드를 구현합니다. 코드의 다른 부분은 수정할 필요가 없습니다.

참고로 할 수 있도록, 강의에서 소개한 inorder() 메서드들 (class Node 와 class BinaryTree 에 대해서) 을 그대로 두었습니다. 문제로 주어진 preorder() 연산도 매우 비슷한 식으로 구현할 수 있으니 참고로 삼으세요.

[참고] 실행 을 눌렀을 때 통과하는 것은 아무 의미 없습니다.
또한, solution() 함수는 테스트에 영향을 미치므로 수정하지 말고 그대로 두세요.
'''
class Node:
    
    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None


    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self.data)
        if self.right:
            traversal += self.right.inorder()
        return traversal

    # 나의 풀이
    def preorder(self):
        traversal = []
        traversal.append(self.data)
        if self.left:
            traversal += self.left.preorder()
        if self.right:
            traversal += self.right.preorder()
        return traversal
            


class BinaryTree:

    def __init__(self, r):
        self.root = r


    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []

    #나의 풀이
    def preorder(self):
        if self.root:
            return self.root.preorder()
        else:
            return [] 
    '''
    테스트 1 〉	통과 (0.03ms, 16.6MB)
    테스트 2 〉	통과 (0.04ms, 16.6MB)
    테스트 3 〉	통과 (0.04ms, 16.5MB)
    테스트 4 〉	통과 (0.04ms, 16.5MB)
    테스트 5 〉	통과 (0.04ms, 16.5MB)
    '''

def solution(x):
    return 0


'''
(18-03) 이진트리의 후위순회 연산 구현
문제 설명
이미 주어진 코드 (class Node 와 class BinaryTree 에 의하여) 의 구조를 따르는 이진 트리 (binary tree) 에 대하여, 트리를 후위 순회 (postorder traversal) 하는 연산의 구현을 완성하세요.

초기 코드에 pass 로만 되어 있는 class Node 의 postorder() 메서드와 class BinaryTree 의 postorder() 메서드를 구현합니다. 코드의 다른 부분은 수정할 필요가 없습니다.

참고로 할 수 있도록, 강의에서 소개한 inorder() 메서드들 (class Node 와 class BinaryTree 에 대해서) 을 그대로 두었습니다. 문제로 주어진 postorder() 연산도 매우 비슷한 식으로 구현할 수 있으니 참고로 삼으세요.

[참고] 실행 을 눌렀을 때 통과하는 것은 아무 의미 없습니다.
또한, solution() 함수는 테스트에 영향을 미치므로 수정하지 말고 그대로 두세요.
'''
class Node:
    
    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None


    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self.data)
        if self.right:
            traversal += self.right.inorder()
        return traversal


    def postorder(self):
        traversal=[]
        if self.left:
            traversal += self.left.postorder()
        if self.right:
            traversal += self.right.postorder()
        traversal.append(self.data)
        return traversal
            


class BinaryTree:

    def __init__(self, r):
        self.root = r


    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []


    def postorder(self):
        if self.root:
            return self.root.postorder()
        else:
            return []
        '''
        테스트 1 〉	통과 (0.08ms, 16.6MB)
        테스트 2 〉	통과 (0.05ms, 16.6MB)
        테스트 3 〉	통과 (0.05ms, 16.8MB)
        테스트 4 〉	통과 (0.04ms, 16.6MB)
        테스트 5 〉	통과 (0.06ms, 16.6MB)
        '''
def solution(x):
    return 0


'''
(19) 이진 트리의 넓이 우선 순회
문제 설명
이진 트리를 구현한 클래스인 class BinaryTree 에 대하여 넓이 우선 순회 (breadth first traversal) 를 구현하는 메서드 bft() 를 완성하세요.

class ArrayQueue 는 배열 (python list) 을 이용하여 구현한 큐 (queue) 의 추상적 자료구조입니다. 이것을 이용하여 넓이 우선 순회 알고리즘을 구현하세요.

[참고 1] solution() 함수의 구현은 그대로 두세요. 이것을 없애면 테스트가 되지 않습니다.

[참고 2] "코드 실행" 을 눌렀을 때 통과하는 것은 아무런 의미가 없습니다.
'''
class ArrayQueue:
    
    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def isEmpty(self):
        return self.size() == 0

    def enqueue(self, item):
        self.data.append(item)

    def dequeue(self):
        return self.data.pop(0)

    def peek(self):
        return self.data[0]


class Node:

    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None


class BinaryTree:

    def __init__(self, r):
        self.root = r

    #나의 풀이
    def bft(self):
        if self.root:
            traversal =[]
            q = ArrayQueue()
            q.enqueue(self.root)
            while not q.isEmpty():
                a = q.dequeue()
                traversal.append(a.data)
                if a.left:
                    q.enqueue(a.left)
                if a.right:
                    q.enqueue(a.right)
            return traversal
        else:    
            return []
        
        '''
        테스트 1 〉	통과 (0.04ms, 16.6MB)
        테스트 2 〉	통과 (0.04ms, 16.5MB)
        테스트 3 〉	통과 (0.04ms, 16.5MB)
        테스트 4 〉	통과 (0.04ms, 16.5MB)
        테스트 5 〉	통과 (0.04ms, 16.8MB)
        '''

def solution(x):
    return 0



'''
(20) 이진 탐색 트리의 원소 삽입 연산 구현
문제 설명
초기 코드에 주어진 class Node 와 class BinSearchTree 를 기반으로, 이진 탐색 트리 (binary search tree) 에 새로운 원소를 삽입하는 insert(key, data) 연산의 구현을 완성하세요.

class BinSearchTree 에는 이미 insert(key, data) 메서드가 구현되어 있습니다. 이것을 그대로 이용하고, class Node 의 insert(key, data) 메서드를 재귀적 방법으로 구현하세요. 강의에서 언급한 바와 같이, 이미 트리 안에 들어 있는 것과 같은 (중복된) 키를 이용하여 삽입을 시도하는 경우에는 KeyError 예외를 발생시켜야 합니다.

[참고 1] inorder() 메서드의 구현은 그대로 두세요. 테스트에 이용됩니다.

[참고 2] solution() 함수의 구현도 그대로 두세요. 이것을 없애면 테스트가 되지 않습니다.

[참고 3] "코드 실행" 을 눌렀을 때 통과하는 것은 아무런 의미가 없습니다.
'''
class Node:
    
    def __init__(self, key, data):
        self.key = key
        self.data = data
        self.left = None
        self.right = None

    # 나의 풀이
    def insert(self, key, data):
        if key < self.key:
            if self.left:
                self.left.insert(key,data)
            else:
                self.left = Node(key,data)
        
        elif key > self.key:
            if self.right:
                self.right.insert(key,data)
            else: 
                self.right = Node(key,data)       
        else:
            raise KeyError("")

    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self)
        if self.right:
            traversal += self.right.inorder()
        return traversal


class BinSearchTree:

    def __init__(self):
        self.root = None


    def insert(self, key, data):
        if self.root:
            self.root.insert(key, data)
        else:
            self.root = Node(key, data)


    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []


def solution(x):
    return 0



'''
(21) 이진 탐색 트리에서 노드의 삭제 연산 구현
문제 설명
초기 코드에 주어진 class Node 와 class BinSearchTree 를 기반으로, 이진 탐색 트리 (binary search tree) 에서 지정된 원소를 삭제하는 remove(key) 연산의 구현을 완성하세요.

class Node 와 class BinSearchTree 에 이미 구현되어 있는 코드는 수정하지 마세요. 코드 구현의 정확성 평가에 이용됩니다. 초기 코드에 들어 있는 주석을 참고로 하여, BinSearchTree::remove() 메서드의 안에 들어 있는 pass 를 없애고 그 자리에 올바른 코드를 써 넣으면 됩니다.

[참고 1] solution() 함수의 구현은 그대로 두세요. 이것을 없애면 테스트가 되지 않습니다.

[참고 2] "코드 실행" 을 눌렀을 때 통과하는 것은 아무런 의미가 없습니다.

[참고 3] 잘 생각해 보면, 이진 탐색 트리를 구현하지 않고 키 순서대로 정렬된 Python 의 배열을 유지함으로써도 같은 연산을 구현할 수 있습니다. 
        이 연습문제에서는 효율성 테스트를 하지 않기 때문에 이러한 구현을 오답으로 간주하지 않습니다만, 배열을 이용한 구현과 트리 구조를 이용한 구현은 연산의 복잡도에 큰 차이가 있습니다. 
        이진 탐색 트리로 구현하여 코드 작성 연습을 하시기 바랍니다.
'''

class Node:
    
    def __init__(self, key, data):
        self.key = key
        self.data = data
        self.left = None
        self.right = None


    def insert(self, key, data):
        if key < self.key:
            if self.left:
                self.left.insert(key, data)
            else:
                self.left = Node(key, data)
        elif key > self.key:
            if self.right:
                self.right.insert(key, data)
            else:
                self.right = Node(key, data)
        else:
            raise KeyError('Key %s already exists.' % key)


    def lookup(self, key, parent=None):
        if key < self.key:
            if self.left:
                return self.left.lookup(key, self)
            else:
                return None, None
        elif key > self.key:
            if self.right:
                return self.right.lookup(key, self)
            else:
                return None, None
        else:
            return self, parent


    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self)
        if self.right:
            traversal += self.right.inorder()
        return traversal


    def countChildren(self):
        count = 0
        if self.left:
            count += 1
        if self.right:
            count += 1
        return count


class BinSearchTree:

    def __init__(self):
        self.root = None


    def insert(self, key, data):
        if self.root:
            self.root.insert(key, data)
        else:
            self.root = Node(key, data)


    def lookup(self, key):
        if self.root:
            return self.root.lookup(key)
        else:
            return None, None


    def remove(self, key):
        node, parent = self.lookup(key)
        if node:
            nChildren = node.countChildren()
            # The simplest case of no children
            if nChildren == 0:
                # 만약 parent 가 있으면
                if parent:
                    if parent.left.key == node.key:
                        parent.left = None
                    else:
                        parent.right = None
                # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
                # parent.left 또는 parent.right 를 None 으로 하여
                # leaf node 였던 자식을 트리에서 끊어내어 없앱니다.
                
                # 만약 parent 가 없으면 (node 는 root 인 경우)
                # self.root 를 None 으로 하여 빈 트리로 만듭니다.
                else:
                    self.root = None
            # When the node has only one child
            elif nChildren == 1:
                # 하나 있는 자식이 왼쪽인지 오른쪽인지를 판단하여
                # 그 자식을 어떤 변수가 가리키도록 합니다.
                if node.left:
                    s = node.left
                else:
                    s = node.right
                # 만약 parent 가 있으면
                # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
                # 위에서 가리킨 자식을 대신 node 의 자리에 넣습니다.
                if parent:
                    if parent.left.key == node.key:
                        parent.left = s
                        s = None
                    else:
                        parent.right = s
                        s = None
                # 만약 parent 가 없으면 (node 는 root 인 경우)
                # self.root 에 위에서 가리킨 자식을 대신 넣습니다.
                else:
                    self.root = s
            # When the node has both left and right children
            else:
                # 1차 풀이(오답)
                parent = node.right
                s = parent.left
                while s.left:
                    parent = s
                    s = s.left
                node.key = s.key
                node.data = s.data
                if s.right:
                    parent.left = s.right
                if s.countChilde() == 0:
                    parent.left = None
                    
                '''
                테스트 1 〉	통과 (0.07ms, 16.8MB)
                테스트 2 〉	통과 (0.04ms, 16.7MB)
                테스트 3 〉	통과 (0.07ms, 16.7MB)
                테스트 4 〉	통과 (0.06ms, 16.7MB)
                테스트 5 〉	실패 (런타임 에러)
                테스트 6 〉	실패 (런타임 에러)
                테스트 7 〉	통과 (0.06ms, 16.9MB)
                테스트 8 〉	실패 (런타임 에러)
                테스트 9 〉	실패 (런타임 에러)
                '''
                    
                    
                # 2차 풀이(정답)
                s = node.right
                parent = node
                while s.left:
                    parent = s
                    s = parent.left
                    
                node.key = s.key
                node.data = s.data
                
                if parent.right == s: # node 가 곧 parent인 경우, s의 child가 left 가 없는 경우  
                    parent.right = s.right                   
                if parent.left == s:
                    parent.left = s.right
                    
                '''
                테스트 1 〉	통과 (0.13ms, 16.8MB)
                테스트 2 〉	통과 (0.04ms, 16.7MB)
                테스트 3 〉	통과 (0.07ms, 16.7MB)
                테스트 4 〉	통과 (0.06ms, 16.8MB)
                테스트 5 〉	통과 (0.06ms, 16.8MB)
                테스트 6 〉	통과 (0.06ms, 16.7MB)
                테스트 7 〉	통과 (0.06ms, 16.8MB)
                테스트 8 〉	통과 (0.06ms, 16.7MB)
                테스트 9 〉	통과 (0.07ms, 16.7MB)
                '''

            return True

        else:
            return False


    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []


def solution(x):
    return 0



'''
(22) 최대 힙에 새로운 원소 삽입
문제 설명
초기 코드에 주어진 class MaxHeap 에 최대 힙에 새로운 원소를 추가하는 연산인 insert() 메서드의 구현을 완성하세요.

[참고 1] solution() 함수의 구현은 그대로 두세요. 이것을 없애면 테스트가 되지 않습니다.

[참고 2] "코드 실행" 을 눌렀을 때 통과하는 것은 아무런 의미가 없습니다.
'''
class MaxHeap:
    
    def __init__(self):
        self.data = [None]


    def insert(self, item):
        # 나의 풀이
        a = self.data
        a.append(item)
        itemIndex       = a.index(item)
        
        while itemIndex != 1:
            parentIndex     = itemIndex // 2
            if a[itemIndex] > a[parentIndex]:
                a[itemIndex], a[parentIndex] = a[parentIndex], a[itemIndex]
                itemIndex, parentIndex = itemIndex, parentIndex 
                itemIndex     = itemIndex // 2
            else:
                break
            
            '''
            테스트 1 〉	통과 (0.06ms, 16.5MB)
            '''
     
        # 다른 풀이        
        self.data.append(item)
        i = len(self.data) - 1
        while i != 1:
            if self.data[i] > self.data[(i // 2)]:
                self.data[i], self.data[(i // 2)] = self.data[(i // 2)], self.data[i]
                i = i // 2
            else:
                break

def solution(x):
    return 0



'''
(23) 최대 힙에서의 원소 삭제
문제 설명
초기 코드에 여기 저기 포함된 빈 칸을 채움으로써 class MaxHeap 의 메서드인 maxHeapify() 의 구현을 완성하세요. 이것은 이미 주어져 있는 remove() 메서드와 연결되어 최대 힙에서의 원소 삭제 연산을 구성합니다.

[참고 1] remove() 메서드의 내용은 이미 주어져 있으므로 수정하지 않는 쪽이 좋습니다.

[참고 2] solution() 함수의 구현은 그대로 두세요. 이것을 없애면 테스트가 되지 않습니다.

[참고 3] "코드 실행" 을 눌렀을 때 통과하는 것은 아무런 의미가 없습니다.
'''
class MaxHeap:

    def __init__(self):
        self.data = [None]


    def remove(self):
        if len(self.data) > 1:
            self.data[1], self.data[-1] = self.data[-1], self.data[1]
            data = self.data.pop(-1)
            self.maxHeapify(1)
        else:
            data = None
        return data

    # 나의 풀이
    def maxHeapify(self, i):
        # 왼쪽 자식 (left child) 의 인덱스를 계산합니다.
        left = 2*i

        # 오른쪽 자식 (right child) 의 인덱스를 계산합니다.
        right = 2*i +1

        smallest = i
        # 왼쪽 자식이 존재하는지, 그리고 왼쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if left < len(self.data) and self.data[left] > self.data[i]:
            # 조건이 만족하는 경우, smallest 는 왼쪽 자식의 인덱스를 가집니다.
            
            smallest = left

        # 오른쪽 자식이 존재하는지, 그리고 오른쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if right < len(self.data) and self.data[right] > self.data[smallest]: 
            #### ⭐️⭐️ i, right, left 셋 중 최대값(smallest)을 찾는 것인데 처음에 self.data[right] > self.data[i]로 작성했다가 엄청 해맸다...
            ## 출제자 분이 최대값의 변수 명을 great가 아닌 smallest로 지정해놓으셔서 더 헷갈린 것도 있었던 것 같다. 
                        
            # 조건이 만족하는 경우, smallest 는 오른쪽 자식의 인덱스를 가집니다.
            smallest = right

        if smallest != i:
            # 현재 노드 (인덱스 i) 와 최댓값 노드 (왼쪽 아니면 오른쪽 자식) 를 교체합니다.
            self.data[i], self.data[smallest] = self.data[smallest], self.data[i]

            # 재귀적 호출을 이용하여 최대 힙의 성질을 만족할 때까지 트리를 정리합니다.
            self.maxHeapify(smallest)
            
    '''
    테스트 1 〉	통과 (0.06ms, 16.8MB)
    '''


def solution(x):
    return 0
import json
from typing import Counter
from django import views
import django
# import requests

from django.views         import View
from django.http.response import JsonResponse



class GrammerView(View):
    def get(self, request):
        '''
        [ 값 교환 ]
        =======================
        a, b = 10, 20
        a, b = b, a
        print(a, b)
        => 결과 : 20, 10
        
        [ 출력 ] 
        =======================
        print("number : ", a, b, c)
        => number : 1, 2, 3
        
        print(i, sep=', ')
        => 1, 2, 3
        
        print(i, sep='')
        => 123
        
        print(i, sep='\n')
        =>
        1
        2
        3
        
        print(i, end=' ')
        => 결과 : 1 2 3 6 7 14 21 42
        
        =======================
            
        [ 반복문 ]
        
        @ For
        =======================
        1) i 증가
            for i in range(10):
                print(i)
            
            => 결과 : 0~9
            
        2) i 감소
            for i in range(10, 0, -2):
                print(i)
            => 결과 : 10, 8, 6, 4, 2
    
        2) 특정 조건에 해당하면 다시 반복문 처음으로 돌아가게하기
            for i in range(10):
                if i%2 == 0:
                    continue
                print(i) # 홀수만 출력됨
                i=i+1
                
                
            3) 특정 상황에서 반복문 멈추게 하기
            ** for ~, else~ 구문 : for 문에서 break가 걸리면, 실행되지 않는다. break가 걸리지 않을 때만 실행된다. 
            
                for i in range(1,11):
                    print(i)
                    if i>15:
                        break
                else:
                    print(11)

                    
                    
        @ While : 조건이 들어간다. i<=10이 참일 때, 반복문 중지
        =======================
        1) i 증가
            i=1
            while i<=10:
                print(i)
                i=i+1
            
        2) i 감소     
            i=10
            while i>=1:
                print(i)
                i=i-1
            
        3) 무한반복을 멈추게 하거나, 특정 상황에서 반복문 멈추게 하기
            i=1
            while True:
                print(i)
                if i == 4:
                    break
                i=i+1         
            
        4) 특정 조건에 해당하면 다시 반복문 처음으로 돌아가게하기
            ** 주의 while문에서 적용할 때는 i의 증감 연산자가 continue보다 먼저 오지 않으면, 반복문이 계속 돌게된다. 
            i = 1
            while i<10:
                i=i+1
                if i % 2 == 0:
                    continue
                print(i)
            
            => 결과 : 3, 5, 7, 9
            
            
        
        [ 반복문을 이용한 문제풀이 ]
        ==========================
        1) 1부터 N까지 홀수 출력하기
            input() :  값을 입력 받는다. ** 타입은 문자가 되므로 연산을 하고싶다면, int형으로 바꿔주어야함.
            
            n=int(input()) 
            for i in range(1, n+1):
                if i%2==1:
                    print(i)
                
        2) 1부터 N까지의 합 구하기
        
            sum=0
            n=int(input()) 
            for i in range(1, n+1):
                sum=sum+i
            print(sum)
        
        3) N의 약수 출력하기// 약수 : 1 부터 나 자신의 수까지, 나 자신과 나눠서 0이 되는 어떤 수 .
        
        n=int(input()) 
        for i in range(1,n+1):
            if n%i==0:
                print(i, end=' ')
        => 1 2 3 6 7 14 21 42
        
       
        
        [ 중첩 반복묵(2중 for 문) ]
        ============================
        for i in range(5):
            for j in range(5):
                print('*', end=' ')
            print()                                                                                
        
        * * * * *
        * * * * *
        * * * * *
        * * * * *
        * * * * *
        
        for i in range(5):
            for j in range(i+1):
                print('*', end=' ')
            print()    
                        
        *
        * *
        * * *
        * * * *
        * * * * *
        
        for i in range(5):
            for j in range(5-i):
                print('*', end=' ')
            print()        
            
        * * * * *
        * * * *
        * * *
        * *
        *      
        
        
        [ 문자열과 내장함수 ]
        ================================
           
        1) upper()  : 문자열 모두 대문자 전환 
            msg = "It is Time"
            print(msg.upper())      
            => IT IS TIME   
        2) lower()  :  문자열 모두 소문자 전환
            msg = "It is Time"
            print(msg.lower())   
            => it is time   
        3) find('T') : 처음 발견되는 T의 인덱스 번호
            msg = "It is Time"
            print(msg.find('T'))  
            => 6 
        4) count('T') : T의 갯수
            msg = "It is Time"
            print(msg.count('T'))  
            => 1
        5) [:2] : 0~1인덱스까지의 문자열 추출
            msg = "It is Time"
            print(msg[:2])  
            => It
        6) [3:5] : 3~4덱스까지의 문자열 추출
            msg = "It is Time"
            print(msg[3:5])  
            => is
        7) len(msg) : 문자열의 길이(공백 포함)    
            msg = "It is Time"
            for i in range(len(msg)):
                print(i, end=' ')
            => 0 1 2 3 4 5 6 7 8 9
        9) 문자열 리스트의 문자 하나하나 반환
        
        (방법1)
            msg = "It is Time"
            for i in range(len(msg)):
                print(msg[i], end=' ')
            print()
            =>I t   i s   T i m e
        
        (방법2)
            msg = "It is Time"
            for x in msg:
                print(x, end=' ')
            print()
            =>I t   i s   T i m e
        
        10) isupper() : 대문자면 true // 대문자만 출력
            msg = "It is Time"
            for x in msg:
                if x.isupper():
                    print(x, end=' ')    
            =>I T
        
        11) islower() : 소문자면 true // 소문자만 출력
            msg = "It is Time"
            for x in msg:
                if x.islower():
                    print(x, end=' ')    
            =>t i s i m e
            
        11) isalpha() : 공백은 X, 오직 알파벳일 때만
        msg = "It is Time"
        for x in msg:
            if x.isalpha():
                print(x, end='')    
        =>ItisTime
        
        12)  ord() : 아스키 넘버 출력(A ~ Z : 65 ~ 90, a ~ z : 97~122)
        
        tmp='AZ'
        for x in tmp:
            print(ord(x))
            
        tmp='az'
        for x in tmp:
            print(ord(x))
            
        
        13)  chr() : 아스키 넘버에 대응되는 문자 출력(A ~ Z : 65 ~ 90, a ~ z : 97~122)
        tmp=65
        print(chr(tmp))
        
        
        [리스트와 내장함수]
        ======================
        - 리스트 : 변수 하나하나를 나열하여 인덱스를 붙인 것. a1,a2,a3.. =>a[0], a[1], a[2]
        1) 빈리스트 만들기
                a = []
                print(a)
                b=list()
                print(b)       
                =>[], [] 
        
        
        2) 값이 있는 리스트 만들기 
            (1) a = [1,2,3,4,5]
            
            (2) b = list(range(1,11))
            
            (3) c=a+b
        
        
        3) a.append(6) # 리스트 멘 마지막에 값 6을 추가
            print(a)
        
        4) a.insert(3,7)# 3번 인덱스에 7을 추가, 나머지는 뒤로 밀림
            print(a)
        
        5) a.pop() # 리스트에서 마지막 값을 제거
            print(a)
        
        6) a.pop(3) # 3번 인덱스의 값을 제거
            print(a)
        
        7) a.remove(4) # 리스트에서 값 4 를 제거, 앞으로 당겨짐
            print(a)
        
        8) a.index(5) # 5라는 값이 몇번 인덱스에 있는지
            print(a.index(5))
            
            a=list(range(1,11))
        
        9) print(sum(a)) # 1~10의 모든 수의 합
        
        10) print(max(a)) # 최대값
        
        11) print(min(a)) # 최소값 
            print(min(7,5)) # 인자들 중 최소값       
            print(min(7,3,5)) # 인자들 중 최소값       
            print(max(7,5)) # 인자들 중 최대값    
        
        12) 무작위로 섞기
        
            import random as r
            
            r.shuffle(a) # 무작위로 섞기
            print(a)   
        
        13) a.sort() #오름차순
            print(a)   
        
        14) a.sort(reverse=True) # 내림차순
            print(a)   

        15) a.clear() # 빈리스트로 만들기
            print(a)   
            
        
        리스트와 내장함수(2)
        ========================
        a=[23, 12, 36, 53, 19]
        print(a[:3])
        print(a[1:4])
        
        1.  리스트 값 출력
        =====================
        방법 1)
            for i in range(len(a)):
                print(a[i], end=' ')
            print()
            =>23 12 36 53 19
        
            for x in a:
                print(x, end=' ')
            print()
            =>23 12 36 53 19
        
        방법 2)
            for x in a:
                if x%2==1:
                    print(x, end=' ')
            print()
        
        방법 3) enumerate()
            for x in enumerate(a):#(인덱스, value)의 형태로 튜플 반환
                print(x)
            =>  (0, 23)
                (1, 12)
                (2, 36)
                (3, 53)
                (4, 19)
        
            ** 튜플의 구조는 리스트와 같으나, 값을 변경할 수 없다.
                a = [23, 12, 36, 53, 19]
                a[0] = 43
                print(a)
                =>[43, 12, 36, 53, 19]
                
                a = (23, 12, 36, 53, 19)
                a[0] = 43
                =>TypeError: 'tuple' object does not support item assignment
            
        방법 4) x[0], x[1]
            for x in enumerate(a):
                print(x[0], x[1]) # x=(인덱스, value)이므로 x[0]은 인덱스 , x[1]은 값 
            =>
            0 23
            1 12
            2 36
            3 53
            4 19
        
        방법 5) 가장 많이 쓰는 enumerate 사용
            for index, value in enumerate(a):
                print(index, value)
            print()
            =>
            0 23
            1 12
            2 36
            3 53
            4 19
        
        방법 6) 가장 많이 쓰는 enumerate 사용
            if all(60>x for x in a): # 모두 충족하면 참
                print("YES")
            else:
                print("NO")

            if any(15>x for x in a): # 한가지라도 충족하면 참
                print("YES")
            else:                    # 모두가 충족안할때, 거짓
                print("NO")
            
        
        
        [2차원 리스트 생성과 접근]
        =========================
        a = [0] * 10 # 인덱스 번호가 0~9까지인 크기가 10인 일차원 리스트    
        a = [0] * 3 # 인덱스 번호가 0~2까지인 크기가 3인 일차원 리스트
        
        1)  for _ in range(3) // _를 하면 변수없이 반복문이 3번 돈다.
            a=[[0]*3 for _ in range(3)] # [0]*3 가 3번 반복됨.    
            print(a)
            =>[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
            열       
            행    0  1  2
            0 [0, 0, 0]
            1 [0, 0, 0]
            2 [0, 0, 0]
            
            열       
            행    0  1  2
            0 [0, 1, 0]
            1 [0, 2, 0]
            2 [0, 0, 0]
            
            a=[[0]*3 for _ in range(3)] # [0]*3 가 3번 반복됨.    
            a[0][1]=1
            a[1][1]=2
            print(a)
            =>[[0, 1, 0], [0, 2, 0], [0, 0, 0]]
            
        
        2) 2차원 리스트 표로 출력하기
            for x in a:
                print(x)
            =>
            [0, 1, 0]
            [0, 2, 0]
            [0, 0, 0]
            
        
        3) 대괄호없이 2차원 리스트 출력하기
            a=[[0]*3 for _ in range(3)] # [0]*3 가 3번 반복됨.    
            for x in a:
                for y in x:
                    print(y, end=' ')
                print()
            =>
            0 0 0   
            0 0 0
            0 0 0    
            
        
        
        [함수 만들기]
        =================
        # 함수는 값을 return 하며, 함수를 종료 한다.
            def add(a,b):
                c=a+b
                return c
            print(add(3,2))
            =>5
        # 파이썬에서는 2개이상의 값을 튜플로 반환할 수 있다.
            def add(a,b):
                c=a+b
                d=a-b
                return c, d
            print(add(3,2))
            =>(5, 1)
        
        # 소수(나누어 떨어지지 않는 수 )만 출력하는 함수 만들기(1~자기자신까지의 수중 1,과 자기자신을 제외하고 나누어서 떨어지지 않는 수)
            def isPrime(x):
                for i in range(2,x):
                    if x%i==0:
                        return False # 여기서 함수가 종료됨.
                return True


        a=[12, 13, 7, 9, 19]
        for y in a:
            if isPrime(y):
                print(y, end=' ')
        
        
            
        [람다함수]
        ====================
        - 람다함수 : 익명의 함수 또는 표현식
        
        def plus_one(x):
            return x+1
        print(plus_one(1))
        =>2
        
        # 람다함수(익명의 함수)로 표현하기(변수에 담아서 호출해주어야함)
        plus_two=lambda x: x+2
        print(plus_two(1))
        =>3
        
        
        * map(함수, 함수를 적용할 자료)
            a=[1,2,3]
            print(list(map(plus_one, a)))
            =>[2, 3, 4]
        
        * 함수 이름이 필요없이 익명의 함수를 사용하여 바로 사용할수있음.
            print(list(map(lambda x: x+1, a))) 
            =>[2, 3, 4]
        
            
        [선형 탐색, x의 위치 찾기]
        ====================
            L = [3,8,2,7,6,10,9]
            x = 6
            def linear_search(S, x):
                i=0
                while i<len(L) and L[i] != x:
                    i+=1
                if i < len(L):
                    return i
                else:
                    return -1    
                
            def linear_search(S, x):
                return S.index(x)
        
        
        [재귀 알고리즘]
        =============== 
        1) 잘못된 예시 -  종결 조건이 없음   
            def sum1(n):
                print(n)
                return n + sum1(n -1) # 자신을 재귀호출하고있음.
            # a = int (input("Number:"))
            # print(sum(a))
            Number:30
            30
            29
            28
            27
            26
            25
            24
            23
            22
            21
            -995..
            ..... 에러가 남....
            
            def sum2(n):
                print(n)
                if n<= 1:
                    return n
                else:
                    return n+ sum2(n-1)
            n=10일때 콘솔에 찍히는 결과 
            10
            9
            8
            7
            6
            5
            4
            3
            2
            1
            
            sum2(10) = 55
            a = int(input("Number:"))
            print(sum2(a))
            
        '''
        return JsonResponse({"MESSAGE": "Hello"}, status=200)
# 2. 선형 배열 알고리즘 풀이
class ProgrammersExample2View(View):
    def get(self, request):
        '''(02) 정렬된 리스트에 원소 삽입
        리스트 L 과 정수 x 가 인자로 주어질 때, 리스트 내의 올바른 위치에 x 를 삽입하여 그 결과 리스트를 반환하는 함수 solution 을 완성하세요.

        인자로 주어지는 리스트 L 은 정수 원소들로 이루어져 있으며 크기에 따라 (오름차순으로) 정렬되어 있다고 가정합니다.

        예를 들어, L = [20, 37, 58, 72, 91] 이고 x = 65 인 경우, 올바른 리턴 값은 [20, 37, 58, 65, 72, 91] 입니다.

        힌트: 순환문을 이용하여 올바른 위치를 결정하고 insert() 메서드를 이용하여 삽입하는 것이 한 가지 방법입니다.

        주의: 리스트 내에 존재하는 모든 원소들보다 작거나 모든 원소들보다 큰 정수가 주어지는 경우에 대해서도 올바르게 처리해야 합니다.
        '''
        x = 65
    
        L = [20, 37, 58, 72, 91]
        
        def solution1(L, x): # 풀이 실패 -> 시간 초과 및 반복문 멈추는 것 고려하지 않음
            answer = []
            for y in L:
                if x > y:
                    if L.index(y) != len(L)-1:
                        L.insert(L.index(y)+1,x)
                    else: L.append(x)
                elif x < y:
                    if L.index(y) == 0:
                        L.insert(0,x)
                    else:
                        L.insert(L.index(y)-1,x)
                        
            answer = L        
            return answer
        
        def solution2(L, x): # 풀이 실패 -> enumerate를 사용하였으나, 역시 시간 초과 및 반복문을 멈추는 것을 고려하지 않음.
            answer = []
            for index, value in enumerate(L) :
                if x > value:
                    if index != len(L)-1:
                        L.insert(index+1,x)
                    else: L.append(x)
                elif x < value:
                    if index == 0:
                        L.insert(0,x)
                    else:
                        L.insert(index,x)
            answer = L        
            return answer
        
        def solution3(L, x): # PASS!!!
            # 반복문이 계속 도는 것이 문제였으며, 이로인해 시간이 초과되는 것을 깨달음. 이를 잡아주니 풀이 성공!!!!! 
            for index, value in enumerate(L) :
                if x > value:
                    if index == len(L)-1:
                        L.append(x)
                        break
                    else:
                        continue
                else: 
                    L.insert(index,x)
                    break
            return L 
        
        def solution4(L, x): # 나와 비슷한 풀이
            for idx, num in enumerate(L):
                if num > x:
                    L.insert(idx,x)
                    break

                if L[-1] < x: # L[-1]은 리스트 맨 끝에 있는 수를 지칭 한다!!, 맨 끝자리이면서, x가 값이 크다는 것을 모두 충족함.
                    L.append(x)
                else:
                    pass
            return L
        
        def solution5(L, x): # 오름차순이라는 문제의 함정을 이용한 문제 풀이
            L.append(x)
            L.sort()
            return L

        return JsonResponse({"RESULT": solution3(L,x)}, status=200)

    def post(self, request):
        
        '''
        문제 설명
        인자로 주어지는 리스트 L 내에서, 또한 인자로 주어지는 원소 x 가 발견되는 모든 인덱스를 구하여 
        이 인덱스들로 이루어진 리스트를 반환하는 함수 solution 을 완성하세요.

        리스트 L 은 정수들로 이루어져 있고 그 순서는 임의로 부여되어 있다고 가정하며, 동일한 원소가 반복하여 들어 있을 수 있습니다. 
        이 안에 정수 x 가 존재하면 그것들을 모두 발견하여 해당 인덱스들을 리스트로 만들어 반환하고, 
        만약 존재하지 않으면 하나의 원소로 이루어진 리스트 [-1] 를 반환하는 함수를 완성하세요.

        예를 들어, L = [64, 72, 83, 72, 54] 이고 x = 72 인 경우의 올바른 리턴 값은 [1, 3] 입니다.
        또 다른 예를 들어, L = [64, 72, 83, 72, 54] 이고 x = 83 인 경우의 올바른 리턴 값은 [2] 입니다.
        마지막으로 또 다른 예를 들어, L = [64, 72, 83, 72, 54] 이고 x = 49 인 경우의 올바른 리턴 값은 [-1] 입니다.

        힌트 1: 리스트의 index() 메서드와 리스트 슬라이싱을 활용하는 것이 한 가지 방법이 됩니다. 리스트 슬라이싱은 아래와 같이 동작합니다.

        L = [6, 2, 8, 7, 3] 인 경우
        L[1:3] = [2, 8]
        L[2:] = [8, 7, 3]
        L[:3] = [6, 2, 8]

        힌트 2: 리스트의 index() 메서드는, 인자로 주어지는 원소가 리스트 내에 존재하지 않을 때 ValueError 를 일으킵니다. 
        이것을 try ... except 로 처리해도 되고, "if x in L" 과 같은 조건문으로 특정 원소가 리스트 내에 존재하는지를 판단해도 됩니다.
        '''
        x= 72
        L= [64, 72, 83, 72, 54]
        def solution1(L,x): # 나의 풀이 ) PASS!!
            answer =[]
            validate=True
            for indx, num in enumerate(L):
                if x == num:
                    answer.append(indx)
                    validate=False
            if validate:
                answer=[-1]   
            return answer
        
        def solution2(L, x): # 다른 풀이 : 리스트 컴프리헨션으로 깔끔하게!
            if x in L:
                return [i for i, y in enumerate(L) if y == x] # 조건문이 만족 할 떄, i를 리스트에 담는다.
            else:
                return [-1]
            
        
        
        return JsonResponse({"RESULT": solution1(L,x)}, status=200)
    
  
# 3. 정렬, 탐색 알고리즘 풀이
class ProgrammersExample3View(View):
    
    def get (self, request):
        '''
        (03) 이진탐색
        
        문제 설명
        리스트 L 과, 그 안에서 찾으려 하는 원소 x 가 인자로 주어질 때, 
        x 와 같은 값을 가지는 원소의 인덱스를 리턴하는 함수 solution() 을 완성하세요. 
        만약 리스트 L 안에 x 와 같은 값을 가지는 원소가 존재하지 않는 경우에는 -1 을 리턴합니다. 
        리스트 L 은 자연수 원소들로 이루어져 있으며, 크기 순으로 정렬되어 있다고 가정합니다. 
        또한, 동일한 원소는 두 번 이상 나타나지 않습니다.

        예를 들어,
        L = [2, 3, 5, 6, 9, 11, 15]
        x = 6
        의 인자들이 주어지면, L[3] == 6 이므로 3 을 리턴해야 합니다.

        또 다른 예로,
        L = [2, 5, 7, 9, 11]
        x = 4
        로 주어지면, 리스트 L 내에 4 의 원소가 존재하지 않으므로 -1 을 리턴해야 합니다.

        이 연습문제에서는 알고리즘의 효율성도 평가합니다. 만약 순차 (선형) 탐색 알고리즘을 구현하는 경우에는
        제한 시간 요구사항을 만족하지 못하여 효율성 테스트 케이스들을 통과하지 못할 수도 있습니다.

        '''
        L = [2, 3, 5, 6, 9, 11, 15]
        #L = [] 
        x = 15
        #x = 20
        
        def solution1(L, x):
            indx = -1 
            if len(L) == 0:
                return indx

            lower=0
            upper=len(L)-1
            tmp =[]
            
            while lower <= upper:
                middle=(lower+upper)//2
               
                if x > L[middle]:
                    lower=middle+1
                elif x < L[middle]:
                    upper=middle-1
                elif x == L[middle]:
                    indx = middle
                    return indx
                tmp = L[lower:upper+1] # 뭔가 이 과정에서 시간을 많이 잡아 먹는 다는 생각이 들었고, 최종 lower와 upper 만을 사용하여 , tmp 리스트를 구하면 될것같았다.
            
            if x not in tmp:
                return indx
                    
                #L=L[lower:upper+1] # L를 슬라이싱 해버리면, 인덱스가 0부터 시작하므로 IndexError: list index out of range가 계속 뜬다는 점 유의!!!
            return indx
        
              
        def solution2(L, x): # PASS!!!! 
            # [1] 빈 리스트가 들어올 때와 [2] 리스트에 없는 값이 들어올 때의 예외 처리에 유의 하여야겠다.
            '''
            정확성: 55.6
            효율성: 44.4
            합계: 100.0 / 100.0
            '''
            indx = -1 
            lower=0
            upper=len(L)-1
            
            if len(L) == 0:
                return indx

            while lower <= upper:
                middle=(lower+upper)//2
               
                if x > L[middle]:
                    lower=middle+1
                elif x < L[middle]:
                    upper=middle-1
                elif x == L[middle]:
                    indx = middle
                    return indx
            
            if x not in L[lower:upper+1]:
                return indx
        
        def solution3(L, x): # PASS!!!! 
            # -1의 중복을 줄어 효율성을 높여보자.
            '''
            정확성: 55.6
            효율성: 44.4
            합계: 100.0 / 100.0
            '''
            lower=0
            upper=len(L)-1

            while lower <= upper:
                middle=(lower+upper)//2
               
                if x > L[middle]:
                    lower=middle+1
                elif x < L[middle]:
                    upper=middle-1
                else:
                    return middle
            return -1
                    
        return JsonResponse({"RESULT": solution3(L,x)}, status=200)
    
class ProgrammersExample4View(View):
    
    def get (self, request):
    
        '''
        (04) 피보나치 순열
        문제 설명
        인자로 0 또는 양의 정수인 x 가 주어질 때, 
        Fibonacci 순열의 해당 값을 구하여 반환하는 함수 solution() 을 완성하세요.

        Fibonacci 순열은 아래와 같이 정의됩니다.
        F0 = 0
        F1 = 1
        Fn = Fn - 1 + Fn - 2, n >= 2

        재귀함수 작성 연습을 의도한 것이므로,
        재귀적 방법으로도 프로그래밍해 보고, 반복적 방법으로도 프로그래밍해 보시기 바랍니다.
        '''
        n=int(input("Number"))
        
        # 1) 재귀함수로 풀기
        def solution1_F(n):
            if n <=1:
                return n
            else:
                return solution1_F(n-1) + solution1_F(n-2)   
        
        def solution2_F(x):
            return n if n <=1 else solution2_F(n-1) + solution2_F(n-2) 
        
        # 2) 반복함수로 풀기 난이도 ⭐️⭐️⭐️⭐️⭐️
        def solution3_F(n):
            answer=0 # n=3
            fa = 0
            fb = 1
            # if n == 0: return 0 //  answer가 0으로 초기화 되어있으므로 안써줘도 상관없음. 
            while n>0:
                n-=1
                fa, fb = fb(1), fa+fb(0+1) # 값변경 사용
                answer = fa
            return answer       
         
        return  JsonResponse({"RESULT": solution2_F(n)}, status=200)
    
class ProgrammersExample5View(View):
    '''
    # (05) 재귀적 이진탐색

    문제 설명

    리스트 L 과, 그 안에서 찾으려 하는 원소 x 가 인자로 주어지고, 
    
    또한 탐색의 대상이 되는 리스트 내에서의 범위 인덱스가 l 부터 u 까지로 (인자로) 정해질 때, 
    
    x 와 같은 값을 가지는 원소의 인덱스를 리턴하는 함수 solution() 을 완성하세요. 
    
    만약 리스트 L 안에 x 와 같은 값을 가지는 원소가 존재하지 않는 경우에는 -1 을 리턴합니다. 
    
    리스트 L 은 자연수 원소들로 이루어져 있으며, 크기 순으로 정렬되어 있다고 가정합니다. 또한, 동일한 원소는 두 번 이상 나타나지 않습니다.

    인덱스 범위를 나타내는 l 과 u 가 인자로 주어지는 이유는, 이 함수를 재귀적인 방법으로 구현하기 위함입니다. 
    
    빈 칸에 알맞은 내용을 채워서 재귀 함수인 solution() 을 완성하세요.

    예를 들어,L = [2, 3, 5, 6, 9, 11, 15]x = 6l = 0u = 6의 인자들이 주어지면, L[3] == 6 이므로 3 을 리턴해야 합니다.

    또 다른 예로,L = [2, 5, 7, 9, 11]x = 4l = 0u = 4로 주어지면, 리스트 L 내에 4 의 원소가 존재하지 않으므로 -1 을 리턴해야 합니다.
    '''
    def get (self, request):
        '''
        정확성: 55.6
        효율성: 0.0
        합계: 55.6 / 100.0
        '''
        L = [2, 5, 7, 9, 11]
        x = 4
        l = 0
        u = 4
        def solution1(L, x, l, u):
            if "x not in L":
                return -1
            mid = (l + u) // 2
            if x == L[mid]:
                return mid
            elif x < L[mid]:
                return "solution1(L, x, l, mid-1)" 
            else:
                return "solution1(L, x, mid+1, u)"
        
        
        def solution2(L, x, l, u):
            '''
            난이도 ⭐️⭐️⭐️⭐️⭐️ 효율성 생각하기!!!
            채점 결과
            정확성: 55.6
            ⭐️ 효율성: 44.4  
            합계: 100.0 / 100.0
            '''
            if "l>u":  # ⭐️ x가 리스트 L에 없다면,  
                        #x=10 L=[11,15]일때, lower는 0, mid=0.5, upper=1로 까지 가게 되므로, u=-0.5, l=1.5가 된다. => 뒤바뀜. 
                        #x=16 L=[11,15]일때, lower는 0, mid=0.5, upper=1로 까지 가게 되므로, u=1, l=1.5가 된다. => 뒤바뀜. 
                return -1
            mid = (l + u) // 2
            if x == L[mid]:
                return mid
            elif x < L[mid]:
                return "solution2(L, x, l, mid-1)" 
            else:
                return "solution2(L, x, mid+1, u)"
        
        return  JsonResponse({"RESULT": solution2(L, x, l, u)}, status=200)

class ProgrammersExample7View(View):
    '''
    (07) 연결 리스트 순회
    문제 설명
    제 7 강에서 소개된 추상적 자료구조로 LinkedList 라는 이름의 클래스가 정의되어 있다고 가정하고, 이 리스트를 처음부터 끝까지 순회하는 메서드 traverse() 를 완성하세요.

    메서드 traverse() 는 리스트를 리턴하되, 이 리스트에는 연결 리스트의 노드들에 들어 있는 데이터 아이템들을 연결 리스트에서의 순서와 같도록 포함합니다. 예를 들어, LinkedList L 에 들어 있는 노드들이 43 -> 85 -> 62 라면, 올바른 리턴 값은 [43, 85, 62] 입니다.

    이 규칙을 적용하면, 빈 연결 리스트에 대한 순회 결과로 traverse() 메서드가 리턴해야 할 올바른 결과는 [] 입니다.

    [참고] "실행" 을 눌렀을 때 통과하는 것은 아무 의미 없습니다. 
    '''
    def get (self, request):
        class Node:
            def __init__(self, item):
                self.data = item
                self.next = None

        class LinkedList:
            def __init__(self):
                self.nodeCount = 0
                self.head = None
                self.tail = None

            def getAt(self, pos):
                if pos < 1 or pos > self.nodeCount:
                    return None
                i = 1
                curr = self.head
                while i < pos:
                    curr = curr.next
                    i += 1
                return curr

            def traverse(self):
                answer=[]
                a = self.head
                while a != None:            # 빈 리스트라면 head와 tail이 None
                    answer.append(a.data) 
                                            # 빈 리스트가 아니라면 헤더가 존재하므로 추가, 
                                            # a는 노드의 순서만 의미하므로, 노드이 데이터에 접근하려면 a.data를 해주어야함. 
                    a = a.next              # 헤드의 다음 연결 노드로 접근
                return answer

            def solution(x):
                return 0
        
        return  JsonResponse({"RESULT": []}, status=200)
 
class ProgrammersExample8View(View):
    '''
    문제 설명
    제 8 강에서 소개된 추상적 자료구조 LinkedList 클래스의 메서드로서 popAt() 메서드를 강의 내용에 소개된
    요구조건을 만족시키도록 구현하세요.

    초기 코드로 들어 있는 것은 solution() 함수를 포함하여 다른 부분은 수정하지 말고, 
    def popAt(self, pos): 의 메서드 몸체만 구현하세요.

    만약, 인자로 주어진 pos 가 올바른 범위의 값을 가지지 않는 경우에는 IndexError exception 을 발생시키도록 합니다. 
    이렇게 하기 위한 코드는 raise IndexError 입니다.
'''
    def get (self, request):
        class Node:
            
            def __init__(self, item):
                self.data = item
                self.next = None


        class LinkedList:

            def __init__(self):
                self.nodeCount = 0
                self.head = None
                self.tail = None


            def getAt(self, pos):
                if pos < 1 or pos > self.nodeCount:
                    return None

                i = 1
                curr = self.head
                while i < pos:
                    curr = curr.next
                    i += 1

                return curr


            def insertAt(self, pos, newNode):
                if pos < 1 or pos > self.nodeCount + 1:
                    return False

                if pos == 1:
                    newNode.next = self.head
                    self.head = newNode

                else:
                    if pos == self.nodeCount + 1:
                        prev = self.tail
                    else:
                        prev = self.getAt(pos - 1)
                        newNode.next = prev.next
                        prev.next = newNode

                if pos == self.nodeCount + 1:
                    self.tail = newNode

                self.nodeCount += 1
                return True

            # 1차 작성 코드
            def popAt_1(self, pos):
                #인덱스 벗어났을 때,
                if pos < 1 or pos > self.nodeCount: 
                    raise IndexError
                '''
                1) head를 없애는 경우, pos == 1
                2) tail을 없애는 경우, pos == nodeCount
                3) nodeCount ==1, pos ==1,  유일한 노드를 없애는 경우 + 2) tail을 없애는 경우, pos == nodeCount
                4) nodeCount > 1 1<post<nodeCount
                '''
                
                if pos == self.nodeCount: # tail의 노드를 없앨 경우  + 빈리스트
                    prev = self.getAt(pos-1)
                    curr = self.tail
                    self.tail = prev

                if pos == 1: # head의 노드를 없앨 경우 +  빈리스트
                    curr = self.head
                    self.head = curr.next
                else:
                    prev = self.getAt(pos-1)
                    if pos == self.nodeCount:
                        curr = self.tail
                        self.tail = prev
                    else:
                        curr = prev.next
                        prev.next = curr.next
                        
                    if self.nodeCount == 1:

                        curr = self.head

                self.nodeCount -=1

                return curr.data
            
            # 2차 작성 코드
            def popAt_2(self, pos):
                '''
                테스트 1 〉	통과 (0.05ms, 16.8MB)
                테스트 2 〉	통과 (0.06ms, 16.6MB)
                테스트 3 〉	통과 (0.04ms, 16.6MB)
                테스트 4 〉	통과 (0.08ms, 16.7MB)
                채점 결과
                정확성: 100.0
                합계: 100.0 / 100.0
                '''
                if pos < 1 or pos > self.nodeCount :
                    raise IndexError
                
                # head 제거
                if pos == 1:
                    # 유일한 원소 head + tail 제거  
                    if self.nodeCount == 1:
                        curr = self.tail
                        self.head = None
                        self.tail = None # ⭐️ tail도, head도 None
                    # 여러원소 중 head 제거  
                    else:
                        curr = self.head
                        self.head = curr.next
                        curr.next = None # ⭐️ 잘라낸 curr의 next는 끊겨있으므로 None!
                else : 
                    # tail 제거
                    if pos == self.nodeCount:
                        prev = self.getAt(pos-1)
                        self.tail = prev
                        curr = prev.next
                        prev.next = None  # ⭐️ prev가 꼬리가 되므로 prev.next는 None
                        curr.next = None 
                    # head와 tail사이의 원소 제거
                    else:
                        prev = self.getAt(pos-1)
                        curr = prev.next
                        prev.next = curr.next
                        curr.next = None
                
                self.nodeCount -= 1
                return curr.data 


            def traverse(self):
                result = []
                curr = self.head
                while curr is not None:
                    result.append(curr.data)
                    curr = curr.next
                return result

            def solution(x):
                return 0
    
        return  JsonResponse({"RESULT": []}, status=200)
    
class ProgrammersExample9View(View):
    '''
    (09) dummy head 를 가지는 연결 리스트 노드 삭제
    문제 설명
    제 9 강에서 소개된 추상적 자료구조 LinkedList 는 dummy head node 를 가지는 연결 리스트입니다.
    이 클래스의 아래와 같은 메서드들을, 강의 내용에 소개된 요구조건을 만족시키도록 구현하세요.

    popAfter()
    popAt()
    이 때, popAt() 메서드의 구현에서는 popAfter() 를 호출하여 이용하도록 합니다. 
    (그렇게 하지 않을 수도 있지만, 여기에서는 popAfter() 의 이용에 의해서 코드 구현이 보다 쉬워지는 것을 확인하기 위함입니다.)

    초기 코드로 들어 있는 것은 solution() 함수를 포함하여 다른 부분은 수정하지 말고, 
    def popAfter(self, prev): 와 def popAt(self, pos): 의 메서드 몸체만 구현하세요.

    만약, popAt() 메서드에 인자로 주어진 pos 가 올바른 범위의 값을 가지지 않는 경우에는 
    IndexError exception 을 발생시키도록 합니다. 이렇게 하기 위한 코드는 raise IndexError 입니다.
    '''
    def get (self, request):
        class Node:
            
            def __init__(self, item):
                self.data = item
                self.next = None


        class LinkedList:

            def __init__(self):
                self.nodeCount = 0         # ⭐️ nodeCount는 dumyNode를 제외함.
                self.head = Node(None) 
                self.tail = None           # ⭐️ 노드 삭제시  tail None이어야함. 
                self.head.next = self.tail # ⭐️ head와 tail의 연결관계 생성


            def traverse(self):
                result = []
                curr = self.head
                while curr.next:
                    curr = curr.next
                    result.append(curr.data)
                return result


            def getAt(self, pos):
                if pos < 0 or pos > self.nodeCount:
                    return None

                i = 0
                curr = self.head
                while i < pos:
                    curr = curr.next
                    i += 1

                return curr


            def insertAfter(self, prev, newNode):
                newNode.next = prev.next
                if prev.next is None:
                    self.tail = newNode
                prev.next = newNode
                self.nodeCount += 1
                return True


            def insertAt(self, pos, newNode):
                if pos < 1 or pos > self.nodeCount + 1:
                    return False

                if pos != 1 and pos == self.nodeCount + 1:
                    prev = self.tail
                else:
                    prev = self.getAt(pos - 1)
                return self.insertAfter(prev, newNode)

            
            '''
            테스트 1 〉	통과 (0.06ms, 16.6MB)
            테스트 2 〉	통과 (0.05ms, 16.6MB)
            테스트 3 〉	통과 (0.05ms, 16.8MB)
            테스트 4 〉	통과 (0.06ms, 16.6MB)
            테스트 5 〉	실패 (0.15ms, 16.7MB)
            '''
            # 초기 나의 풀이
            def popAfter_1(self, prev):
                # prev가 끝일때,
                if prev.next is None:
                    return None
                curr = prev.next
                # post가 1일때,
                if prev == self.head:#******
                    prev.next = curr.next
                    if curr.next is None:
                        prev.next = None
                        self.tail = prev
                elif curr.next is None: # pos가 끝일때
                    prev.next = None
                    self.tail = prev
                else:# 중간
                    prev.next = curr.next
                curr.next = None
                self.nodeCount -=1
                return curr.data


            def popAt_1(self, pos):
                if pos < 1 and pos >= self.nodeCount:
                    raise IndexError
                # pos == 1

                if pos == 1:
                    prev = self.head
            # 1<pos<nodeCount
                else:
                    prev = self.getAt(pos-1)
                return self.popAfter(prev)
            
            
            '''
            테스트 1 〉	통과 (0.05ms, 16.6MB)
            테스트 2 〉	통과 (0.07ms, 16.7MB)
            테스트 3 〉	통과 (0.05ms, 16.5MB)
            테스트 4 〉	통과 (0.07ms, 16.6MB)
            테스트 5 〉	통과 (0.05ms, 16.6MB)
            '''
            # 진화된 나의 풀이 - # ⭐️ ⭐️  dummy head 를 가지는 연결 리스트에서는 pos가 끝일 때만 유의하면됨.
            def popAfter_2(self, prev):
                # 빈 리스트 일때, count=0
                if prev.next is None:
                    return None
                curr = prev.next
                    
                if curr.next == None:    # 👈 pos가 끝자리 일때 유의
                    if self.nodeCount == 1:
                        self.tail = None
                    else:
                        self.tail = prev
                prev.next = curr.next
                curr.next = None
                self.nodeCount -=1
                return curr.data


            def popAt_2(self, pos):
                if pos < 1 or pos > self.nodeCount: # ⭐️ or 주의 하기 ,  nodeCount는 dumyNode를 제외
                    raise IndexError
                prev = self.getAt(pos-1)
                return self.popAfter_2(prev)    
            
            def solution(x):
                return 0
    
        return  JsonResponse({"RESULT": []}, status=200)
    
    
    
class ProgrammersExample10_1View(View):
    
    '''
    (10-1) 양방향 연결 리스트 역방향 순회
    문제 설명
    제 10 강에서 소개된 추상적 자료구조 DoublyLinkedList 에 대하여, 또한 강의 내용에서 언급한 reverse() 메서드를 구현하세요.

    이 reverse() 메서드는 양방향 연결 리스트를 끝에서부터 시작해서 맨 앞에 도달할 때까지 (tail 방향에서 head 방향으로) 순회하면서, 
    방문하게 되는 node 에 들어 있는 data item 을 순회 순서에 따라 리스트에 담아 리턴합니다.

    예를 들어, DoublyLinkedList L 에 들어 있는 노드들이 43 -> 85 -> 62 라면, 올바른 리턴 값은 [62, 85, 43] 입니다.

    이 규칙을 적용하면, 빈 연결 리스트에 대한 역방향 순회 결과로 reverse() 메서드라 리턴해야 할 올바른 결과는 [] 입니다.

    '''    
    def get(self,request):
        
        '''
        테스트 1 〉	통과 (0.04ms, 16.6MB)
        테스트 2 〉	통과 (0.04ms, 16.6MB)
        '''
        
        class Node:
            
            def __init__(self, item):
                self.data = item
                self.prev = None
                self.next = None


        class DoublyLinkedList:

            def __init__(self):
                self.nodeCount = 0
                self.head = Node(None)
                self.tail = Node(None)
                self.head.prev = None
                self.head.next = self.tail
                self.tail.prev = self.head
                self.tail.next = None

            # 나의 풀이
            def reverse(self):
                result = []
                
                curr = self.tail
                while curr.prev.prev !=None:            
                    curr = curr.prev
                    result.append(curr.data)
                    
                return result


            def getAt(self, pos):
                if pos < 0 or pos > self.nodeCount:
                    return None

                if pos > self.nodeCount // 2:
                    i = 0
                    curr = self.tail
                    while i < self.nodeCount - pos + 1:
                        curr = curr.prev
                        i += 1
                else:
                    i = 0
                    curr = self.head
                    while i < pos:
                        curr = curr.next
                        i += 1

                return curr


            def insertAfter(self, prev, newNode):
                next = prev.next
                newNode.prev = prev
                newNode.next = next
                prev.next = newNode
                next.prev = newNode
                self.nodeCount += 1
                return True


            def insertAt(self, pos, newNode):
                if pos < 1 or pos > self.nodeCount + 1:
                    return False

                prev = self.getAt(pos - 1)
                return self.insertAfter(prev, newNode)


        def solution(x):
            return 0
        
        return  JsonResponse({"RESULT": self.reverse(self)}, status=200)
    
class ProgrammersExample10_2View(View):
    
    '''
    (10-2) 양방향 연결 리스트 노드 삽입
    문제 설명
    제 10 강에서 소개된 추상적 자료구조 DoublyLinkedList 의 메서드로 insertBefore() 를 구현하세요.

    이 insertBefore() 메서드에는 두 개의 인자가 주어지는데, next 는 어느 node 의 앞에 새로운 node 를 삽입할지를 지정하고, 
    newNode 는 삽입할 새로운 node 입니다.

    강의 내용에서 소개된 insertAfter() 메서드의 구현과 매우 유사하게 할 수 있습니다.
    '''    
    def get(self,request):
        '''
        테스트 1 〉	통과 (0.06ms, 16.8MB)

        '''
        
        class Node:
        
            def __init__(self, item):
                self.data = item
                self.prev = None
                self.next = None

        class DoublyLinkedList:

            def __init__(self):
                self.nodeCount = 0
                self.head = Node(None)
                self.tail = Node(None)
                self.head.prev = None
                self.head.next = self.tail
                self.tail.prev = self.head
                self.tail.next = None

            def traverse(self):
                result = []
                curr = self.head
                while curr.next.next:
                    curr = curr.next
                    result.append(curr.data)
                return result

            #나의 풀이
            def insertBefore(self, next, newNode):
                # if next == self.head:
                #     return False
                prevNode = next.prev
                nextNode = next
                nextNode.prev  = newNode
                prevNode.next = newNode   
                newNode.next  = nextNode
                newNode.prev  = prevNode 
                self.nodeCount +=1
                return True

            def solution(x):
                return 0
        
        return JsonResponse({"RESULT": self.insertBefore(self,1)}, status=200)
        
class ProgrammersExample10_3View(View):
    
    '''
    (10-3) 양방향 연결 리스트 노드 삭제
    문제 설명
    제 10 강에서 소개된 추상적 자료구조 DoublyLinkedList 에 대하여 node 의 삭제 연산에 관련한 아래와 같은 메서드들을 구현하세요.

    popAfter()
    popBefore()
    popAt()
    popAfter(prev) 는 인자 prev 에 의하여 주어진 node 의 다음에 있던 node 를 삭제하고, popBefore(next) 는 인자 next 에 의하여
    주어진 node 의 이전에 있던 node 를 삭제합니다. 그리고 삭제되는 node 에 담겨 있던 data item 을 리턴합니다.

    popAt(pos) 는 인자 pos 에 의하여 지정되는 node 를 삭제하고 그 node 에 담겨 있던 data item 을 리턴하는데,
    위 popAfter() 또는 popBefore() 를 호출하여 이용하는 방식으로 구현하세요. 또한, 만약 인자 pos 가 올바른 범위 내에 있지 않은 경우에는
    raise IndexError 를 이용하여 IndexError exception 을 일으키도록 구현하세요.

    테스트 케이스 1-3 은 각각 (1) popAfter(), (2) popBefore(), (3) popAt() 메서드의 올바른 동작을 검증하는 케이스입니다.

    '''    
    def get(self,request):
        
        '''
        테스트 1 〉	통과 (0.07ms, 16.7MB)
        테스트 2 〉	통과 (0.06ms, 16.6MB)
        테스트 3 〉	통과 (0.07ms, 16.7MB)

        '''
        
        class Node:
    
            def __init__(self, item):
                self.data = item
                self.prev = None
                self.next = None


        class DoublyLinkedList:

            def __init__(self):
                self.nodeCount = 0
                self.head = Node(None)
                self.tail = Node(None)
                self.head.prev = None
                self.head.next = self.tail
                self.tail.prev = self.head
                self.tail.next = None


            def traverse(self):
                result = []
                curr = self.head
                while curr.next.next:
                    curr = curr.next
                    result.append(curr.data)
                return result


            def getAt(self, pos):
                if pos < 0 or pos > self.nodeCount:
                    return None

                if pos > self.nodeCount // 2:
                    i = 0
                    curr = self.tail
                    while i < self.nodeCount - pos + 1:
                        curr = curr.prev
                        i += 1
                else:
                    i = 0
                    curr = self.head
                    while i < pos:
                        curr = curr.next
                        i += 1

                return curr


            def insertAfter(self, prev, newNode):
                next = prev.next
                newNode.prev = prev
                newNode.next = next
                prev.next = newNode
                next.prev = newNode
                self.nodeCount += 1
                return True


            def insertAt(self, pos, newNode):
                if pos < 1 or pos > self.nodeCount + 1:
                    return False

                prev = self.getAt(pos - 1)
                return self.insertAfter(prev, newNode)

            # 나의 풀이
            def popAfter(self, prev):       
                curr = prev.next
                nextN = curr.next
                nextN.prev = prev
                prev.next = nextN
                self.nodeCount -=1        
                return curr.data  

            # 나의 풀이
            def popBefore(self, nextN):      
                curr = nextN.prev
                prev = curr.prev
                prev.next = nextN
                nextN.prev = prev
                self.nodeCount -=1
                return curr.data

            # 나의 풀이
            def popAt(self, pos):
                if pos <1 or pos>self.nodeCount:
                    raise IndexError
                prev = self.getAt(pos-1)
                return self.popAfter(prev)
        
        return  JsonResponse({"RESULT": self.popAt(self,1)}, status=200)
    
    
        
class ProgrammersExample10_4View(View):    
    '''
   (10-4) 양방향 연결 리스트의 병합
    문제 설명
    제 10 강에서 소개된 추상적 자료구조 DoublyLinkedList 에 대하여 두 개의 양방향 연결 리스트를 앞뒤로 이어 붙이는 메서드 concat() 을 구현하세요.

    예를 들어, 양방향 연결 리스트 L1 에는 1 -> 2 -> 3 의 원소가 순서대로 들어 있고, 또다른 양방향 연결 리스트 L2 에는 4 -> 5 의 순서로 원소가 들어 있을 때,
    메서드 호출 L1.concat(L2) 의 결과로 L1 은 1 -> 2 -> 3 -> 4 -> 5 의 양방향 연결 리스트가 됩니다. 물
    론, L1 또는 L2 또는 둘 다가 비어 있는 양방향 연결 리스트인 경우도 고려되도록 코드를 작성해야 합니다.
    '''
    def get(self,request):
        '''
        테스트 1 〉	통과 (0.05ms, 16.7MB)
        테스트 2 〉	통과 (0.07ms, 16.6MB)
        테스트 3 〉	통과 (0.05ms, 16.6MB)
        '''

        class Node:
            
            def __init__(self, item):
                self.data = item
                self.prev = None
                self.next = None


        class DoublyLinkedList:

            def __init__(self):
                self.nodeCount = 0
                self.head = Node(None)
                self.tail = Node(None)
                self.head.prev = None
                self.head.next = self.tail
                self.tail.prev = self.head
                self.tail.next = None

            # 나의 풀이 - 양방향 연결리스트에서는 각각의 리스트가 빈리스트일때를 고려하지 않아도 해결된다.  
            def concat(self, L):
                L1Last = self.tail.prev
                L2First = L.head.next
                L1Last.next = L2First
                L2First.prev = L1Last
                self.tail = L.tail
                L.head = self.head
                self.nodeCount +=L.nodeCount
                return self


            def traverse(self):
                result = []
                curr = self.head
                while curr.next.next:
                    curr = curr.next
                    result.append(curr.data)
                return result

            
            def getAt(self, pos):
                if pos < 0 or pos > self.nodeCount:
                    return None

                if pos > self.nodeCount // 2:
                    i = 0
                    curr = self.tail
                    while i < self.nodeCount - pos + 1:
                        curr = curr.prev
                        i += 1
                else:
                    i = 0
                    curr = self.head
                    while i < pos:
                        curr = curr.next
                        i += 1

                return curr

            def insertAfter(self, prev, newNode):
                next = prev.next
                newNode.prev = prev
                newNode.next = next
                prev.next = newNode
                next.prev = newNode
                self.nodeCount += 1
                return True


            def insertAt(self, pos, newNode):
                if pos < 1 or pos > self.nodeCount + 1:
                    return False

                prev = self.getAt(pos - 1)
                return self.insertAfter(prev, newNode)


        def solution(x):
            return 0
        
        return JsonResponse({"RESULT": self.concat(self,1)}, status=200)
        
        
class ProgrammersExample11View(View):    
    '''
    (11) 수식의 괄호 검사 (스택)
    문제 설명
    소괄호: ( )
    중괄호: /{ /}
    대괄호: [ ]
    를 포함할 수 있는 수식을 표현한 문자열 expr 이 인자로 주어질 때, 이 수식의 괄호가 올바르게 여닫혀 있는지를 판단하는 함수 solution() 을 완성하세요. 이 함수는 수식의 괄호가 유효하면 True 를, 그렇지 않으면 False 를 리턴합니다.

    스택을 활용하여 수식 내의 괄호 여닫음의 유효성을 검사하는 알고리즘에 대해서는 동영상 강의 내용을 참고하세요.
        '''
    def get(self,request):
        '''
        테스트 1 〉	통과 (0.01ms, 10.2MB)
        테스트 2 〉	통과 (0.01ms, 10.2MB)
        테스트 3 〉	통과 (0.01ms, 10.3MB)
        테스트 4 〉	통과 (0.01ms, 10.4MB)
        테스트 5 〉	통과 (0.01ms, 10.2MB)
        테스트 6 〉	통과 (0.01ms, 10.2MB)
        '''
        class ArrayStack:

            def __init__(self):
                self.data = []

            def size(self):
                return len(self.data)

            def isEmpty(self):
                return self.size() == 0

            def push(self, item):
                self.data.append(item)

            def pop(self):
                return self.data.pop()

            def peek(self):
                return self.data[-1]


        def solution(expr):
            match = {
                ')': '(',
                '}': '{',
                ']': '['
            }
            S = ArrayStack()
            for c in expr:
                if c in '({[':
                    S.push(c)

                elif c in match:
                    if S.isEmpty():
                        return False
                    else:
                        t = match[c]

                        if t != S.pop():
                            return False
            return S.isEmpty()
        
        return JsonResponse({"RESULT": solution(self.expr)}, status=200)
    
class ProgrammersExample12View(View):    
    
    '''
        (12) 중위표현 수식 --> 후위표현 수식
    문제 설명
    중위 표기법을 따르는 수식 S 가 인자로 주어질 때, 이 수식을 후위 표기법을 따르는 수식으로 변환하여 반환하는 함수 solution() 을 완성하세요.

    인자로 주어지는 수식 문자열 S 는 영문 대문자 알파벳 한 글자로 이루어지는 변수 A - Z 까지와 4칙연산을 나타내는 연산자 기호 +, -, *, /, 그리고 여는 괄호와 닫는 괄호 (, ) 로 이루어져 있으며 공백 문자는 포함하지 않는 것으로 가정합니다. 또한, 올바르게 구성되지 않은 수식은 인자로 주어지지 않는다고 가정합니다. (수식의 유효성은 검증할 필요가 없습니다.)

    문제에서 미리 주어진, 연산자의 우선순위를 표현한 python dict 인 prec 을 활용할 수 있습니다.

    또한, 스택의 기초 강의에서 이미 구현한, 배열을 이용한 스택의 추상적 자료 구조 코드가 이미 포함되어 있으므로 그대로 이용할 수 있습니다.

    (참고) 테스트 케이스를 보완하여 문제가 2019년 9월 24일에 수정되었습니다.
    (추가 참고) 테스트 케이스를 또 보완하여 문제가 2021년 7월 21일에 수정되었습니다. 추가된 테스트 케이스들은 9번부터 12번까지입니다. 관련하여 질문과 답변 (https://programmers.co.kr/questions/19360) 을 참고할 수 있습니다.
    '''
    def get(self,request):
        class ArrayStack:
    
            def __init__(self):
                self.data = []

            def size(self):
                return len(self.data)

            def isEmpty(self):
                return self.size() == 0

            def push(self, item):
                self.data.append(item)

            def pop(self):
                return self.data.pop()

            def peek(self):
                return self.data[-1]

        prec = {
            '*': 3, '/': 3,
            '+': 2, '-': 2,
            '(': 1
        }

        ## 처음 접근 방식(오답)
        def solution(S):
            opStack = ArrayStack()
            answer = ''
            
            for a in S:
                if a in prec:# 딕셔너리에 있을 때
                    opStack.push(a)
                    opStack.peek()
                elif a == ')': # 닫기 괄호를 만났을 때,
                    while not opStack.isEmpty:
                        b = opStack.pop()
                        if prec[b] > 1:
                            answer+=b
                else:# 피연산자일때
                    answer+=a
            return answer
        
        
        '''
        테스트 1
        입력값 〉	"(A+B)*(C+D)"
        기댓값 〉	"AB+CD+*"
        실행 결과 〉	테스트를 통과하였습니다.
        테스트 2
        입력값 〉	"A*B+C"
        기댓값 〉	"AB*C+"
        실행 결과 〉	테스트를 통과하였습니다.
        테스트 3
        입력값 〉	"A+B*C"
        기댓값 〉	"ABC*+"
        실행 결과 〉	테스트를 통과하였습니다.
        테스트 4
        입력값 〉	"A+B+C"
        기댓값 〉	"AB+C+"
        실행 결과 〉	테스트를 통과하였습니다.
        테스트 5
        입력값 〉	"(A+B)*C"
        기댓값 〉	"AB+C*"
        실행 결과 〉	테스트를 통과하였습니다.
        테스트 6
        입력값 〉	"A*(B+C)"
        기댓값 〉	"ABC+*"
        실행 결과 〉	테스트를 통과하였습니다.
        '''
        ## 나의 풀이
        def solution(S):
            opStack = ArrayStack()
            answer = ''
            
            for a in S:
                if a in prec:# 딕셔너리에 있을 때
                    if opStack.isEmpty():
                        opStack.push(a)
                    elif a == '(':
                        opStack.push(a)
                    elif prec[opStack.peek()] < prec[a]:
                        opStack.push(a)
                    else:
                        while not opStack.isEmpty() and prec[opStack.peek()]>=prec[a]:
                            answer += opStack.pop()
                        opStack.push(a) # 우선순위가 peek보다 낮을 때, stack의 데이터 꺼내고 새로 담아주기
                            
                elif a == ')': # 닫기 괄호를 만났을 때,
                    while not opStack.isEmpty():
                        top = opStack.peek()
                        opStack.pop()
                        if top != '(': 
                            answer+=top
                            
                else:# 피연산자일때
                    answer+=a
                    
            while not opStack.isEmpty():
                answer += opStack.pop()
                
            return answer
        
        # 다른 풀이1
        def solution(S):
            opStack = ArrayStack()
            answer = ''
            #tmp=[]

            for var in S:
                # <prec>에 있을때
                if var in prec:
                    # 비어있을때
                    if opStack.isEmpty():
                        opStack.push(var)
                    # 스택에서 이보다 높거나 같은 우선순위는 pop
                    elif var == '(':
                        opStack.push(var)
                    # 스택에서 이보다 작은 priority를 갖는다면 push
                    elif prec[opStack.peek()] < prec[var]:
                        opStack.push(var)
                    # 스택에서 이보다 큰 priority를 갖는다면 pop
                    else:
                        while not opStack.isEmpty() and prec[opStack.peek()]>=prec[var]:
                            answer += opStack.pop()
                        opStack.push(var)
                # <괄호닫기>일때
                # elif var == ')':
                #     while opStack.peek() != '(':
                #         answer += opStack.pop()
                #     opStack.pop()
                    
                elif var == ')':
                    topToken = opStack.pop()
                    while topToken != '(':
                        answer += topToken
                        topToken = opStack.pop()
                
                # <인수>일때
                else:
                    answer += var
            # 남은 인자 출력        
            while not opStack.isEmpty():
                answer += opStack.pop()
                
                
        # 다른 풀이2
        def solution(S):
            opStack = ArrayStack()
            answer = ''
            for c in S:
                if c not in "*+-/()":
                    answer += c
                if c == "(":
                    opStack.push(c)
                if c == ")":
                    while opStack.peek() != "(":
                        answer += opStack.pop()
                    opStack.pop()
                if c in "*+/-":
                    if opStack.isEmpty():
                        opStack.push(c)
                    else:
                        while prec[opStack.peek()] >= prec[c]:
                            answer += opStack.pop()
                            if opStack.isEmpty():
                                break
                        opStack.push(c)
            while not opStack.isEmpty():
                answer += opStack.pop()
            return answer
        
        return JsonResponse({"RESULT": solution("(A+B)*(C+D)")}, status=200)
    
    
class ArrayStack:
        
        def __init__(self):
            self.data = []

        def size(self):
            return len(self.data)

        def isEmpty(self):
            return self.size() == 0

        def push(self, item):
            self.data.append(item)

        def pop(self):
            return self.data.pop()

        def peek(self):
            return self.data[-1]

class ProgrammersExample13View(View):  
    '''
    # (13) 후위표현 수식 계산

    ### **문제 설명**

    인자로 주어진 문자열 expr 은 소괄호와 사칙연산 기호, 그리고 정수들로만 이루어진 중위 표현 수식입니다. 함수 `solution()` 은 
    이 수식의 값을 계산하여 그 결과를 리턴하도록 작성되어 있습니다. 이 함수는 차례로 `splitTokens()`, `infixToPostfix()`, 
    그리고 `postfixEval()` 함수를 호출하여 이 수식의 값을 계산하는데,

    - `splitTokens()` - 강의 내용에서와 같은 코드로 이미 구현되어 있습니다.
    - `infixToPostfix()` - 지난 강의의 연습문제에서 작성했던 코드를 수정하여, 문자열이 아닌 리스트를 리턴하도록 작성합니다.
    - `postfixEval()` - 이번 강의의 연습문제입니다. 함수의 내용을 완성하세요.

    즉, 두 개의 함수 `infixToPostfix()` 와 `postfixEval()` 을 구현하는 연습입니다. 스택을 이용하기 위하여 `class ArrayStack` 이 정의되어 있으므로 그것을 활용하세요.

    [참고] Python 에는 `eval()` 이라는 built-in 함수가 있어서, 이 함수에 문자열을 인자로 전달하면, 
    그 문자열을 그대로 Python 표현식으로 간주하고 계산한 결과를 리턴하도록 되어 있습니다. 이 built-in 함수 `eval()` 을 이용하면 
    이 연습문제는 전혀 직접 코드를 작성하지 않고도 정답을 낼 수 있을 것이지만, 스택을 이용하여 중위표현식을 계산하는 프로그래밍 연습을 위한 것이니, 
    강의 내용에서 설명한 절차를 수행하도록 코드를 작성해 보세요.
   
    '''
      
    def get(self,request):

        def splitTokens(exprStr):
            tokens = []
            val = 0
            valProcessing = False
            
            # (5+3)*(5-4)
            # ['(', 5, '+', 3, ')' ,*, '(', 5, '-', 4, ')']
            for c in exprStr:
                if c == ' ':
                    continue
                if c in '0123456789':
                    val = val * 10 + int(c)
                    valProcessing = True
                else:
                    if valProcessing:
                        tokens.append(val)
                        val = 0
                    valProcessing = False
                    tokens.append(c) 
            if valProcessing:
                tokens.append(val)

            return tokens


        def infixToPostfix(tokenList):
            prec = {
                '*': 3,
                '/': 3,
                '+': 2,
                '-': 2,
                '(': 1,
            }

            opStack = ArrayStack()
            postfixList = []
            
            for token in tokenList:
                if type(token) is int:# 피연산자가 올 때, 
                    postfixList.append(token)
                elif token == '(': # 여는 괄호가 올때, 
                    opStack.push(token)
                    
                elif token == ')':# 닫는 괄호가 올때, 
                    while not opStack.peek() == '(':
                        postfixList.append(opStack.pop())
                    opStack.pop()
                    
                else:# 연산자가 올 때, 
                    while not opStack.isEmpty():
                        if prec[opStack.peek()] >= prec[token]:
                            postfixList.append(opStack.pop())
                        else : break #*** 반복문 끊어주기
                    opStack.push(token)
                
            while not opStack.isEmpty():
                postfixList.append(opStack.pop())

            return postfixList


        def postfixEval(tokenList):
            valStack = ArrayStack()
            
            for token in tokenList:
                if type(token) is int:
                    valStack.push(token)
                elif token == '*':
                    val1 =valStack.pop()
                    val2 =valStack.pop()
                    valStack.push(val2*val1)
                elif token == '/':
                    val1 =valStack.pop()
                    val2 =valStack.pop()
                    valStack.push(val2/val1)
                elif token == '+':
                    val1 =valStack.pop()
                    val2 =valStack.pop()
                    valStack.push(val2+val1)
                elif token == '-':
                    val1 =valStack.pop()
                    val2 =valStack.pop()
                    valStack.push(val2-val1)
                    
            return valStack.pop()

        def solution(expr):
            tokens = ProgrammersExample13View.splitTokens(expr)
            postfix = ProgrammersExample13View.infixToPostfix(tokens)
            val = ProgrammersExample13View.postfixEval(postfix)
            return val
        
        '''
         테스트 1
        입력값 〉	"5 + 3"
        기댓값 〉	8
        실행 결과 〉	테스트를 통과하였습니다.
        출력 〉	[5, '+', 3]
        테스트 2
        입력값 〉	"(1 + 2) * (3 + 4)"
        기댓값 〉	21
        실행 결과 〉	테스트를 통과하였습니다.
        출력 〉	['(', 1, '+', 2, ')', '*', '(', 3, '+', 4, ')']
        테스트 3
        입력값 〉	"7 * (9 - (3+2))"
        기댓값 〉	28
        실행 결과 〉	테스트를 통과하였습니다.
        출력 〉	[7, '*', '(', 9, '-', '(', 3, '+', 2, ')', ')']
        '''
        return JsonResponse({"RESULT": solution("(5+4)*(6-7)")}, status=200)
    
class ProgrammersExample14View(View):  
        '''
        (14) 양방향 연결 리스트로 구현하는 큐
        문제 설명
        양방향 연결 리스트를 활용하여 큐 (queue) 의 추상적 자료구조 (abstract data structure) 구현을 완성하세요.

        정의하고자 하는 큐의 추상적 자료구조는 class LinkedListQueue 로 구현됩니다. 
        이 문제는 해당 클래스의 메서드들의 구현을 빈칸 채우기 형태로 완성하는 것으로 되어 있으며, 이 클래스의 구현은 L120 부터 시작합니다.

        그 위에는 (LL1-117) 이 추상적 자료구조를 구현하기 위해서 이용할 class DoublyLinkedList 와, 
        또한 여기서 이용하는 class Node 의 구현이 정의되어 있습니다. 이 코드는 이전의 "양방향 연결 리스트" 강의에서 다루어진 것과 완전히 동일합니다.

        정확성 테스트는 class LinkedListQueue 의 각 메서드가 올바르게 구현되어 있는지를 검사합니다. 
        "코드 실행" 을 눌렀을 때 예시 테스트 케이스를 통과하는 것은 아무런 의미가 없습니다.

        '''
        
def get(self,request):
        class Node:

            def __init__(self, item):
                self.data = item
                self.prev = None
                self.next = None


        class DoublyLinkedList:

            def __init__(self):
                self.nodeCount = 0
                self.head = Node(None)
                self.tail = Node(None)
                self.head.prev = None
                self.head.next = self.tail
                self.tail.prev = self.head
                self.tail.next = None


            def __repr__(self):
                if self.nodeCount == 0:
                    return 'LinkedList: empty'

                s = ''
                curr = self.head
                while curr.next.next:
                    curr = curr.next
                    s += repr(curr.data)
                    if curr.next.next is not None:
                        s += ' -> '
                return s


            def getLength(self):
                return self.nodeCount


            def traverse(self):
                result = []
                curr = self.head
                while curr.next.next:
                    curr = curr.next
                    result.append(curr.data)
                return result


            def reverse(self):
                result = []
                curr = self.tail
                while curr.prev.prev:
                    curr = curr.prev
                    result.append(curr.data)
                return result


            def getAt(self, pos):
                if pos < 0 or pos > self.nodeCount:
                    return None

                if pos > self.nodeCount // 2:
                    i = 0
                    curr = self.tail
                    while i < self.nodeCount - pos + 1:
                        curr = curr.prev
                        i += 1
                else:
                    i = 0
                    curr = self.head
                    while i < pos:
                        curr = curr.next
                        i += 1

                return curr


            def insertAfter(self, prev, newNode):
                next = prev.next
                newNode.prev = prev
                newNode.next = next
                prev.next = newNode
                next.prev = newNode
                self.nodeCount += 1
                return True


            def insertAt(self, pos, newNode):
                if pos < 1 or pos > self.nodeCount + 1:
                    return False

                prev = self.getAt(pos - 1)
                return self.insertAfter(prev, newNode)


            def popAfter(self, prev):
                curr = prev.next
                next = curr.next
                prev.next = next
                next.prev = prev
                self.nodeCount -= 1
                return curr.data


            def popAt(self, pos):
                if pos < 1 or pos > self.nodeCount:
                    raise IndexError('Index out of range')

                prev = self.getAt(pos - 1)
                return self.popAfter(prev)


            def concat(self, L):
                self.tail.prev.next = L.head.next
                L.head.next.prev = self.tail.prev
                self.tail = L.tail

                self.nodeCount += L.nodeCount

        # 나의 풀이
        class LinkedListQueue:

            def __init__(self):
                self.data = DoublyLinkedList()

            def size(self):
                return self.data.getLength()

            def isEmpty(self):
                return self.size()==0

            def enqueue(self, item):
                node = Node(item)
                self.data.insertAt(self.size()+1, node)

            def dequeue(self):
                return self.data.popAt(1)

            def peek(self):
                return self.data.getAt(1).data

        def solution(x):
            return 0
        
        '''
        정확성  테스트
        테스트 1 〉	통과 (0.06ms, 16.7MB)
        테스트 2 〉	통과 (0.04ms, 16.7MB)
        테스트 3 〉	통과 (0.06ms, 16.8MB)
        테스트 4 〉	통과 (0.06ms, 16.8MB)
        '''

        return JsonResponse({"RESULT": "Sucess"}, status=200)
    
    
class ProgrammersExample15View(View):  
    def get(self,request):
        '''
        # (15) 환형 큐 구현

        ### **문제 설명**

        Python 의 내장 데이터형인 리스트 (list) 를 이용하여 환형 큐의 추상적 자료 구조를 구현한 클래스 `CircularQueue` 를 완성하세요.

        [참고] 함수 `solution()` 은 이 클래스의 구현과는 관계 없는 것이지만, 문제가 올바르게 동작하는 데 필요해서 넣어 둔 것이니 무시해도 좋습니다. 
        또한, "실행" 을 눌렀을 때 예시 테스트 케이스를 통과한다고 출력되는 것은 아무런 의미가 없습니다.
        '''
        class CircularQueue:
            
            def __init__(self, n):
                self.maxCount = n
                self.data = [None] * n
                self.count = 0
                self.front = -1
                self.rear = -1


            def size(self):
                return self.count

            def isEmpty(self):
                return self.count == 0

            def isFull(self):
                return self.count == self.maxCount
            # 나의 풀이
            def enqueue(self, x):
                if self.isFull():
                    raise IndexError('Queue full')
                self.rear = (self.rear+1)%self.maxCount

                self.data[self.rear] = x
                self.count += 1

            # 나의 풀이
            def dequeue(self):
                if self.size()==0:
                    raise IndexError('Queue empty')
                self.front = (self.front+1)%self.maxCount
                # front는 첫 원소의 바로 앞을 지칭하기 때문에 먼저 자릿수를 한자리 위로 옮긴 다음 x를 출력해낸다.
                x = self.data[self.front]

                self.count -= 1
                return x

            # 나의 풀이
            def peek(self):
                if self.isEmpty():
                    raise IndexError('Queue empty')
                return self.data[(self.front+1)%self.maxCount]
                # front는 첫 원소의 바로 앞을 지칭함.

        CQ = CircularQueue(5)
        
        return JsonResponse({"RESULT": CQ.peek()}, status=200)
    
class ProgrammersExample16View(View):  
    def get(self,request):
        '''
        # (16) 우선순위 큐의 enqueue 연산 구현

        ### **문제 설명**

        앞선 강의에서 소개된 양방향 연결 리스트의 추상적 자료구조 구현인 클래스 `DoublyLinkedList` 를 이용하여 우
        선순위 큐의 추상적 자료구조인 클래스 `PriorityQueue` 의 구현을 완성하세요.

        코드의 윗부분은 양방향 연결 리스트를 이용하기 위한 클래스 `Node` 와 `DoublyLinikedList` 의 구현입니다. 
        그대로 둔 채, 아래에 있는 `class PriorityQueue` 의 메서드들 중 `enqueue()` 메서드의 구현을 위한 
        빈 칸 채우기만 완성하면 됩니다.

        [참고] 함수 `solution()` 은 이 클래스의 구현과는 관계 없는 것이지만, 문제가 올바르게 동작하는 데 필요해서 
        넣어 둔 것이니 무시해도 좋습니다. 또한, 실행 을 눌렀을 때 예시 테스트 케이스를 통과한다고 출력되는 것은 아무런 
        의미가 없습니다.

        '''
        class Node:
    
            def __init__(self, item):
                self.data = item
                self.prev = None
                self.next = None

        class DoublyLinkedList:

            def __init__(self):
                self.nodeCount = 0
                self.head = Node(None)
                self.tail = Node(None)
                self.head.prev = None
                self.head.next = self.tail
                self.tail.prev = self.head
                self.tail.next = None


            def __repr__(self):
                if self.nodeCount == 0:
                    return 'LinkedList: empty'

                s = ''
                curr = self.head
                while curr.next.next:
                    curr = curr.next
                    s += repr(curr.data)
                    if curr.next.next is not None:
                        s += ' -> '
                return s


            def getLength(self):
                return self.nodeCount


            def traverse(self):
                result = []
                curr = self.head
                while curr.next.next:
                    curr = curr.next
                    result.append(curr.data)
                return result


            def reverse(self):
                result = []
                curr = self.tail
                while curr.prev.prev:
                    curr = curr.prev
                    result.append(curr.data)
                return result


            def getAt(self, pos):
                if pos < 0 or pos > self.nodeCount:
                    return None

                if pos > self.nodeCount // 2:
                    i = 0
                    curr = self.tail
                    while i < self.nodeCount - pos + 1:
                        curr = curr.prev
                        i += 1
                else:
                    i = 0
                    curr = self.head
                    while i < pos:
                        curr = curr.next
                        i += 1

                return curr


            def insertAfter(self, prev, newNode):
                next = prev.next
                newNode.prev = prev
                newNode.next = next
                prev.next = newNode
                next.prev = newNode
                self.nodeCount += 1
                return True


            def insertAt(self, pos, newNode):
                if pos < 1 or pos > self.nodeCount + 1:
                    return False

                prev = self.getAt(pos - 1)
                return self.insertAfter(prev, newNode)


            def popAfter(self, prev):
                curr = prev.next
                next = curr.next
                prev.next = next
                next.prev = prev
                self.nodeCount -= 1
                return curr.data


            def popAt(self, pos):
                if pos < 1 or pos > self.nodeCount:
                    return None

                prev = self.getAt(pos - 1)
                return self.popAfter(prev)


            def concat(self, L):
                self.tail.prev.next = L.head.next
                L.head.next.prev = self.tail.prev
                self.tail = L.tail

                self.nodeCount += L.nodeCount


        class PriorityQueue:

            def __init__(self):
                self.queue = DoublyLinkedList()


            def size(self):
                return self.queue.getLength()

            def isEmpty(self):
                return self.size() == 0
            
            # 나의 풀이(빈칸채우기)
            # 주의 할 것, enqueue시 숫자가 낮은 것이 우선이 되도록!!
            def enqueue(self, x):
                newNode = Node(x)
                curr = self.queue.head
                while curr.next.data != None and x < curr.next.data:
                    curr = curr.next
                self.queue.insertAfter(curr, newNode)

            # 주의 할 것, dequeue시 숫자가 낮은 것이 먼저 나오며, 앞이 아니라 뒤에서 나온다!!!!!
            def dequeue(self):
                return self.queue.popAt(self.queue.getLength())

            def peek(self):
                return self.queue.getAt(self.queue.getLength()).data


        def solution(x):
            return 0
        
        PQ = PriorityQueue()
        
        return JsonResponse({"RESULT": PQ.enqueue(2)}, status=200)
    
    
    
    '''
    (18-01) 이진트리의 depth() 연산 구현
    문제 설명
    이미 주어진 코드 (class Node 와 class BinaryTree 에 의하여) 의 구조를 따르는 이진 트리 (binary tree) 에 대하여, 트리의 깊이 (depth) 를 구하는 연산의 구현을 완성하세요.

    초기 코드에 pass 로만 되어 있는 class Node 의 depth() 메서드와 class BinaryTree 의 depth() 메서드를 구현합니다. 코드의 다른 부분은 수정할 필요가 없습니다.

    참고로 할 수 있도록, 강의에서 소개한 size() 메서드들 (class Node 와 class BinaryTree 에 대해서) 을 그대로 두었습니다. 문제로 주어진 depth() 연산도 매우 비슷한 식으로 구현할 수 있으니 참고로 삼으세요.

    [참고] 실행 을 눌렀을 때 통과하는 것은 아무 의미 없습니다.
    또한, solution() 함수는 테스트에 영향을 미치므로 수정하지 말고 그대로 두세요.
    '''
    class Node:
    
        def __init__(self, item):
            self.data = item
            self.left = None
            self.right = None


        def size(self):
            l = self.left.size() if self.left else 0
            r = self.right.size() if self.right else 0
            return l + r + 1


        # 나의 풀이
        def depth(self):
            l = self.left.depth() if self.left else 0
            r = self.right.depth() if self.right else 0
            return (l if l >= r else r) + 1
            


    class BinaryTree:
    
        def __init__(self, r):
            self.root = r

        def size(self):
            if self.root:
                return self.root.size()
            else:
                return 0
        # 나의 풀이
        def depth(self):
            if self.root:
                return self.root.depth()
            else:
                return 0
            
        '''
        테스트 1 〉	통과 (0.05ms, 16.5MB)
        테스트 2 〉	통과 (0.04ms, 16.4MB)
        테스트 3 〉	통과 (0.05ms, 16.6MB)
        테스트 4 〉	통과 (0.04ms, 16.3MB)
        테스트 5 〉	통과 (0.05ms, 16.3MB)    
        '''        
def solution(x):
    return 0


'''
(18-02) 이진트리의 전위순회 연산 구현
문제 설명
이미 주어진 코드 (class Node 와 class BinaryTree 에 의하여) 의 구조를 따르는 이진 트리 (binary tree) 에 대하여, 트리를 전위 순회 (preorder traversal) 하는 연산의 구현을 완성하세요.

초기 코드에 pass 로만 되어 있는 class Node 의 preorder() 메서드와 class BinaryTree 의 preorder() 메서드를 구현합니다. 코드의 다른 부분은 수정할 필요가 없습니다.

참고로 할 수 있도록, 강의에서 소개한 inorder() 메서드들 (class Node 와 class BinaryTree 에 대해서) 을 그대로 두었습니다. 문제로 주어진 preorder() 연산도 매우 비슷한 식으로 구현할 수 있으니 참고로 삼으세요.

[참고] 실행 을 눌렀을 때 통과하는 것은 아무 의미 없습니다.
또한, solution() 함수는 테스트에 영향을 미치므로 수정하지 말고 그대로 두세요.
'''
class Node:
    
    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None


    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self.data)
        if self.right:
            traversal += self.right.inorder()
        return traversal

    # 나의 풀이
    def preorder(self):
        traversal = []
        traversal.append(self.data)
        if self.left:
            traversal += self.left.preorder()
        if self.right:
            traversal += self.right.preorder()
        return traversal
            


class BinaryTree:

    def __init__(self, r):
        self.root = r


    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []

    #나의 풀이
    def preorder(self):
        if self.root:
            return self.root.preorder()
        else:
            return [] 
    '''
    테스트 1 〉	통과 (0.03ms, 16.6MB)
    테스트 2 〉	통과 (0.04ms, 16.6MB)
    테스트 3 〉	통과 (0.04ms, 16.5MB)
    테스트 4 〉	통과 (0.04ms, 16.5MB)
    테스트 5 〉	통과 (0.04ms, 16.5MB)
    '''

def solution(x):
    return 0


'''
(18-03) 이진트리의 후위순회 연산 구현
문제 설명
이미 주어진 코드 (class Node 와 class BinaryTree 에 의하여) 의 구조를 따르는 이진 트리 (binary tree) 에 대하여, 트리를 후위 순회 (postorder traversal) 하는 연산의 구현을 완성하세요.

초기 코드에 pass 로만 되어 있는 class Node 의 postorder() 메서드와 class BinaryTree 의 postorder() 메서드를 구현합니다. 코드의 다른 부분은 수정할 필요가 없습니다.

참고로 할 수 있도록, 강의에서 소개한 inorder() 메서드들 (class Node 와 class BinaryTree 에 대해서) 을 그대로 두었습니다. 문제로 주어진 postorder() 연산도 매우 비슷한 식으로 구현할 수 있으니 참고로 삼으세요.

[참고] 실행 을 눌렀을 때 통과하는 것은 아무 의미 없습니다.
또한, solution() 함수는 테스트에 영향을 미치므로 수정하지 말고 그대로 두세요.
'''
class Node:
    
    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None


    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self.data)
        if self.right:
            traversal += self.right.inorder()
        return traversal


    def postorder(self):
        traversal=[]
        if self.left:
            traversal += self.left.postorder()
        if self.right:
            traversal += self.right.postorder()
        traversal.append(self.data)
        return traversal
            


class BinaryTree:

    def __init__(self, r):
        self.root = r


    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []


    def postorder(self):
        if self.root:
            return self.root.postorder()
        else:
            return []
        '''
        테스트 1 〉	통과 (0.08ms, 16.6MB)
        테스트 2 〉	통과 (0.05ms, 16.6MB)
        테스트 3 〉	통과 (0.05ms, 16.8MB)
        테스트 4 〉	통과 (0.04ms, 16.6MB)
        테스트 5 〉	통과 (0.06ms, 16.6MB)
        '''
def solution(x):
    return 0


'''
(19) 이진 트리의 넓이 우선 순회
문제 설명
이진 트리를 구현한 클래스인 class BinaryTree 에 대하여 넓이 우선 순회 (breadth first traversal) 를 구현하는 메서드 bft() 를 완성하세요.

class ArrayQueue 는 배열 (python list) 을 이용하여 구현한 큐 (queue) 의 추상적 자료구조입니다. 이것을 이용하여 넓이 우선 순회 알고리즘을 구현하세요.

[참고 1] solution() 함수의 구현은 그대로 두세요. 이것을 없애면 테스트가 되지 않습니다.

[참고 2] "코드 실행" 을 눌렀을 때 통과하는 것은 아무런 의미가 없습니다.
'''
class ArrayQueue:
    
    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def isEmpty(self):
        return self.size() == 0

    def enqueue(self, item):
        self.data.append(item)

    def dequeue(self):
        return self.data.pop(0)

    def peek(self):
        return self.data[0]


class Node:

    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None


class BinaryTree:

    def __init__(self, r):
        self.root = r

    #나의 풀이
    def bft(self):
        if self.root:
            traversal =[]
            q = ArrayQueue()
            q.enqueue(self.root)
            while not q.isEmpty():
                a = q.dequeue()
                traversal.append(a.data)
                if a.left:
                    q.enqueue(a.left)
                if a.right:
                    q.enqueue(a.right)
            return traversal
        else:    
            return []
        
        '''
        테스트 1 〉	통과 (0.04ms, 16.6MB)
        테스트 2 〉	통과 (0.04ms, 16.5MB)
        테스트 3 〉	통과 (0.04ms, 16.5MB)
        테스트 4 〉	통과 (0.04ms, 16.5MB)
        테스트 5 〉	통과 (0.04ms, 16.8MB)
        '''

def solution(x):
    return 0



'''
(20) 이진 탐색 트리의 원소 삽입 연산 구현
문제 설명
초기 코드에 주어진 class Node 와 class BinSearchTree 를 기반으로, 이진 탐색 트리 (binary search tree) 에 새로운 원소를 삽입하는 insert(key, data) 연산의 구현을 완성하세요.

class BinSearchTree 에는 이미 insert(key, data) 메서드가 구현되어 있습니다. 이것을 그대로 이용하고, class Node 의 insert(key, data) 메서드를 재귀적 방법으로 구현하세요. 강의에서 언급한 바와 같이, 이미 트리 안에 들어 있는 것과 같은 (중복된) 키를 이용하여 삽입을 시도하는 경우에는 KeyError 예외를 발생시켜야 합니다.

[참고 1] inorder() 메서드의 구현은 그대로 두세요. 테스트에 이용됩니다.

[참고 2] solution() 함수의 구현도 그대로 두세요. 이것을 없애면 테스트가 되지 않습니다.

[참고 3] "코드 실행" 을 눌렀을 때 통과하는 것은 아무런 의미가 없습니다.
'''
class Node:
    
    def __init__(self, key, data):
        self.key = key
        self.data = data
        self.left = None
        self.right = None

    # 나의 풀이
    def insert(self, key, data):
        if key < self.key:
            if self.left:
                self.left.insert(key,data)
            else:
                self.left = Node(key,data)
        
        elif key > self.key:
            if self.right:
                self.right.insert(key,data)
            else: 
                self.right = Node(key,data)       
        else:
            raise KeyError("")

    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self)
        if self.right:
            traversal += self.right.inorder()
        return traversal


class BinSearchTree:

    def __init__(self):
        self.root = None


    def insert(self, key, data):
        if self.root:
            self.root.insert(key, data)
        else:
            self.root = Node(key, data)


    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []


def solution(x):
    return 0



'''
(21) 이진 탐색 트리에서 노드의 삭제 연산 구현
문제 설명
초기 코드에 주어진 class Node 와 class BinSearchTree 를 기반으로, 이진 탐색 트리 (binary search tree) 에서 지정된 원소를 삭제하는 remove(key) 연산의 구현을 완성하세요.

class Node 와 class BinSearchTree 에 이미 구현되어 있는 코드는 수정하지 마세요. 코드 구현의 정확성 평가에 이용됩니다. 초기 코드에 들어 있는 주석을 참고로 하여, BinSearchTree::remove() 메서드의 안에 들어 있는 pass 를 없애고 그 자리에 올바른 코드를 써 넣으면 됩니다.

[참고 1] solution() 함수의 구현은 그대로 두세요. 이것을 없애면 테스트가 되지 않습니다.

[참고 2] "코드 실행" 을 눌렀을 때 통과하는 것은 아무런 의미가 없습니다.

[참고 3] 잘 생각해 보면, 이진 탐색 트리를 구현하지 않고 키 순서대로 정렬된 Python 의 배열을 유지함으로써도 같은 연산을 구현할 수 있습니다. 
        이 연습문제에서는 효율성 테스트를 하지 않기 때문에 이러한 구현을 오답으로 간주하지 않습니다만, 배열을 이용한 구현과 트리 구조를 이용한 구현은 연산의 복잡도에 큰 차이가 있습니다. 
        이진 탐색 트리로 구현하여 코드 작성 연습을 하시기 바랍니다.
'''

class Node:
    
    def __init__(self, key, data):
        self.key = key
        self.data = data
        self.left = None
        self.right = None


    def insert(self, key, data):
        if key < self.key:
            if self.left:
                self.left.insert(key, data)
            else:
                self.left = Node(key, data)
        elif key > self.key:
            if self.right:
                self.right.insert(key, data)
            else:
                self.right = Node(key, data)
        else:
            raise KeyError('Key %s already exists.' % key)


    def lookup(self, key, parent=None):
        if key < self.key:
            if self.left:
                return self.left.lookup(key, self)
            else:
                return None, None
        elif key > self.key:
            if self.right:
                return self.right.lookup(key, self)
            else:
                return None, None
        else:
            return self, parent


    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self)
        if self.right:
            traversal += self.right.inorder()
        return traversal


    def countChildren(self):
        count = 0
        if self.left:
            count += 1
        if self.right:
            count += 1
        return count


class BinSearchTree:

    def __init__(self):
        self.root = None


    def insert(self, key, data):
        if self.root:
            self.root.insert(key, data)
        else:
            self.root = Node(key, data)


    def lookup(self, key):
        if self.root:
            return self.root.lookup(key)
        else:
            return None, None


    def remove(self, key):
        node, parent = self.lookup(key)
        if node:
            nChildren = node.countChildren()
            # The simplest case of no children
            if nChildren == 0:
                # 만약 parent 가 있으면
                if parent:
                    if parent.left.key == node.key:
                        parent.left = None
                    else:
                        parent.right = None
                # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
                # parent.left 또는 parent.right 를 None 으로 하여
                # leaf node 였던 자식을 트리에서 끊어내어 없앱니다.
                
                # 만약 parent 가 없으면 (node 는 root 인 경우)
                # self.root 를 None 으로 하여 빈 트리로 만듭니다.
                else:
                    self.root = None
            # When the node has only one child
            elif nChildren == 1:
                # 하나 있는 자식이 왼쪽인지 오른쪽인지를 판단하여
                # 그 자식을 어떤 변수가 가리키도록 합니다.
                if node.left:
                    s = node.left
                else:
                    s = node.right
                # 만약 parent 가 있으면
                # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
                # 위에서 가리킨 자식을 대신 node 의 자리에 넣습니다.
                if parent:
                    if parent.left.key == node.key:
                        parent.left = s
                        s = None
                    else:
                        parent.right = s
                        s = None
                # 만약 parent 가 없으면 (node 는 root 인 경우)
                # self.root 에 위에서 가리킨 자식을 대신 넣습니다.
                else:
                    self.root = s
            # When the node has both left and right children
            else:
                # 1차 풀이(오답)
                parent = node.right
                s = parent.left
                while s.left:
                    parent = s
                    s = s.left
                node.key = s.key
                node.data = s.data
                if s.right:
                    parent.left = s.right
                if s.countChilde() == 0:
                    parent.left = None
                    
                '''
                테스트 1 〉	통과 (0.07ms, 16.8MB)
                테스트 2 〉	통과 (0.04ms, 16.7MB)
                테스트 3 〉	통과 (0.07ms, 16.7MB)
                테스트 4 〉	통과 (0.06ms, 16.7MB)
                테스트 5 〉	실패 (런타임 에러)
                테스트 6 〉	실패 (런타임 에러)
                테스트 7 〉	통과 (0.06ms, 16.9MB)
                테스트 8 〉	실패 (런타임 에러)
                테스트 9 〉	실패 (런타임 에러)
                '''
                    
                    
                # 2차 풀이(정답)
                s = node.right
                parent = node
                while s.left:
                    parent = s
                    s = parent.left
                    
                node.key = s.key
                node.data = s.data
                
                if parent.right == s: # node 가 곧 parent인 경우, s의 child가 left 가 없는 경우  
                    parent.right = s.right                   
                if parent.left == s:
                    parent.left = s.right
                    
                '''
                테스트 1 〉	통과 (0.13ms, 16.8MB)
                테스트 2 〉	통과 (0.04ms, 16.7MB)
                테스트 3 〉	통과 (0.07ms, 16.7MB)
                테스트 4 〉	통과 (0.06ms, 16.8MB)
                테스트 5 〉	통과 (0.06ms, 16.8MB)
                테스트 6 〉	통과 (0.06ms, 16.7MB)
                테스트 7 〉	통과 (0.06ms, 16.8MB)
                테스트 8 〉	통과 (0.06ms, 16.7MB)
                테스트 9 〉	통과 (0.07ms, 16.7MB)
                '''

            return True

        else:
            return False


    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []


def solution(x):
    return 0



'''
(22) 최대 힙에 새로운 원소 삽입
문제 설명
초기 코드에 주어진 class MaxHeap 에 최대 힙에 새로운 원소를 추가하는 연산인 insert() 메서드의 구현을 완성하세요.

[참고 1] solution() 함수의 구현은 그대로 두세요. 이것을 없애면 테스트가 되지 않습니다.

[참고 2] "코드 실행" 을 눌렀을 때 통과하는 것은 아무런 의미가 없습니다.
'''
class MaxHeap:
    
    def __init__(self):
        self.data = [None]


    def insert(self, item):
        # 나의 풀이
        a = self.data
        a.append(item)
        itemIndex       = a.index(item)
        
        while itemIndex != 1:
            parentIndex     = itemIndex // 2
            if a[itemIndex] > a[parentIndex]:
                a[itemIndex], a[parentIndex] = a[parentIndex], a[itemIndex]
                itemIndex, parentIndex = itemIndex, parentIndex 
                itemIndex     = itemIndex // 2
            else:
                break
            
            '''
            테스트 1 〉	통과 (0.06ms, 16.5MB)
            '''
     
        # 다른 풀이        
        self.data.append(item)
        i = len(self.data) - 1
        while i != 1:
            if self.data[i] > self.data[(i // 2)]:
                self.data[i], self.data[(i // 2)] = self.data[(i // 2)], self.data[i]
                i = i // 2
            else:
                break

def solution(x):
    return 0



'''
(23) 최대 힙에서의 원소 삭제
문제 설명
초기 코드에 여기 저기 포함된 빈 칸을 채움으로써 class MaxHeap 의 메서드인 maxHeapify() 의 구현을 완성하세요. 이것은 이미 주어져 있는 remove() 메서드와 연결되어 최대 힙에서의 원소 삭제 연산을 구성합니다.

[참고 1] remove() 메서드의 내용은 이미 주어져 있으므로 수정하지 않는 쪽이 좋습니다.

[참고 2] solution() 함수의 구현은 그대로 두세요. 이것을 없애면 테스트가 되지 않습니다.

[참고 3] "코드 실행" 을 눌렀을 때 통과하는 것은 아무런 의미가 없습니다.
'''
class MaxHeap:

    def __init__(self):
        self.data = [None]


    def remove(self):
        if len(self.data) > 1:
            self.data[1], self.data[-1] = self.data[-1], self.data[1]
            data = self.data.pop(-1)
            self.maxHeapify(1)
        else:
            data = None
        return data

    # 나의 풀이
    def maxHeapify(self, i):
        # 왼쪽 자식 (left child) 의 인덱스를 계산합니다.
        left = 2*i

        # 오른쪽 자식 (right child) 의 인덱스를 계산합니다.
        right = 2*i +1

        smallest = i
        # 왼쪽 자식이 존재하는지, 그리고 왼쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if left < len(self.data) and self.data[left] > self.data[i]:
            # 조건이 만족하는 경우, smallest 는 왼쪽 자식의 인덱스를 가집니다.
            
            smallest = left

        # 오른쪽 자식이 존재하는지, 그리고 오른쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if right < len(self.data) and self.data[right] > self.data[smallest]: 
            #### ⭐️⭐️ i, right, left 셋 중 최대값(smallest)을 찾는 것인데 처음에 self.data[right] > self.data[i]로 작성했다가 엄청 해맸다...
            ## 출제자 분이 최대값의 변수 명을 great가 아닌 smallest로 지정해놓으셔서 더 헷갈린 것도 있었던 것 같다. 
                        
            # 조건이 만족하는 경우, smallest 는 오른쪽 자식의 인덱스를 가집니다.
            smallest = right

        if smallest != i:
            # 현재 노드 (인덱스 i) 와 최댓값 노드 (왼쪽 아니면 오른쪽 자식) 를 교체합니다.
            self.data[i], self.data[smallest] = self.data[smallest], self.data[i]

            # 재귀적 호출을 이용하여 최대 힙의 성질을 만족할 때까지 트리를 정리합니다.
            self.maxHeapify(smallest)
            
    '''
    테스트 1 〉	통과 (0.06ms, 16.8MB)
    '''


def solution(x):
    return 0
# import requests [ 값 교환 ]         =======================         a, b = 10, 20         a, b = b, a         print(a, b)         => 결과 : 20, 10                  [ 출력 ]          =======================         print("number : ", a, b, c)         => number : 1, 2, 3                  print(i, sep=', ')         => 1, 2, 3                  print(i, sep='')         => 123                  print(i, sep='\n')         =>         1         2         3                  print(i, end=' ')         => 결과 : 1 2 3 6 7 14 21 42                  =======================                      [ 반복문 ]                  @ For         =======================         1) i 증가             for i in range(10):                 print(i)                          => 결과 : 0~9                      2) i 감소             for i in range(10, 0, -2):                 print(i)             => 결과 : 10, 8, 6, 4, 2              2) 특정 조건에 해당하면 다시 반복문 처음으로 돌아가게하기             for i in range(10):                 if i%2 == 0:                     continue                 print(i) # 홀수만 출력됨                 i=i+1                                               3) 특정 상황에서 반복문 멈추게 하기             ** for ~, else~ 구문 : for 문에서 break가 걸리면, 실행되지 않는다. break가 걸리지 않을 때만 실행된다.                               for i in range(1,11):                     print(i)                     if i>15:                         break                 else:                     print(11)                                                    @ While : 조건이 들어간다. i<=10이 참일 때, 반복문 중지         =======================         1) i 증가             i=1             while i<=10:                 print(i)                 i=i+1                      2) i 감소                  i=10             while i>=1:                 print(i)                 i=i-1                      3) 무한반복을 멈추게 하거나, 특정 상황에서 반복문 멈추게 하기             i=1             while True:                 print(i)                 if i == 4:                     break                 i=i+1                               4) 특정 조건에 해당하면 다시 반복문 처음으로 돌아가게하기             ** 주의 while문에서 적용할 때는 i의 증감 연산자가 continue보다 먼저 오지 않으면, 반복문이 계속 돌게된다.              i = 1             while i<10:                 i=i+1                 if i % 2 == 0:                     continue                 print(i)                          => 결과 : 3, 5, 7, 9                                            [ 반복문을 이용한 문제풀이 ]         ==========================         1) 1부터 N까지 홀수 출력하기             input() :  값을 입력 받는다. ** 타입은 문자가 되므로 연산을 하고싶다면, int형으로 바꿔주어야함.                          n=int(input())              for i in range(1, n+1):                 if i%2==1:                     print(i)                          2) 1부터 N까지의 합 구하기                      sum=0             n=int(input())              for i in range(1, n+1):                 sum=sum+i             print(sum)                  3) N의 약수 출력하기// 약수 : 1 부터 나 자신의 수까지, 나 자신과 나눠서 0이 되는 어떤 수 .                  n=int(input())          for i in range(1,n+1):             if n%i==0:                 print(i, end=' ')         => 1 2 3 6 7 14 21 42                                   [ 중첩 반복묵(2중 for 문) ]         ============================         for i in range(5):             for j in range(5):                 print('*', end=' ')             print()                                                                                                  * * * * *         * * * * *         * * * * *         * * * * *         * * * * *                  for i in range(5):             for j in range(i+1):                 print('*', end=' ')             print()                                      *         * *         * * *         * * * *         * * * * *                  for i in range(5):             for j in range(5-i):                 print('*', end=' ')             print()                              * * * * *         * * * *         * * *         * *         *                                 [ 문자열과 내장함수 ]         ================================                     1) upper()  : 문자열 모두 대문자 전환              msg = "It is Time"             print(msg.upper())                   => IT IS TIME            2) lower()  :  문자열 모두 소문자 전환             msg = "It is Time"             print(msg.lower())                => it is time            3) find('T') : 처음 발견되는 T의 인덱스 번호             msg = "It is Time"             print(msg.find('T'))               => 6          4) count('T') : T의 갯수             msg = "It is Time"             print(msg.count('T'))               => 1         5) [:2] : 0~1인덱스까지의 문자열 추출             msg = "It is Time"             print(msg[:2])               => It         6) [3:5] : 3~4덱스까지의 문자열 추출             msg = "It is Time"             print(msg[3:5])               => is         7) len(msg) : 문자열의 길이(공백 포함)                 msg = "It is Time"             for i in range(len(msg)):                 print(i, end=' ')             => 0 1 2 3 4 5 6 7 8 9         9) 문자열 리스트의 문자 하나하나 반환                  (방법1)             msg = "It is Time"             for i in range(len(msg)):                 print(msg[i], end=' ')             print()             =>I t   i s   T i m e                  (방법2)             msg = "It is Time"             for x in msg:                 print(x, end=' ')             print()             =>I t   i s   T i m e                  10) isupper() : 대문자면 true // 대문자만 출력             msg = "It is Time"             for x in msg:                 if x.isupper():                     print(x, end=' ')                 =>I T                  11) islower() : 소문자면 true // 소문자만 출력             msg = "It is Time"             for x in msg:                 if x.islower():                     print(x, end=' ')                 =>t i s i m e                      11) isalpha() : 공백은 X, 오직 알파벳일 때만         msg = "It is Time"         for x in msg:             if x.isalpha():                 print(x, end='')             =>ItisTime                  12)  ord() : 아스키 넘버 출력(A ~ Z : 65 ~ 90, a ~ z : 97~122)                  tmp='AZ'         for x in tmp:             print(ord(x))                      tmp='az'         for x in tmp:             print(ord(x))                               13)  chr() : 아스키 넘버에 대응되는 문자 출력(A ~ Z : 65 ~ 90, a ~ z : 97~122)         tmp=65         print(chr(tmp))                           [리스트와 내장함수]         ======================         - 리스트 : 변수 하나하나를 나열하여 인덱스를 붙인 것. a1,a2,a3.. =>a[0], a[1], a[2]         1) 빈리스트 만들기                 a = []                 print(a)                 b=list()                 print(b)                        =>[], []                            2) 값이 있는 리스트 만들기              (1) a = [1,2,3,4,5]                          (2) b = list(range(1,11))                          (3) c=a+b                           3) a.append(6) # 리스트 멘 마지막에 값 6을 추가             print(a)                  4) a.insert(3,7)# 3번 인덱스에 7을 추가, 나머지는 뒤로 밀림             print(a)                  5) a.pop() # 리스트에서 마지막 값을 제거             print(a)                  6) a.pop(3) # 3번 인덱스의 값을 제거             print(a)                  7) a.remove(4) # 리스트에서 값 4 를 제거, 앞으로 당겨짐             print(a)                  8) a.index(5) # 5라는 값이 몇번 인덱스에 있는지             print(a.index(5))                          a=list(range(1,11))                  9) print(sum(a)) # 1~10의 모든 수의 합                  10) print(max(a)) # 최대값                  11) print(min(a)) # 최소값              print(min(7,5)) # 인자들 중 최소값                    print(min(7,3,5)) # 인자들 중 최소값                    print(max(7,5)) # 인자들 중 최대값                      12) 무작위로 섞기                      import random as r                          r.shuffle(a) # 무작위로 섞기             print(a)                     13) a.sort() #오름차순             print(a)                     14) a.sort(reverse=True) # 내림차순             print(a)             15) a.clear() # 빈리스트로 만들기             print(a)                                  리스트와 내장함수(2)         ========================         a=[23, 12, 36, 53, 19]         print(a[:3])         print(a[1:4])                  1.  리스트 값 출력         =====================         방법 1)             for i in range(len(a)):                 print(a[i], end=' ')             print()             =>23 12 36 53 19                      for x in a:                 print(x, end=' ')             print()             =>23 12 36 53 19                  방법 2)             for x in a:                 if x%2==1:                     print(x, end=' ')             print()                  방법 3) enumerate()             for x in enumerate(a):#(인덱스, value)의 형태로 튜플 반환                 print(x)             =>  (0, 23)                 (1, 12)                 (2, 36)                 (3, 53)                 (4, 19)                      ** 튜플의 구조는 리스트와 같으나, 값을 변경할 수 없다.                 a = [23, 12, 36, 53, 19]                 a[0] = 43                 print(a)                 =>[43, 12, 36, 53, 19]                                  a = (23, 12, 36, 53, 19)                 a[0] = 43                 =>TypeError: 'tuple' object does not support item assignment                      방법 4) x[0], x[1]             for x in enumerate(a):                 print(x[0], x[1]) # x=(인덱스, value)이므로 x[0]은 인덱스 , x[1]은 값              =>             0 23             1 12             2 36             3 53             4 19                  방법 5) 가장 많이 쓰는 enumerate 사용             for index, value in enumerate(a):                 print(index, value)             print()             =>             0 23             1 12             2 36             3 53             4 19                  방법 6) 가장 많이 쓰는 enumerate 사용             if all(60>x for x in a): # 모두 충족하면 참                 print("YES")             else:                 print("NO")              if any(15>x for x in a): # 한가지라도 충족하면 참                 print("YES")             else:                    # 모두가 충족안할때, 거짓                 print("NO")                                        [2차원 리스트 생성과 접근]         =========================         a = [0] * 10 # 인덱스 번호가 0~9까지인 크기가 10인 일차원 리스트             a = [0] * 3 # 인덱스 번호가 0~2까지인 크기가 3인 일차원 리스트                  1)  for _ in range(3) // _를 하면 변수없이 반복문이 3번 돈다.             a=[[0]*3 for _ in range(3)] # [0]*3 가 3번 반복됨.                 print(a)             =>[[0, 0, 0], [0, 0, 0], [0, 0, 0]]             열                    행    0  1  2             0 [0, 0, 0]             1 [0, 0, 0]             2 [0, 0, 0]                          열                    행    0  1  2             0 [0, 1, 0]             1 [0, 2, 0]             2 [0, 0, 0]                          a=[[0]*3 for _ in range(3)] # [0]*3 가 3번 반복됨.                 a[0][1]=1             a[1][1]=2             print(a)             =>[[0, 1, 0], [0, 2, 0], [0, 0, 0]]                               2) 2차원 리스트 표로 출력하기             for x in a:                 print(x)             =>             [0, 1, 0]             [0, 2, 0]             [0, 0, 0]                               3) 대괄호없이 2차원 리스트 출력하기             a=[[0]*3 for _ in range(3)] # [0]*3 가 3번 반복됨.                 for x in a:                 for y in x:                     print(y, end=' ')                 print()             =>             0 0 0                0 0 0             0 0 0                                            [함수 만들기]         =================         # 함수는 값을 return 하며, 함수를 종료 한다.             def add(a,b):                 c=a+b                 return c             print(add(3,2))             =>5         # 파이썬에서는 2개이상의 값을 튜플로 반환할 수 있다.             def add(a,b):                 c=a+b                 d=a-b                 return c, d             print(add(3,2))             =>(5, 1)                  # 소수(나누어 떨어지지 않는 수 )만 출력하는 함수 만들기(1~자기자신까지의 수중 1,과 자기자신을 제외하고 나누어서 떨어지지 않는 수)             def isPrime(x):                 for i in range(2,x):                     if x%i==0:                         return False # 여기서 함수가 종료됨.                 return True           a=[12, 13, 7, 9, 19]         for y in a:             if isPrime(y):                 print(y, end=' ')                                        [람다함수]         ====================         - 람다함수 : 익명의 함수 또는 표현식                  def plus_one(x):             return x+1         print(plus_one(1))         =>2                  # 람다함수(익명의 함수)로 표현하기(변수에 담아서 호출해주어야함)         plus_two=lambda x: x+2         print(plus_two(1))         =>3                           * map(함수, 함수를 적용할 자료)             a=[1,2,3]             print(list(map(plus_one, a)))             =>[2, 3, 4]                  * 함수 이름이 필요없이 익명의 함수를 사용하여 바로 사용할수있음.             print(list(map(lambda x: x+1, a)))              =>[2, 3, 4]                               [선형 탐색, x의 위치 찾기]         ====================             L = [3,8,2,7,6,10,9]             x = 6             def linear_search(S, x):                 i=0                 while i<len(L) and L[i] != x:                     i+=1                 if i < len(L):                     return i                 else:                     return -1                                  def linear_search(S, x):                 return S.index(x)                           [재귀 알고리즘]         ===============          1) 잘못된 예시 -  종결 조건이 없음                def sum1(n):                 print(n)                 return n + sum1(n -1) # 자신을 재귀호출하고있음.             # a = int (input("Number:"))             # print(sum(a))             Number:30             30             29             28             27             26             25             24             23             22             21             -995..             ..... 에러가 남....                          def sum2(n):                 print(n)                 if n<= 1:                     return n                 else:                     return n+ sum2(n-1)             n=10일때 콘솔에 찍히는 결과              10             9             8             7             6             5             4             3             2             1                          sum2(10) = 55             a = int(input("Number:"))             print(sum2(a)) # 2. 선형 배열 알고리즘 풀이 (02) 정렬된 리스트에 원소 삽입         리스트 L 과 정수 x 가 인자로 주어질 때, 리스트 내의 올바른 위치에 x 를 삽입하여 그 결과 리스트를 반환하는 함수 solution 을 완성하세요.          인자로 주어지는 리스트 L 은 정수 원소들로 이루어져 있으며 크기에 따라 (오름차순으로) 정렬되어 있다고 가정합니다.          예를 들어, L = [20, 37, 58, 72, 91] 이고 x = 65 인 경우, 올바른 리턴 값은 [20, 37, 58, 65, 72, 91] 입니다.          힌트: 순환문을 이용하여 올바른 위치를 결정하고 insert() 메서드를 이용하여 삽입하는 것이 한 가지 방법입니다.          주의: 리스트 내에 존재하는 모든 원소들보다 작거나 모든 원소들보다 큰 정수가 주어지는 경우에 대해서도 올바르게 처리해야 합니다. # 풀이 실패 -> 시간 초과 및 반복문 멈추는 것 고려하지 않음 # 풀이 실패 -> enumerate를 사용하였으나, 역시 시간 초과 및 반복문을 멈추는 것을 고려하지 않음. # PASS!!! # 반복문이 계속 도는 것이 문제였으며, 이로인해 시간이 초과되는 것을 깨달음. 이를 잡아주니 풀이 성공!!!!! # 나와 비슷한 풀이 # L[-1]은 리스트 맨 끝에 있는 수를 지칭 한다!!, 맨 끝자리이면서, x가 값이 크다는 것을 모두 충족함. # 오름차순이라는 문제의 함정을 이용한 문제 풀이 문제 설명         인자로 주어지는 리스트 L 내에서, 또한 인자로 주어지는 원소 x 가 발견되는 모든 인덱스를 구하여          이 인덱스들로 이루어진 리스트를 반환하는 함수 solution 을 완성하세요.          리스트 L 은 정수들로 이루어져 있고 그 순서는 임의로 부여되어 있다고 가정하며, 동일한 원소가 반복하여 들어 있을 수 있습니다.          이 안에 정수 x 가 존재하면 그것들을 모두 발견하여 해당 인덱스들을 리스트로 만들어 반환하고,          만약 존재하지 않으면 하나의 원소로 이루어진 리스트 [-1] 를 반환하는 함수를 완성하세요.          예를 들어, L = [64, 72, 83, 72, 54] 이고 x = 72 인 경우의 올바른 리턴 값은 [1, 3] 입니다.         또 다른 예를 들어, L = [64, 72, 83, 72, 54] 이고 x = 83 인 경우의 올바른 리턴 값은 [2] 입니다.         마지막으로 또 다른 예를 들어, L = [64, 72, 83, 72, 54] 이고 x = 49 인 경우의 올바른 리턴 값은 [-1] 입니다.          힌트 1: 리스트의 index() 메서드와 리스트 슬라이싱을 활용하는 것이 한 가지 방법이 됩니다. 리스트 슬라이싱은 아래와 같이 동작합니다.          L = [6, 2, 8, 7, 3] 인 경우         L[1:3] = [2, 8]         L[2:] = [8, 7, 3]         L[:3] = [6, 2, 8]          힌트 2: 리스트의 index() 메서드는, 인자로 주어지는 원소가 리스트 내에 존재하지 않을 때 ValueError 를 일으킵니다.          이것을 try ... except 로 처리해도 되고, "if x in L" 과 같은 조건문으로 특정 원소가 리스트 내에 존재하는지를 판단해도 됩니다. # 나의 풀이 ) PASS!! # 다른 풀이 : 리스트 컴프리헨션으로 깔끔하게! # 조건문이 만족 할 떄, i를 리스트에 담는다. # 3. 정렬, 탐색 알고리즘 풀이 (03) 이진탐색                  문제 설명         리스트 L 과, 그 안에서 찾으려 하는 원소 x 가 인자로 주어질 때,          x 와 같은 값을 가지는 원소의 인덱스를 리턴하는 함수 solution() 을 완성하세요.          만약 리스트 L 안에 x 와 같은 값을 가지는 원소가 존재하지 않는 경우에는 -1 을 리턴합니다.          리스트 L 은 자연수 원소들로 이루어져 있으며, 크기 순으로 정렬되어 있다고 가정합니다.          또한, 동일한 원소는 두 번 이상 나타나지 않습니다.          예를 들어,         L = [2, 3, 5, 6, 9, 11, 15]         x = 6         의 인자들이 주어지면, L[3] == 6 이므로 3 을 리턴해야 합니다.          또 다른 예로,         L = [2, 5, 7, 9, 11]         x = 4         로 주어지면, 리스트 L 내에 4 의 원소가 존재하지 않으므로 -1 을 리턴해야 합니다.          이 연습문제에서는 알고리즘의 효율성도 평가합니다. 만약 순차 (선형) 탐색 알고리즘을 구현하는 경우에는         제한 시간 요구사항을 만족하지 못하여 효율성 테스트 케이스들을 통과하지 못할 수도 있습니다. #L = [] #x = 20 # 뭔가 이 과정에서 시간을 많이 잡아 먹는 다는 생각이 들었고, 최종 lower와 upper 만을 사용하여 , tmp 리스트를 구하면 될것같았다. #L=L[lower:upper+1] # L를 슬라이싱 해버리면, 인덱스가 0부터 시작하므로 IndexError: list index out of range가 계속 뜬다는 점 유의!!! # PASS!!!! # [1] 빈 리스트가 들어올 때와 [2] 리스트에 없는 값이 들어올 때의 예외 처리에 유의 하여야겠다. 정확성: 55.6             효율성: 44.4             합계: 100.0 / 100.0 # PASS!!!! # -1의 중복을 줄어 효율성을 높여보자. 정확성: 55.6             효율성: 44.4             합계: 100.0 / 100.0 (04) 피보나치 순열         문제 설명         인자로 0 또는 양의 정수인 x 가 주어질 때,          Fibonacci 순열의 해당 값을 구하여 반환하는 함수 solution() 을 완성하세요.          Fibonacci 순열은 아래와 같이 정의됩니다.         F0 = 0         F1 = 1         Fn = Fn - 1 + Fn - 2, n >= 2          재귀함수 작성 연습을 의도한 것이므로,         재귀적 방법으로도 프로그래밍해 보고, 반복적 방법으로도 프로그래밍해 보시기 바랍니다. # 1) 재귀함수로 풀기 # 2) 반복함수로 풀기 난이도 ⭐️⭐️⭐️⭐️⭐️ # n=3 # if n == 0: return 0 //  answer가 0으로 초기화 되어있으므로 안써줘도 상관없음. # 값변경 사용 # (05) 재귀적 이진탐색      문제 설명      리스트 L 과, 그 안에서 찾으려 하는 원소 x 가 인자로 주어지고,           또한 탐색의 대상이 되는 리스트 내에서의 범위 인덱스가 l 부터 u 까지로 (인자로) 정해질 때,           x 와 같은 값을 가지는 원소의 인덱스를 리턴하는 함수 solution() 을 완성하세요.           만약 리스트 L 안에 x 와 같은 값을 가지는 원소가 존재하지 않는 경우에는 -1 을 리턴합니다.           리스트 L 은 자연수 원소들로 이루어져 있으며, 크기 순으로 정렬되어 있다고 가정합니다. 또한, 동일한 원소는 두 번 이상 나타나지 않습니다.      인덱스 범위를 나타내는 l 과 u 가 인자로 주어지는 이유는, 이 함수를 재귀적인 방법으로 구현하기 위함입니다.           빈 칸에 알맞은 내용을 채워서 재귀 함수인 solution() 을 완성하세요.      예를 들어,L = [2, 3, 5, 6, 9, 11, 15]x = 6l = 0u = 6의 인자들이 주어지면, L[3] == 6 이므로 3 을 리턴해야 합니다.      또 다른 예로,L = [2, 5, 7, 9, 11]x = 4l = 0u = 4로 주어지면, 리스트 L 내에 4 의 원소가 존재하지 않으므로 -1 을 리턴해야 합니다. 정확성: 55.6         효율성: 0.0         합계: 55.6 / 100.0 난이도 ⭐️⭐️⭐️⭐️⭐️ 효율성 생각하기!!!             채점 결과             정확성: 55.6             ⭐️ 효율성: 44.4               합계: 100.0 / 100.0 # ⭐️ x가 리스트 L에 없다면, #x=10 L=[11,15]일때, lower는 0, mid=0.5, upper=1로 까지 가게 되므로, u=-0.5, l=1.5가 된다. => 뒤바뀜. #x=16 L=[11,15]일때, lower는 0, mid=0.5, upper=1로 까지 가게 되므로, u=1, l=1.5가 된다. => 뒤바뀜. (07) 연결 리스트 순회     문제 설명     제 7 강에서 소개된 추상적 자료구조로 LinkedList 라는 이름의 클래스가 정의되어 있다고 가정하고, 이 리스트를 처음부터 끝까지 순회하는 메서드 traverse() 를 완성하세요.      메서드 traverse() 는 리스트를 리턴하되, 이 리스트에는 연결 리스트의 노드들에 들어 있는 데이터 아이템들을 연결 리스트에서의 순서와 같도록 포함합니다. 예를 들어, LinkedList L 에 들어 있는 노드들이 43 -> 85 -> 62 라면, 올바른 리턴 값은 [43, 85, 62] 입니다.      이 규칙을 적용하면, 빈 연결 리스트에 대한 순회 결과로 traverse() 메서드가 리턴해야 할 올바른 결과는 [] 입니다.      [참고] "실행" 을 눌렀을 때 통과하는 것은 아무 의미 없습니다. # 빈 리스트라면 head와 tail이 None # 빈 리스트가 아니라면 헤더가 존재하므로 추가, # a는 노드의 순서만 의미하므로, 노드이 데이터에 접근하려면 a.data를 해주어야함. # 헤드의 다음 연결 노드로 접근 문제 설명     제 8 강에서 소개된 추상적 자료구조 LinkedList 클래스의 메서드로서 popAt() 메서드를 강의 내용에 소개된     요구조건을 만족시키도록 구현하세요.      초기 코드로 들어 있는 것은 solution() 함수를 포함하여 다른 부분은 수정하지 말고,      def popAt(self, pos): 의 메서드 몸체만 구현하세요.      만약, 인자로 주어진 pos 가 올바른 범위의 값을 가지지 않는 경우에는 IndexError exception 을 발생시키도록 합니다.      이렇게 하기 위한 코드는 raise IndexError 입니다. # 1차 작성 코드 #인덱스 벗어났을 때, 1) head를 없애는 경우, pos == 1                 2) tail을 없애는 경우, pos == nodeCount                 3) nodeCount ==1, pos ==1,  유일한 노드를 없애는 경우 + 2) tail을 없애는 경우, pos == nodeCount                 4) nodeCount > 1 1<post<nodeCount # tail의 노드를 없앨 경우  + 빈리스트 # head의 노드를 없앨 경우 +  빈리스트 # 2차 작성 코드 테스트 1 〉	통과 (0.05ms, 16.8MB)                 테스트 2 〉	통과 (0.06ms, 16.6MB)                 테스트 3 〉	통과 (0.04ms, 16.6MB)                 테스트 4 〉	통과 (0.08ms, 16.7MB)                 채점 결과                 정확성: 100.0                 합계: 100.0 / 100.0 # head 제거 # 유일한 원소 head + tail 제거 # ⭐️ tail도, head도 None # 여러원소 중 head 제거 # ⭐️ 잘라낸 curr의 next는 끊겨있으므로 None! # tail 제거 # ⭐️ prev가 꼬리가 되므로 prev.next는 None # head와 tail사이의 원소 제거 (09) dummy head 를 가지는 연결 리스트 노드 삭제     문제 설명     제 9 강에서 소개된 추상적 자료구조 LinkedList 는 dummy head node 를 가지는 연결 리스트입니다.     이 클래스의 아래와 같은 메서드들을, 강의 내용에 소개된 요구조건을 만족시키도록 구현하세요.      popAfter()     popAt()     이 때, popAt() 메서드의 구현에서는 popAfter() 를 호출하여 이용하도록 합니다.      (그렇게 하지 않을 수도 있지만, 여기에서는 popAfter() 의 이용에 의해서 코드 구현이 보다 쉬워지는 것을 확인하기 위함입니다.)      초기 코드로 들어 있는 것은 solution() 함수를 포함하여 다른 부분은 수정하지 말고,      def popAfter(self, prev): 와 def popAt(self, pos): 의 메서드 몸체만 구현하세요.      만약, popAt() 메서드에 인자로 주어진 pos 가 올바른 범위의 값을 가지지 않는 경우에는      IndexError exception 을 발생시키도록 합니다. 이렇게 하기 위한 코드는 raise IndexError 입니다. # ⭐️ nodeCount는 dumyNode를 제외함. # ⭐️ 노드 삭제시  tail None이어야함. # ⭐️ head와 tail의 연결관계 생성 테스트 1 〉	통과 (0.06ms, 16.6MB)             테스트 2 〉	통과 (0.05ms, 16.6MB)             테스트 3 〉	통과 (0.05ms, 16.8MB)             테스트 4 〉	통과 (0.06ms, 16.6MB)             테스트 5 〉	실패 (0.15ms, 16.7MB) # 초기 나의 풀이 # prev가 끝일때, # post가 1일때, #****** # pos가 끝일때 # 중간 # pos == 1 # 1<pos<nodeCount 테스트 1 〉	통과 (0.05ms, 16.6MB)             테스트 2 〉	통과 (0.07ms, 16.7MB)             테스트 3 〉	통과 (0.05ms, 16.5MB)             테스트 4 〉	통과 (0.07ms, 16.6MB)             테스트 5 〉	통과 (0.05ms, 16.6MB) # 진화된 나의 풀이 - # ⭐️ ⭐️  dummy head 를 가지는 연결 리스트에서는 pos가 끝일 때만 유의하면됨. # 빈 리스트 일때, count=0 # 👈 pos가 끝자리 일때 유의 # ⭐️ or 주의 하기 ,  nodeCount는 dumyNode를 제외 (10-1) 양방향 연결 리스트 역방향 순회     문제 설명     제 10 강에서 소개된 추상적 자료구조 DoublyLinkedList 에 대하여, 또한 강의 내용에서 언급한 reverse() 메서드를 구현하세요.      이 reverse() 메서드는 양방향 연결 리스트를 끝에서부터 시작해서 맨 앞에 도달할 때까지 (tail 방향에서 head 방향으로) 순회하면서,      방문하게 되는 node 에 들어 있는 data item 을 순회 순서에 따라 리스트에 담아 리턴합니다.      예를 들어, DoublyLinkedList L 에 들어 있는 노드들이 43 -> 85 -> 62 라면, 올바른 리턴 값은 [62, 85, 43] 입니다.      이 규칙을 적용하면, 빈 연결 리스트에 대한 역방향 순회 결과로 reverse() 메서드라 리턴해야 할 올바른 결과는 [] 입니다. 테스트 1 〉	통과 (0.04ms, 16.6MB)         테스트 2 〉	통과 (0.04ms, 16.6MB) # 나의 풀이 (10-2) 양방향 연결 리스트 노드 삽입     문제 설명     제 10 강에서 소개된 추상적 자료구조 DoublyLinkedList 의 메서드로 insertBefore() 를 구현하세요.      이 insertBefore() 메서드에는 두 개의 인자가 주어지는데, next 는 어느 node 의 앞에 새로운 node 를 삽입할지를 지정하고,      newNode 는 삽입할 새로운 node 입니다.      강의 내용에서 소개된 insertAfter() 메서드의 구현과 매우 유사하게 할 수 있습니다. 테스트 1 〉	통과 (0.06ms, 16.8MB) #나의 풀이 # if next == self.head: #     return False (10-3) 양방향 연결 리스트 노드 삭제     문제 설명     제 10 강에서 소개된 추상적 자료구조 DoublyLinkedList 에 대하여 node 의 삭제 연산에 관련한 아래와 같은 메서드들을 구현하세요.      popAfter()     popBefore()     popAt()     popAfter(prev) 는 인자 prev 에 의하여 주어진 node 의 다음에 있던 node 를 삭제하고, popBefore(next) 는 인자 next 에 의하여     주어진 node 의 이전에 있던 node 를 삭제합니다. 그리고 삭제되는 node 에 담겨 있던 data item 을 리턴합니다.      popAt(pos) 는 인자 pos 에 의하여 지정되는 node 를 삭제하고 그 node 에 담겨 있던 data item 을 리턴하는데,     위 popAfter() 또는 popBefore() 를 호출하여 이용하는 방식으로 구현하세요. 또한, 만약 인자 pos 가 올바른 범위 내에 있지 않은 경우에는     raise IndexError 를 이용하여 IndexError exception 을 일으키도록 구현하세요.      테스트 케이스 1-3 은 각각 (1) popAfter(), (2) popBefore(), (3) popAt() 메서드의 올바른 동작을 검증하는 케이스입니다. 테스트 1 〉	통과 (0.07ms, 16.7MB)         테스트 2 〉	통과 (0.06ms, 16.6MB)         테스트 3 〉	통과 (0.07ms, 16.7MB) # 나의 풀이 # 나의 풀이 # 나의 풀이 (10-4) 양방향 연결 리스트의 병합     문제 설명     제 10 강에서 소개된 추상적 자료구조 DoublyLinkedList 에 대하여 두 개의 양방향 연결 리스트를 앞뒤로 이어 붙이는 메서드 concat() 을 구현하세요.      예를 들어, 양방향 연결 리스트 L1 에는 1 -> 2 -> 3 의 원소가 순서대로 들어 있고, 또다른 양방향 연결 리스트 L2 에는 4 -> 5 의 순서로 원소가 들어 있을 때,     메서드 호출 L1.concat(L2) 의 결과로 L1 은 1 -> 2 -> 3 -> 4 -> 5 의 양방향 연결 리스트가 됩니다. 물     론, L1 또는 L2 또는 둘 다가 비어 있는 양방향 연결 리스트인 경우도 고려되도록 코드를 작성해야 합니다. 테스트 1 〉	통과 (0.05ms, 16.7MB)         테스트 2 〉	통과 (0.07ms, 16.6MB)         테스트 3 〉	통과 (0.05ms, 16.6MB) # 나의 풀이 - 양방향 연결리스트에서는 각각의 리스트가 빈리스트일때를 고려하지 않아도 해결된다. (11) 수식의 괄호 검사 (스택)     문제 설명     소괄호: ( )     중괄호: /{ /}     대괄호: [ ]     를 포함할 수 있는 수식을 표현한 문자열 expr 이 인자로 주어질 때, 이 수식의 괄호가 올바르게 여닫혀 있는지를 판단하는 함수 solution() 을 완성하세요. 이 함수는 수식의 괄호가 유효하면 True 를, 그렇지 않으면 False 를 리턴합니다.      스택을 활용하여 수식 내의 괄호 여닫음의 유효성을 검사하는 알고리즘에 대해서는 동영상 강의 내용을 참고하세요. 테스트 1 〉	통과 (0.01ms, 10.2MB)         테스트 2 〉	통과 (0.01ms, 10.2MB)         테스트 3 〉	통과 (0.01ms, 10.3MB)         테스트 4 〉	통과 (0.01ms, 10.4MB)         테스트 5 〉	통과 (0.01ms, 10.2MB)         테스트 6 〉	통과 (0.01ms, 10.2MB) (12) 중위표현 수식 --> 후위표현 수식     문제 설명     중위 표기법을 따르는 수식 S 가 인자로 주어질 때, 이 수식을 후위 표기법을 따르는 수식으로 변환하여 반환하는 함수 solution() 을 완성하세요.      인자로 주어지는 수식 문자열 S 는 영문 대문자 알파벳 한 글자로 이루어지는 변수 A - Z 까지와 4칙연산을 나타내는 연산자 기호 +, -, *, /, 그리고 여는 괄호와 닫는 괄호 (, ) 로 이루어져 있으며 공백 문자는 포함하지 않는 것으로 가정합니다. 또한, 올바르게 구성되지 않은 수식은 인자로 주어지지 않는다고 가정합니다. (수식의 유효성은 검증할 필요가 없습니다.)      문제에서 미리 주어진, 연산자의 우선순위를 표현한 python dict 인 prec 을 활용할 수 있습니다.      또한, 스택의 기초 강의에서 이미 구현한, 배열을 이용한 스택의 추상적 자료 구조 코드가 이미 포함되어 있으므로 그대로 이용할 수 있습니다.      (참고) 테스트 케이스를 보완하여 문제가 2019년 9월 24일에 수정되었습니다.     (추가 참고) 테스트 케이스를 또 보완하여 문제가 2021년 7월 21일에 수정되었습니다. 추가된 테스트 케이스들은 9번부터 12번까지입니다. 관련하여 질문과 답변 (https://programmers.co.kr/questions/19360) 을 참고할 수 있습니다. ## 처음 접근 방식(오답) # 딕셔너리에 있을 때 # 닫기 괄호를 만났을 때, # 피연산자일때 테스트 1         입력값 〉	"(A+B)*(C+D)"         기댓값 〉	"AB+CD+*"         실행 결과 〉	테스트를 통과하였습니다.         테스트 2         입력값 〉	"A*B+C"         기댓값 〉	"AB*C+"         실행 결과 〉	테스트를 통과하였습니다.         테스트 3         입력값 〉	"A+B*C"         기댓값 〉	"ABC*+"         실행 결과 〉	테스트를 통과하였습니다.         테스트 4         입력값 〉	"A+B+C"         기댓값 〉	"AB+C+"         실행 결과 〉	테스트를 통과하였습니다.         테스트 5         입력값 〉	"(A+B)*C"         기댓값 〉	"AB+C*"         실행 결과 〉	테스트를 통과하였습니다.         테스트 6         입력값 〉	"A*(B+C)"         기댓값 〉	"ABC+*"         실행 결과 〉	테스트를 통과하였습니다. ## 나의 풀이 # 딕셔너리에 있을 때 # 우선순위가 peek보다 낮을 때, stack의 데이터 꺼내고 새로 담아주기 # 닫기 괄호를 만났을 때, # 피연산자일때 # 다른 풀이1 #tmp=[] # <prec>에 있을때 # 비어있을때 # 스택에서 이보다 높거나 같은 우선순위는 pop # 스택에서 이보다 작은 priority를 갖는다면 push # 스택에서 이보다 큰 priority를 갖는다면 pop # <괄호닫기>일때 # elif var == ')': #     while opStack.peek() != '(': #         answer += opStack.pop() #     opStack.pop() # <인수>일때 # 남은 인자 출력 # 다른 풀이2 # (13) 후위표현 수식 계산      ### **문제 설명**      인자로 주어진 문자열 expr 은 소괄호와 사칙연산 기호, 그리고 정수들로만 이루어진 중위 표현 수식입니다. 함수 `solution()` 은      이 수식의 값을 계산하여 그 결과를 리턴하도록 작성되어 있습니다. 이 함수는 차례로 `splitTokens()`, `infixToPostfix()`,      그리고 `postfixEval()` 함수를 호출하여 이 수식의 값을 계산하는데,      - `splitTokens()` - 강의 내용에서와 같은 코드로 이미 구현되어 있습니다.     - `infixToPostfix()` - 지난 강의의 연습문제에서 작성했던 코드를 수정하여, 문자열이 아닌 리스트를 리턴하도록 작성합니다.     - `postfixEval()` - 이번 강의의 연습문제입니다. 함수의 내용을 완성하세요.      즉, 두 개의 함수 `infixToPostfix()` 와 `postfixEval()` 을 구현하는 연습입니다. 스택을 이용하기 위하여 `class ArrayStack` 이 정의되어 있으므로 그것을 활용하세요.      [참고] Python 에는 `eval()` 이라는 built-in 함수가 있어서, 이 함수에 문자열을 인자로 전달하면,      그 문자열을 그대로 Python 표현식으로 간주하고 계산한 결과를 리턴하도록 되어 있습니다. 이 built-in 함수 `eval()` 을 이용하면      이 연습문제는 전혀 직접 코드를 작성하지 않고도 정답을 낼 수 있을 것이지만, 스택을 이용하여 중위표현식을 계산하는 프로그래밍 연습을 위한 것이니,      강의 내용에서 설명한 절차를 수행하도록 코드를 작성해 보세요. # (5+3)*(5-4) # ['(', 5, '+', 3, ')' ,*, '(', 5, '-', 4, ')'] # 피연산자가 올 때, # 여는 괄호가 올때, # 닫는 괄호가 올때, # 연산자가 올 때, #*** 반복문 끊어주기 테스트 1         입력값 〉	"5 + 3"         기댓값 〉	8         실행 결과 〉	테스트를 통과하였습니다.         출력 〉	[5, '+', 3]         테스트 2         입력값 〉	"(1 + 2) * (3 + 4)"         기댓값 〉	21         실행 결과 〉	테스트를 통과하였습니다.         출력 〉	['(', 1, '+', 2, ')', '*', '(', 3, '+', 4, ')']         테스트 3         입력값 〉	"7 * (9 - (3+2))"         기댓값 〉	28         실행 결과 〉	테스트를 통과하였습니다.         출력 〉	[7, '*', '(', 9, '-', '(', 3, '+', 2, ')', ')'] (14) 양방향 연결 리스트로 구현하는 큐         문제 설명         양방향 연결 리스트를 활용하여 큐 (queue) 의 추상적 자료구조 (abstract data structure) 구현을 완성하세요.          정의하고자 하는 큐의 추상적 자료구조는 class LinkedListQueue 로 구현됩니다.          이 문제는 해당 클래스의 메서드들의 구현을 빈칸 채우기 형태로 완성하는 것으로 되어 있으며, 이 클래스의 구현은 L120 부터 시작합니다.          그 위에는 (LL1-117) 이 추상적 자료구조를 구현하기 위해서 이용할 class DoublyLinkedList 와,          또한 여기서 이용하는 class Node 의 구현이 정의되어 있습니다. 이 코드는 이전의 "양방향 연결 리스트" 강의에서 다루어진 것과 완전히 동일합니다.          정확성 테스트는 class LinkedListQueue 의 각 메서드가 올바르게 구현되어 있는지를 검사합니다.          "코드 실행" 을 눌렀을 때 예시 테스트 케이스를 통과하는 것은 아무런 의미가 없습니다. # 나의 풀이 정확성  테스트         테스트 1 〉	통과 (0.06ms, 16.7MB)         테스트 2 〉	통과 (0.04ms, 16.7MB)         테스트 3 〉	통과 (0.06ms, 16.8MB)         테스트 4 〉	통과 (0.06ms, 16.8MB) # (15) 환형 큐 구현          ### **문제 설명**          Python 의 내장 데이터형인 리스트 (list) 를 이용하여 환형 큐의 추상적 자료 구조를 구현한 클래스 `CircularQueue` 를 완성하세요.          [참고] 함수 `solution()` 은 이 클래스의 구현과는 관계 없는 것이지만, 문제가 올바르게 동작하는 데 필요해서 넣어 둔 것이니 무시해도 좋습니다.          또한, "실행" 을 눌렀을 때 예시 테스트 케이스를 통과한다고 출력되는 것은 아무런 의미가 없습니다. # 나의 풀이 # 나의 풀이 # front는 첫 원소의 바로 앞을 지칭하기 때문에 먼저 자릿수를 한자리 위로 옮긴 다음 x를 출력해낸다. # 나의 풀이 # front는 첫 원소의 바로 앞을 지칭함. # (16) 우선순위 큐의 enqueue 연산 구현          ### **문제 설명**          앞선 강의에서 소개된 양방향 연결 리스트의 추상적 자료구조 구현인 클래스 `DoublyLinkedList` 를 이용하여 우         선순위 큐의 추상적 자료구조인 클래스 `PriorityQueue` 의 구현을 완성하세요.          코드의 윗부분은 양방향 연결 리스트를 이용하기 위한 클래스 `Node` 와 `DoublyLinikedList` 의 구현입니다.          그대로 둔 채, 아래에 있는 `class PriorityQueue` 의 메서드들 중 `enqueue()` 메서드의 구현을 위한          빈 칸 채우기만 완성하면 됩니다.          [참고] 함수 `solution()` 은 이 클래스의 구현과는 관계 없는 것이지만, 문제가 올바르게 동작하는 데 필요해서          넣어 둔 것이니 무시해도 좋습니다. 또한, 실행 을 눌렀을 때 예시 테스트 케이스를 통과한다고 출력되는 것은 아무런          의미가 없습니다. # 나의 풀이(빈칸채우기) # 주의 할 것, enqueue시 숫자가 낮은 것이 우선이 되도록!! # 주의 할 것, dequeue시 숫자가 낮은 것이 먼저 나오며, 앞이 아니라 뒤에서 나온다!!!!! (18-01) 이진트리의 depth() 연산 구현     문제 설명     이미 주어진 코드 (class Node 와 class BinaryTree 에 의하여) 의 구조를 따르는 이진 트리 (binary tree) 에 대하여, 트리의 깊이 (depth) 를 구하는 연산의 구현을 완성하세요.      초기 코드에 pass 로만 되어 있는 class Node 의 depth() 메서드와 class BinaryTree 의 depth() 메서드를 구현합니다. 코드의 다른 부분은 수정할 필요가 없습니다.      참고로 할 수 있도록, 강의에서 소개한 size() 메서드들 (class Node 와 class BinaryTree 에 대해서) 을 그대로 두었습니다. 문제로 주어진 depth() 연산도 매우 비슷한 식으로 구현할 수 있으니 참고로 삼으세요.      [참고] 실행 을 눌렀을 때 통과하는 것은 아무 의미 없습니다.     또한, solution() 함수는 테스트에 영향을 미치므로 수정하지 말고 그대로 두세요. # 나의 풀이 # 나의 풀이 테스트 1 〉	통과 (0.05ms, 16.5MB)         테스트 2 〉	통과 (0.04ms, 16.4MB)         테스트 3 〉	통과 (0.05ms, 16.6MB)         테스트 4 〉	통과 (0.04ms, 16.3MB)         테스트 5 〉	통과 (0.05ms, 16.3MB) (18-02) 이진트리의 전위순회 연산 구현 문제 설명 이미 주어진 코드 (class Node 와 class BinaryTree 에 의하여) 의 구조를 따르는 이진 트리 (binary tree) 에 대하여, 트리를 전위 순회 (preorder traversal) 하는 연산의 구현을 완성하세요.  초기 코드에 pass 로만 되어 있는 class Node 의 preorder() 메서드와 class BinaryTree 의 preorder() 메서드를 구현합니다. 코드의 다른 부분은 수정할 필요가 없습니다.  참고로 할 수 있도록, 강의에서 소개한 inorder() 메서드들 (class Node 와 class BinaryTree 에 대해서) 을 그대로 두었습니다. 문제로 주어진 preorder() 연산도 매우 비슷한 식으로 구현할 수 있으니 참고로 삼으세요.  [참고] 실행 을 눌렀을 때 통과하는 것은 아무 의미 없습니다. 또한, solution() 함수는 테스트에 영향을 미치므로 수정하지 말고 그대로 두세요. # 나의 풀이 #나의 풀이 테스트 1 〉	통과 (0.03ms, 16.6MB)     테스트 2 〉	통과 (0.04ms, 16.6MB)     테스트 3 〉	통과 (0.04ms, 16.5MB)     테스트 4 〉	통과 (0.04ms, 16.5MB)     테스트 5 〉	통과 (0.04ms, 16.5MB) (18-03) 이진트리의 후위순회 연산 구현 문제 설명 이미 주어진 코드 (class Node 와 class BinaryTree 에 의하여) 의 구조를 따르는 이진 트리 (binary tree) 에 대하여, 트리를 후위 순회 (postorder traversal) 하는 연산의 구현을 완성하세요.  초기 코드에 pass 로만 되어 있는 class Node 의 postorder() 메서드와 class BinaryTree 의 postorder() 메서드를 구현합니다. 코드의 다른 부분은 수정할 필요가 없습니다.  참고로 할 수 있도록, 강의에서 소개한 inorder() 메서드들 (class Node 와 class BinaryTree 에 대해서) 을 그대로 두었습니다. 문제로 주어진 postorder() 연산도 매우 비슷한 식으로 구현할 수 있으니 참고로 삼으세요.  [참고] 실행 을 눌렀을 때 통과하는 것은 아무 의미 없습니다. 또한, solution() 함수는 테스트에 영향을 미치므로 수정하지 말고 그대로 두세요. 테스트 1 〉	통과 (0.08ms, 16.6MB)         테스트 2 〉	통과 (0.05ms, 16.6MB)         테스트 3 〉	통과 (0.05ms, 16.8MB)         테스트 4 〉	통과 (0.04ms, 16.6MB)         테스트 5 〉	통과 (0.06ms, 16.6MB) (19) 이진 트리의 넓이 우선 순회 문제 설명 이진 트리를 구현한 클래스인 class BinaryTree 에 대하여 넓이 우선 순회 (breadth first traversal) 를 구현하는 메서드 bft() 를 완성하세요.  class ArrayQueue 는 배열 (python list) 을 이용하여 구현한 큐 (queue) 의 추상적 자료구조입니다. 이것을 이용하여 넓이 우선 순회 알고리즘을 구현하세요.  [참고 1] solution() 함수의 구현은 그대로 두세요. 이것을 없애면 테스트가 되지 않습니다.  [참고 2] "코드 실행" 을 눌렀을 때 통과하는 것은 아무런 의미가 없습니다. #나의 풀이 테스트 1 〉	통과 (0.04ms, 16.6MB)         테스트 2 〉	통과 (0.04ms, 16.5MB)         테스트 3 〉	통과 (0.04ms, 16.5MB)         테스트 4 〉	통과 (0.04ms, 16.5MB)         테스트 5 〉	통과 (0.04ms, 16.8MB) (20) 이진 탐색 트리의 원소 삽입 연산 구현 문제 설명 초기 코드에 주어진 class Node 와 class BinSearchTree 를 기반으로, 이진 탐색 트리 (binary search tree) 에 새로운 원소를 삽입하는 insert(key, data) 연산의 구현을 완성하세요.  class BinSearchTree 에는 이미 insert(key, data) 메서드가 구현되어 있습니다. 이것을 그대로 이용하고, class Node 의 insert(key, data) 메서드를 재귀적 방법으로 구현하세요. 강의에서 언급한 바와 같이, 이미 트리 안에 들어 있는 것과 같은 (중복된) 키를 이용하여 삽입을 시도하는 경우에는 KeyError 예외를 발생시켜야 합니다.  [참고 1] inorder() 메서드의 구현은 그대로 두세요. 테스트에 이용됩니다.  [참고 2] solution() 함수의 구현도 그대로 두세요. 이것을 없애면 테스트가 되지 않습니다.  [참고 3] "코드 실행" 을 눌렀을 때 통과하는 것은 아무런 의미가 없습니다. # 나의 풀이 (21) 이진 탐색 트리에서 노드의 삭제 연산 구현 문제 설명 초기 코드에 주어진 class Node 와 class BinSearchTree 를 기반으로, 이진 탐색 트리 (binary search tree) 에서 지정된 원소를 삭제하는 remove(key) 연산의 구현을 완성하세요.  class Node 와 class BinSearchTree 에 이미 구현되어 있는 코드는 수정하지 마세요. 코드 구현의 정확성 평가에 이용됩니다. 초기 코드에 들어 있는 주석을 참고로 하여, BinSearchTree::remove() 메서드의 안에 들어 있는 pass 를 없애고 그 자리에 올바른 코드를 써 넣으면 됩니다.  [참고 1] solution() 함수의 구현은 그대로 두세요. 이것을 없애면 테스트가 되지 않습니다.  [참고 2] "코드 실행" 을 눌렀을 때 통과하는 것은 아무런 의미가 없습니다.  [참고 3] 잘 생각해 보면, 이진 탐색 트리를 구현하지 않고 키 순서대로 정렬된 Python 의 배열을 유지함으로써도 같은 연산을 구현할 수 있습니다.          이 연습문제에서는 효율성 테스트를 하지 않기 때문에 이러한 구현을 오답으로 간주하지 않습니다만, 배열을 이용한 구현과 트리 구조를 이용한 구현은 연산의 복잡도에 큰 차이가 있습니다.          이진 탐색 트리로 구현하여 코드 작성 연습을 하시기 바랍니다. # The simplest case of no children # 만약 parent 가 있으면 # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여 # parent.left 또는 parent.right 를 None 으로 하여 # leaf node 였던 자식을 트리에서 끊어내어 없앱니다. # 만약 parent 가 없으면 (node 는 root 인 경우) # self.root 를 None 으로 하여 빈 트리로 만듭니다. # When the node has only one child # 하나 있는 자식이 왼쪽인지 오른쪽인지를 판단하여 # 그 자식을 어떤 변수가 가리키도록 합니다. # 만약 parent 가 있으면 # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여 # 위에서 가리킨 자식을 대신 node 의 자리에 넣습니다. # 만약 parent 가 없으면 (node 는 root 인 경우) # self.root 에 위에서 가리킨 자식을 대신 넣습니다. # When the node has both left and right children # 1차 풀이(오답) 테스트 1 〉	통과 (0.07ms, 16.8MB)                 테스트 2 〉	통과 (0.04ms, 16.7MB)                 테스트 3 〉	통과 (0.07ms, 16.7MB)                 테스트 4 〉	통과 (0.06ms, 16.7MB)                 테스트 5 〉	실패 (런타임 에러)                 테스트 6 〉	실패 (런타임 에러)                 테스트 7 〉	통과 (0.06ms, 16.9MB)                 테스트 8 〉	실패 (런타임 에러)                 테스트 9 〉	실패 (런타임 에러) # 2차 풀이(정답) # node 가 곧 parent인 경우, s의 child가 left 가 없는 경우 테스트 1 〉	통과 (0.13ms, 16.8MB)                 테스트 2 〉	통과 (0.04ms, 16.7MB)                 테스트 3 〉	통과 (0.07ms, 16.7MB)                 테스트 4 〉	통과 (0.06ms, 16.8MB)                 테스트 5 〉	통과 (0.06ms, 16.8MB)                 테스트 6 〉	통과 (0.06ms, 16.7MB)                 테스트 7 〉	통과 (0.06ms, 16.8MB)                 테스트 8 〉	통과 (0.06ms, 16.7MB)                 테스트 9 〉	통과 (0.07ms, 16.7MB) (22) 최대 힙에 새로운 원소 삽입 문제 설명 초기 코드에 주어진 class MaxHeap 에 최대 힙에 새로운 원소를 추가하는 연산인 insert() 메서드의 구현을 완성하세요.  [참고 1] solution() 함수의 구현은 그대로 두세요. 이것을 없애면 테스트가 되지 않습니다.  [참고 2] "코드 실행" 을 눌렀을 때 통과하는 것은 아무런 의미가 없습니다. # 나의 풀이 테스트 1 〉	통과 (0.06ms, 16.5MB) # 다른 풀이 (23) 최대 힙에서의 원소 삭제 문제 설명 초기 코드에 여기 저기 포함된 빈 칸을 채움으로써 class MaxHeap 의 메서드인 maxHeapify() 의 구현을 완성하세요. 이것은 이미 주어져 있는 remove() 메서드와 연결되어 최대 힙에서의 원소 삭제 연산을 구성합니다.  [참고 1] remove() 메서드의 내용은 이미 주어져 있으므로 수정하지 않는 쪽이 좋습니다.  [참고 2] solution() 함수의 구현은 그대로 두세요. 이것을 없애면 테스트가 되지 않습니다.  [참고 3] "코드 실행" 을 눌렀을 때 통과하는 것은 아무런 의미가 없습니다. # 나의 풀이 # 왼쪽 자식 (left child) 의 인덱스를 계산합니다. # 오른쪽 자식 (right child) 의 인덱스를 계산합니다. # 왼쪽 자식이 존재하는지, 그리고 왼쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다. # 조건이 만족하는 경우, smallest 는 왼쪽 자식의 인덱스를 가집니다. # 오른쪽 자식이 존재하는지, 그리고 오른쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다. #### ⭐️⭐️ i, right, left 셋 중 최대값(smallest)을 찾는 것인데 처음에 self.data[right] > self.data[i]로 작성했다가 엄청 해맸다... ## 출제자 분이 최대값의 변수 명을 great가 아닌 smallest로 지정해놓으셔서 더 헷갈린 것도 있었던 것 같다. # 조건이 만족하는 경우, smallest 는 오른쪽 자식의 인덱스를 가집니다. # 현재 노드 (인덱스 i) 와 최댓값 노드 (왼쪽 아니면 오른쪽 자식) 를 교체합니다. # 재귀적 호출을 이용하여 최대 힙의 성질을 만족할 때까지 트리를 정리합니다. 테스트 1 〉	통과 (0.06ms, 16.8MB)