문제

www.acmicpc.net/problem/10828

 

10828번: 스택

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지

www.acmicpc.net

 

풀이

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

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])
반응형
저작자표시 비영리 변경금지

'Development > Algorithm' 카테고리의 다른 글

[boj] 1874 - 스택 수열  (0) 2021.03.08
[boj] 2164 - 카드2  (0) 2021.03.08
[boj] 18258 - 큐2  (0) 2021.03.04
[boj] 9012 - 괄호  (0) 2021.03.04
[boj] 1158 - 요세푸스 문제  (0) 2021.03.04

문제

www.acmicpc.net/problem/1158

 

1158번: 요세푸스 문제

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

www.acmicpc.net

 

풀이

해당 문제는 비교적 간단한 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]))

 

 

반응형
저작자표시 비영리 변경금지

'Development > Algorithm' 카테고리의 다른 글

[boj] 1874 - 스택 수열  (0) 2021.03.08
[boj] 2164 - 카드2  (0) 2021.03.08
[boj] 18258 - 큐2  (0) 2021.03.04
[boj] 9012 - 괄호  (0) 2021.03.04
[boj] 10828 - 스택  (0) 2021.03.04

+ Recent posts

티스토리툴바