저별이의 초보 코딩

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

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

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

출력

예제와 같이 요세푸스 순열을 출력한다.

7 3

<3, 6, 2, 7, 5, 1, 4>

#실버4, 요세푸스 문제 0
import sys
from collections import deque
n,k=map(int,sys.stdin.readline().split())
list=deque([i+1 for i in range(n)])
print('<', end='')
for i in range(n):
    for j in range(k-1):
        list.append(list.popleft())
    print(list.popleft(), end='')
    if(i!=n-1):
        print(',', end=' ')
print('>')

이 문제를 처음 보았을 때 요세푸스 순열이 무엇인지에 대해서 알아보기로 했다.

요세푸스 순열에 대해 먼저 알아보자면 n(사람수), k(몇번째 제외)를 입력받는다.

n번째까지 차례대로 줄을 서서 있는데 k번째 사람만 계속해서 제외하는 것이다.

7,3이라고 가정해보자

그러면 이렇게 줄을 서 있을 것이다.

1 2 3 4 5 6 7

그리고 3번째를 위해서 1,2번째의 수는 차례대로 다시 줄을 세워준다.

3 4 5 6 7 1 2

이렇게 말이다.

그리고 여기서 3을 빼준다.

4 5 6 7 1 2가 되고 다시 여기서 3번째 숫자인 6을 빼준다.

이 과정을 리스트에서 숫자를 다 뺄때까지 반복한다. 

큐 문제를 풀다보니 deque의 중요성을 알게되었는데 여기서도 속도를 빠르게 하기 위해 deque로 입력받고 이 문법을 사용했다. 입력을 deque([])형태로 입력을 받았고 숫자를 뺄때 popleft()를 이용했다.

그리고 빼주는 즉시 출력을 해주기로 했다.

시간 제한이 있기에 새롭게 for문을 만들면 시간이 많이 소요되기 때문이다.

그리고 end=''을 이용해 줄바꿈 없이 출력하도록 해 주었다. 그리고 가운데에는 , 표시까지 넣어주었다.

이 문제를 풀어보니 단계별 풀어보기에 있는 앞의 deque문제를 풀다보면 쉽게 풀리는 문제라는 생각이 들었다.

버블정렬이란?

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘을 의미한다.

버블정렬의 진행과정

5개 배열이 있다고 가정해보자

랜덤 숫자를 넣어보았다.

1. 첫번째 원소인 4와 두번째 원소 9를 비교해보자

오른쪽에 있는 숫자가 크다. 그럼 교환이 일어나지 않는다.

2. 두번째 원소인 9와 세번째 원소인 1을 비교해보자.

오른쪽 숫자가 더 크다.

배열 순서를 바꿔준다.

3. 두번 봤으니 이제는 약간의 감을 잡을 수도 있을것 같다.

9와 3을 비교해준다.

이번에도 교환이 필요한 상태다.

제일 큰 수가 이제 4번째까지 왔다.

4. 9를 위한 처리가 한번 남았다.

9와 5를 비교해준다.

이제 배열에서 가장 큰수가 뒤에 놓였다.

5. 그럼 이제 두번째 큰수를 처리하기 위해 다시 처음부터 시작한다. 이 사례에서는 4번째에 이미 두번째 큰 수가 놓였다.

6. 세번째 큰수인 4는 3번의 교환여부를 확인하고 2번의 교환으로 4는 3번째의 위치에 자리하게 된다.

7. 다음으로는 1부터 비교해야 하지만 이미 1과 3이 다 차례대로 정렬이 되어있기 때문에 이 케이스에서는 교환이 필요없다.

버블정렬 구현 코드(C)

이제 방법을 알았으니 코드로는 어떻게 해야 할지 의문이 들 것이다. 코드를 한번 살펴보자.

#include <stdio.h>

