Classic_Blue_Note

문제

www.acmicpc.net/problem/9012

풀이

스택 개념을 이용하되, 실제로 스택을 구현하지 않고 풀이하였다.

우선 데이터를 입력받은 뒤, VPS를 확인해주는 함수를 작성하였다. 이때, VPS를 판별하기 위해 별도의 sum이라는 값을 활용했는데, 예외 상황을 모두 고려하기 위해 if-else문을 이용하여 작성하였다.

(을 만날 때마다 1씩 더하고, )을 만나면 1을 뺀다. 이때 (가 모두 사라진 상태에서 )를 만날 경우 VPS가 아니기 때문에 NO를 출력한다.

모든 연산이 끝난 상태에서 (와 )의 개수가 같을 경우 sum값이 0이어야 하기 때문에, 이때 YES를, 아닌 경우 NO를 출력한다.

연산이나 저장 장소가 필요한 경우 스택을 사용해도 되지만, 이 문제에서는 별도의 연산이 필요 없고, 존재 유무 및 스택의 길이 정도만 확인하면 되기 때문에 스택을 직접 사용하지는 않고 해당 개념만 차용했다.

코드

T = int(input())

data = []
for i in range(T):
    data.append(input())


def VPS(test):
    sum = 0
    
    for char in test:
        if char == "(":
            sum += 1
            
        else:
            if sum == 0:
                return "NO"
                
            else:
                sum -= 1
                
    if sum == 0:
        return "YES"
        
    else:
        return "NO"

for test in data:
    print(VPS(test))

문제

www.acmicpc.net/problem/10828

풀이

스택을 구현하는 문제이다. 파이썬의 경우, 스택을 직접 구현하지 않고도, 리스트를 이용해서 유연하게 사용할 수 있다.

push의 경우 operand가 존재하기 때문에 입력받을 때부터 split 메소드를 이용하여 입력받았다.

좀더 스택스럽게 구현하기 위해 isempty 함수만 별도로 구현했고, 나머지는 기존 리스트 클래스에 존재하는 메소드를 이용하여 구현하였다.

인덱스 값 중 -1은 맨 뒤의 위치를 의미하는 인덱스이다. append 메소드를 사용하면 리스트에서 자연스럽게 뒤쪽으로 값이 추가되기 때문에, 뒤의 값을 빼내기 위해 -1 인덱스를 활용하였다. insert 메소드를 통해 값을 앞에 넣을수도 있지만, append는 O(1)의 시간 복잡도를 갖고, insert는 O(n)의 시간 복잡도를 갖기 때문에 append 메소드를 활용하였다.

코드

N = int(input())

op_list = []

for i in range(N):
    op_list.append(input().split(" "))


def isempty(stack):
    return len(stack) == 0


st = []

for op in op_list:
    if op[0] == "push":
        st.append(int(op[1]))
        
    elif op[0] == "pop":
        if isempty(st):
            print(-1)
        else:
            print(st.pop(-1))
            
    elif op[0] == "size":
        print(len(st))
        
    elif op[0] == "empty":
        if isempty(st):
            print(1)
        else:
            print(0)
            
    elif op[0] == "top":
        if isempty(st):
            print(-1)
        else:
            print(st[-1])

문제

www.acmicpc.net/problem/1158

풀이

해당 문제는 비교적 간단한 solved.ac 기준 실버 5급 문제로, 처음에는 원형 큐를 사용해야 할 지 고민했지만, 조금 생각해 보니 굳이 원형 큐를 구현할 필요 없이, 리스트와 인덱스 포인터만을 이용하여 간단하게 해결할 수 있다.

필자의 경우, 우선 사람 배열을 만들고, 제거할 사람의 위치를 가리키는 인덱스 포인터를 지정했다. 그리고 해당 인덱스 포인터에 K값을 더해 가면서, 해당 값이 사람 배열의 크기보다 커지면 나눠 줘 가면서 원형으로 이동하는 것을 표현했다.

그리고 사람을 빼낸 다음, 빼낸 사람을 그대로 요세푸스 배열에 추가한다. 이때 사람을 빼낸 후 인덱스 포인터를 1만큼 감소시켜야 하는데, 그 이유는 사람을 빼내면서 자연스럽게 인덱스 포인터가 다음 사람을 가리키게 되기 때문에, 다음 사람을 1번째 사람으로 표현하기 위해서는 인덱스 포인터를 함께 1만큼 감소시켜 줘야 한다.

출력 형식에서 약간의 문제가 있었는데, 파이썬 메소드 중 __str__ 메소드를 이용하여 간단하게 해결하였다. 리스트의 경우 __str__ 메소드를 거치면 [a, b, c] 형태로 출력되기 때문에, 해당 메소드를 호출한 뒤 맨 앞과 맨 뒤의 문자만 제거하고, 해당 부분에 <, >를 넣어 출력하는 식으로 해결하였다.

코드

N, K = map(int, input().split(" "))

people = []
for i in range(N):
    people.append(i+1)

yosep = []
people_index = -1

while True:
    people_index += K
    people_index = people_index % len(people)
    yosep.append(people.pop(people_index))
    people_index -= 1
    if len(people) == 0:
        break

print("<{}>".format(yosep.__str__()[1:-1]))