BAEKJOON : 1406, 10845, 1158

No. 1406

1. Problem

2. My Solution

• insert() 함수를 이용해 삽입 -> 시간초과

import sys

def L():
    global cursor
    if cursor == 0:
        return
    cursor -= 1

def D():
    global cursor, string
    if cursor == len(string):
        return
    cursor += 1

def B():
    global cursor
    if cursor == 0:
        return
    del string[cursor-1]
    cursor -= 1

def P(word):
    global cursor, string
    if cursor == len(string):
        string.append(word)
        cursor += 1
    else:
        string.insert(cursor,word)
        cursor += 1

string = list(sys.stdin.readline().strip())
n = int(sys.stdin.readline().strip())
cursor = len(string) 

for _ in range(n):
    instruction = sys.stdin.readline().strip().split()

    if instruction[0] == 'L':
        L()
    elif instruction[0] == 'D':
        D()
    elif instruction[0] == 'B':
        B()
    else:
        P(instruction[1])

print(''.join(string))

• insert() 함수대신 문자열을 잘라서 삽입 -> 시간초과

def P(word):
    global cursor, string
    if cursor == len(string):
        string.append(word)
        cursor += 1
    else:
        string = string[0:cursor] + list(word) + string[cursor:]
        cursor += 1

3. Others' Solutions

• 스택을 2개 이용해서 구현
• pop() 수행시 원소가 없는 경우 에러가 발생하므로 try-catch문 이용
• right_stack의 문자들은 역순으로 출력

import sys

def L():
    global left_stack,right_stack
    try:
        right_stack.append(left_stack.pop())
    except:
        return
    
def D():
    global left_stack,right_stack
    try:
        left_stack.append(right_stack.pop())
    except:
        return
  
def B():
    global left_stack,right_stack
    try:
        left_stack.pop()
    except:
        return

def P(word):
    global left_stack,right_stack
    left_stack.append(word)
    

left_stack = list(sys.stdin.readline().strip())
right_stack = []
n = int(sys.stdin.readline().strip())

for _ in range(n):
    instruction = sys.stdin.readline().strip().split()

    if instruction[0] == 'L':
        L()
    elif instruction[0] == 'D':
        D()
    elif instruction[0] == 'B':
        B()
    else:
        P(instruction[1])

print(''.join(map(str,left_stack)),end="")
print(''.join(map(str,right_stack))[::-1])

4. Learned

• 어느 부분의 시간을 줄여야 되는지 판단할 줄 알아야 함
• 스택을 2개 이용해서 문제를 푸는 경우도 있음 참고 유튜브
• 시간이 얼마나 걸리는지 확인해보기 위해 아래 코드를 이용할 수 있음

start = time.time()
...수행부분...
print(time.time() - start)

• 파이썬 함수 시간 복잡도 정리 참고 블로그

---

No. 10845

1. Problem

2. My Solution

• 시간초과를 피하기 위해서 크기 10000인 리스트 먼저 생성한 뒤 대입연산만 수행

import sys

def push(x):
    global back_pointer
    queue[back_pointer] = x
    back_pointer += 1

def pop():
    global front_pointer
    if empty() == True:
        print(-1)
    else:
        print(queue[front_pointer])
        front_pointer += 1

def size():
    print(back_pointer - front_pointer)

def front():
    if empty() == True:
        print(-1)
    else:
        print(queue[front_pointer])

def back():
    if empty() == True:
        print(-1)
    else:
        print(queue[back_pointer-1])

def empty():
    if front_pointer == back_pointer:
        return True
    else:
        return False


n = int(sys.stdin.readline().strip())
queue = [0 for _ in range(10001)]
front_pointer = 0
back_pointer = 0

for _ in range(n):
    instruction = sys.stdin.readline().strip().split()

    if instruction[0] == 'push':
        push(instruction[1])
    elif instruction[0] == 'pop':
        pop()
    elif instruction[0] == 'size':
        size()
    elif instruction[0] == 'front':
        front()
    elif instruction[0] == 'back':
        back()
    else:
        if empty() == True:
            print(1)
        else:
            print(0)

3. Others' Solutions

• insert() 함수는 시간복잡도 O(N)이지만 10000번만 명령어를 수행하기 때문에 모두 push 라고해도 100000000 -> 1초

import sys

N = int(sys.stdin.readline())

queue = []

for i in range(N):
    cmd = sys.stdin.readline().split()

    if cmd[0] == "push":
        queue.insert(0, cmd[1])
        ##print(queue)

    elif cmd[0] == "pop":
        if len(queue) != 0: print(queue.pop())
        else: print(-1)

    elif cmd[0] == "size":
        print(len(queue))

    elif cmd[0] == "empty":
        if len(queue) == 0: print(1)
        else : print(0)

    elif cmd[0] == "front":
        if len(queue) == 0: print(-1)
        else: print(queue[len(queue) -1])

    elif cmd[0] == "back":
        if len(queue) == 0: print(-1)
        else: print(queue[0])

4. Learned

• 수행시간이 얼마나 걸릴 지 예상하여 알고리즘을 구현하자

---

No. 10845

1. Problem

2. My Solution

• index를 제거된 후의 요소의 개수로 % 연산함
• index가 요소의 개수를 넘어가면 % 연산자로 다시 앞으로 index를 넘김

import sys

n,k = map(int,sys.stdin.readline().strip().split())

circle = [i for i in range(1,n+1)]
index = k-1
result = []

while(True):
    result.append(circle[index % len(circle)])
    del circle[index % len(circle)]
    index += k-1

    if len(circle) == 0:
        break

    index = index % len(circle)

print("<",end="")
print(', '.join(map(str,result)),end="")
print(">")

3. Others' Solutions

• 맨 앞의 요소를 pop -> push 하여 다시 뒤로 삽입함 (참고 유튜브)

4. Learned

• 스택의 pop, push 연산자를 이용해서 구현할 수 있는 알고리즘을 생각해보자
• 인데스가 0부터 시작해야 % 연산자로 다시 앞으로 돌아갈 수 있음