int main(){
	int n=5;
    int list={4,9,1,3,5};
    
    for(int i=0;i<n;i++){
    	for(int j=0;j<n-(i+1);j++){
        	if(list[j]>list[j+1]{
            	int temp=list[j+1];
                list[j+1]=list[j];
                list[j]=temp;
            }
        }
    }
}

C언어로 구현해보면 이렇게 이중 for문과 그 안에서 if문으로 앞 뒤 배열을 확인한 뒤에 비교를 해주는 코드를 넣어주면 된다. 반복은 변수를 설정해서 그만큼 돌도록 했는데 안쪽 for문이 특이할 것이다.

n-(i+1)을 하게 된 이유를 알아보자면

처음할 때는 배열크기-1만큼 교환 비교가 일어나는 것을 볼 수 있을 것이다.

그러면 5-1=4 총 4번 돌게된다

다음 비교는 1번 줄어야 하는데 5-(1+1)=3이므로 3번 돌게 된다.

for문 안에서 j의 최댓값이 줄면서 반복 해주면 정렬이 되게 된다.

버블 정렬 코드(Python)

l=[4,9,1,3,5]
for i in range(len(l)-1,0,-1):
    for j in range(i):
        if l[j]>l[j+1]:
            l[j], l[j+1]=l[j+1], l[j]
print(l)

파이썬으로도 구현해보았다.

C언어에 비해 정말 간단하다.

리스트 안에 값을 넣어주고 마찬가지로 for 이중문과 if문으로 값 비교를 해주었다. 여기서는 반복횟수가 줄어드는 과정을 len(l)-1로 만들어주었다. 바깥 for문에서 몇번 돌지 정해주면 안쪽 for문에서 그만큼 돌려주는 것이다.

바꿔주는 것은 파이썬 문법에서도 볼 수 있듯이 ,로 구분해주어 순서만 바꿔주면 값이 교환되어 들어가므로 쉽게 구현이 가능하다.

버블정렬 정리 그리고 결론: 시간복잡도는??

버블 정렬은 하나하나 모두 비교하고 뒤에서부터 차례대로 채워나가는 형태다. 그래서 매우 시간이 오래 걸릴 수 밖에 없다. 시간복잡도로 나타내면 O(N*N)이 되게 된다. 삽입정렬과 같은 복잡도이지만 연산수가 가장 많아 아 가장 느리고 효율성이 떨어지기 때문에 실제로는 많이 쓰이지는 않는다.

참고자료

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

https://yjg-lab.tistory.com/161

https://bowbowbow.tistory.com/10

https://www.daleseo.com/sort-bubble/

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

So when I die (the [first] I will see in (heaven) is a score list).
[ first in ] ( first out ).
Half Moon tonight (At least it is better than no Moon at all].
A rope may form )( a trail in a maze.
Help( I[m being held prisoner in a fortune cookie factory)].
([ (([( [ ] ) ( ) (( ))] )) ]).
 .
.

yes
yes
no
no
no
yes
yes

이 문제가 처음에는 쉬워 보일 수 있지만 '균형잡힌 문자열'이라는 단어에 주목해야 한다.

나 역시도 단계별 문제에서 앞 문제였던 '괄호' 문제와 같은 방식으로 풀다가 균형잡힌 이라는 말때문에 막혔다.

어떤 과정으로 균형을 잡힌 것을 찾아내는 것일까?

여기서 원하는 것은 열리는 게 ([이라고 한다면 ])가 되어야 한다는 것이다. 만약 비어있는 상태나 ( [ ( ]로 형태가 맞지 않는다면 false로 받아야 한다.  

while(1):
    line=input()
    line_1=list(line)#이건 오류 방지용 리스트따로
    stack=[]
    temp=True

    if(line=='.'):#종료조건 만족시
        break
    for i in line_1:
        if(i=='(' or i=='['):
            stack.append(i)
        elif(i==')'):
            if not stack or stack[-1]=='[':
                temp=False
                break
            elif stack[-1]=='(':
                stack.pop()
        elif(i==']'):
            if not stack or stack[-1]=='(':
                temp=False
                break
            elif stack[-1]=='[':
                stack.pop()
    if temp==True and not stack:
        print("yes")
    else:
        print("no")
    #print(line)

일단 입력받는 과정은 크게 다르지 않다. input으로 입력받아 리스트로 바꿔준다.

그리고 while문 탈출은 바로 문자열에 '.'이 있는지만 확인해주고 break으로 탈출을 시키면 된다.

문제는 for문을 돌릴때인데

일단 여는 소괄호, 대괄호는 stack에 쌓아준다.

그리고 닫힐 때는 앞에 소괄호 혹은 대괄호가 있는지 확인을 해주어야 한다.

만약 닫아주어야 하는 형태 앞에 균형이 맞지 않으면 no로 출력을 해주어야 한다.

하지만 닫아주어야 하는 형태인데 같은 기호이지만 열리는 것이라면 뽑아주어야 한다.

뽑아주어야 하는 이유는 성립했기 때문이다. ()나 []형태로 만들어졌기 때문에 비워주어야 한다. false라면 stack에 기호가 남아있을 것이다.

stack이 아니라는 것은 리스트가 empty라는 말이다.

이렇게 stack이라는 리스트에 열리는 것이라면 닫는 것을 맞춰주어야 하고 안에서는 무조건 균형을 맞추어 닫아주어야 한다. 이것을 생각하는 과정이 굉장히 어려웠던 것 같다.