5397-키로거 (python)

1. 내가 작성한 코드 (실패: 시간초과)
  - 효율성을 높이고자 pop(0) 대신, pop() 을 사용하려고 했으나 이것도 시간초과로 실패하였다
  - 그 이유는 아래 핵심 로직에 있듯이, 최대 L의 길이가 1,000,000개인 것이 문제가 된다
    - 시간 복잡도를 계산하면, 아래 단순 구현 코드에선 최악의 경우 O(n^2)이 나온다   
    - 시간제한이 1초, 컴퓨터가 1초당 대략 1억 번의 연산한다는 걸 감안할 때, 시간제한에 당연히 걸릴 것이다.
    - 이에 따라 다른 적절한 알고리즘을 고려해야 하고, 결과적으로 스택을 사용하는 방법을 선택하기로 한다
      그리고 스택을 사용한 풀이는 두 번째 코드에 기록해두었다

tc = int(input())
for _ in range(tc):
    data = input()
    l = len(data)

    stack= list(data[::-1])
    password = [0] * l
    cursor = 0

    while stack:
        letter = stack.pop()
        print('cursor >', cursor, password)
        if letter == '-':
            if len(password) > 0:
                password.pop(cursor-1)
        elif letter == '<':
            if cursor > 0:
                cursor -= 1
        elif letter == '>':
            if cursor <= l:
                cursor += 1
        else:
            if password[cursor] != 0:
                password = 
                  password[:cursor] + [letter] + password[cursor:]  
            else:
                password[cursor] = letter
            cursor += 1

    print(''.join([p for p in password if p != 0]))
    

2. fastcampus 나동빈 강사님 문제 풀이 아이디어

< 핵심 로직 >
    - 최대 L의 길이가 1,000,000개 이므로, 문제에서 요구하는 대로만 구현하면(시뮬레이션 방식을 사용하면)
      문제를 해결할 수 없다
    - 다시 말해, 적절한 알고리즘을 설계해서 문제를 풀어야 한다
    - 여기에서는 스택을 활용하여 선형시간(O(n)) 문제를 해결할 수 있는 알고리즘을 설계한다.

    1. 스택 두 개를 만들고, 스택 두 개의 중간 지점을 cursor로 간주한다
    2. 문자 입력: 왼족 스택에 원소를 삽입한다
    3. '-' 입력: 왼쪽 스택에서 원소를 제거한다
    4. '<' 입력: 왼쪽 스택에서 오른쪽 스택으로 원소를 이동한다
    5. '>' 입력: 오른쪽 스택에서 왼쪽 스택으로 원소를 이동한다

풀이는 강의 자료로 공개하기 어렵습니다.


배운 점
  - 기본 자료구조(스택, 큐)를 활용하려면 더더더 연습해야한다!
  - 시간 복잡도를 선형화할 수 있도록 연습해야한다
  - extend 활용

출처 : fastcampus