[백준] 5430번: AC (tbc)

https://www.acmicpc.net/problem/5430

initial

my intial ValueError solution:

from collections import deque
import sys

n=int(input())
for _ in range(n):
    commands = str(input())
    num = int(input())
    queue = deque(sys.stdin.readline().rstrip()[1:-1].split(","))
    # if flag is False it is queue, else it is reversed

    flag= False
    prev = ''
    countD = 0
    for command in commands:
        if command=='R':
            flag = not flag
        else:
            if not queue:
                break
            if not flag:
                queue.popleft()
            else:
                queue.pop()
    if queue:
        if not flag:
            tmp=[]
            for i in range(len(queue)):
                tmp.append(int(queue[i]))
            print(tmp)
        else:
            tmp=[]
            for i in range(len(queue)-1,-1,-1):
                tmp.append(int(queue[i]))
            print(tmp)
    else:
        print("error")

2 parts are wrong:
1) from if queue statement is wrong. After break, it looks for else?
2) the way that i am trying to print out answer is wrong. Using tmp and appending elements like that is wrong

The else block in your code is associated with the for loop, and it gets executed when the loop completes without encountering a break statement. In Python, the else block following a loop is executed when the loop finishes its iteration without being prematurely exited by a break.

model solution

i fixed those 2 points to get

from collections import deque
import sys

n=int(input())
for _ in range(n):
    commands = str(input())
    num = int(input())
    queue = deque(sys.stdin.readline().rstrip()[1:-1].split(","))
    # if flag is False it is queue, else it is reversed

    if num==0:
        queue=[]

    flag= False
    prev = ''
    for command in commands:
        if command=='R':
            flag = not flag
        else:
            if not queue:
                print("error")
                break
            if not flag:
                queue.popleft()
            else:
                queue.pop()
    else:
        if not flag:
            print("[" + ",".join(queue) + "]")

        else:
            queue.reverse()
            print("[" + ",".join(queue) + "]")

complexity

The time and space complexity of the provided code can be analyzed as follows:

Time Complexity:

1. Input Reading: Reading the number of test cases and the associated inputs (commands and num) for each test case takes O(1) time per test case, assuming a constant number of input values.

2. Deque Initialization: For each test case, initializing the deque by splitting a string takes O(N) time, where N is the length of the input string.

3. Command Processing: Iterating through the commands string and performing operations based on each command has a time complexity of O(L), where L is the length of the commands string.

4. Deque Operations: Within the command processing loop, operations like popleft() and pop() are performed. These operations are O(1) time complexity each, as deque data structures are optimized for efficient element removal at both ends.

5. Printing: After processing the commands, printing the final state of the deque involves joining the elements in the deque using join(), which is O(N) in the worst case, where N is the number of elements in the deque.

Overall, the dominant time complexity factor per test case is the splitting of the input string (O(N)) and joining the deque elements (O(N)), making the time complexity per test case O(N).

Space Complexity:

1. Deque Initialization: The code initializes a deque to store the elements from the input. The space complexity for the deque is O(N), where N is the number of elements in the input string.

2. Other Variables: The code uses a few other variables such as commands, num, flag, prev, and temporary variables. These variables have a constant space requirement and do not depend on the size of the input.

3. Printing: The space required for printing the final state of the deque is O(N), where N is the number of elements in the deque when printed.

Overall, the space complexity is dominated by the space used for the deque (O(N)) and the space required for printing (O(N)), making the space complexity O(N).

In summary, the time complexity per test case is O(N), and the space complexity is O(N), where N is the number of elements in the input string.