바킹독 0x04 문제3 / 백준 1158번 요세푸스 문제

반갑소

오랜만이요.

 

추석때 싱글벙글 놀기만 했소

이렇게 긴 연휴를 뱅글뱅글 놀아서그런지 조금의 아쉬움이 남소

그래도 책을 좀 봤소

 

한권을 다 읽진 못했지만

뭐 이번주안으로 마무리 할 것이요.

 

오랜만에 문제를 푸려니 굉장히 풀기싫ㅇ...

것도 있지만 아무 기억이 나지않는게 문제인거 같소..

이래서 나는 언제쯤...ㅋㅋㅋㅋ

 

오늘은 이름이 특이한 요세푸스... 문제를

풀어보겠소..

---

 

..문제를 20분이나 읽어봤는데 이해를 못 해서 지선생에게 물어봤다.

 

지선생 말로는 k 번째 사람 제거라서

1 2 3 4 5 6 7

이렇게 있으면

1부터 3칸 3지우고

그럼 3 다음인 4부터 시작 3칸 6 지우고

7에서 시작 3칸이니까 2 지우고

이렇게 지우는 거 같다.

중요한 건 원이 문제인데..

원으로 어떻게 만드는지 안 배웠는데......

ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

맨 마지막의 다음 주소를 처음 주소로 하면 될 거 같은데

생각은 드는데 어떻게 코드를 짜야할지 잘 모르겠다.

 

지선생은 큐?로 푸는 방식이 가장 좋다고 이야기해 주었으나..

나는 아직 큐를 안 배웠기 때문에 연결리스트로 마음을 먹었다.

답을 봤더니 배열로 사용했다.

 

배열로 구현한 원형 연결 리스트

함께 알아보자.

 

 

pre와 nxt는 i 번째 사람의 왼쪽과 오른쪽을 담당한다.

왼쪽에는 그전사람의 주소가 담기고

오른쪽에는 그다음 사람의 주소가 담겨있도록 했다.

그리고 vector v는 제거되는 순서를 담도록 만들었다.

사실 이것도 5001 개 하면 되긴 하겠다.

 

이 식은 1부터 N까지 원형으로 연결하는 방식이다.

만약에 pre [i] 내 왼쪽에 식이 1이라면.. 맨 앞이니까

맨뒤의 숫자를 넣어주어야 하니 N을 넣어주게 되고

그게 아니라면 내가 지금 3인데 pre [i]는 2가 나와야 하니까

i-1로 해주는 방식이다.

 

밑도 마찬가지로

N 일경우 내 오른쪽의 값이 원형에 의해 1이 되어야 하니까

그 상황을 제외하고 다 next인 1을 더해주는 방식이다.

 

len을 더하는 이유는 길이를 카운트해서 나중에 한 개씩 빼면서

for문을 돌리기 위해서 더하게 된다.

 

 

여기서 i는 카운트에 역할을 한다.

k값까지 카운트가 되어야 한다. 그래서

조건문으로 i == k가 나오는 것이다.

 

연결리스트에서 커서역할을 하는 친구가

cur 이 친구이다.

여기가 중요한데

cur의 nex 사람의 전 주소를 내 전주소로 바꾼다.

아 이게 말로 하면 어렵고

 

 

 

그림으로 나타내면

cur이 5라고 치자

5의 nxt 인 6에 pre값를

현재 5의 pre값인 4로 수정 ( 보라색 화살표 )

 

5의 pre인 4의 nxt값을 

현재 5의 nxt값인 6으로 수정 ( 초록색 화살표 )

 

이렇게 해서 5의 양쪽 값을 바꿔주게 된다.

지우게 되는 것..!

그리고 5를 벡터에 넣고

그리고 i를 초기화하고 len--한 줄 빼주기 숫자 하나 빠졌으니까

 

아니면 그냥 i++해서 k값에 맞추고!

 

다 하고 나서 출력도 나름? 중요한데

그 이유는

꼭 < > 이 친구를 적어달라고 했기 때문

 

그래서 < 먼저 출력하고

벡터 사이즈만큼 벡터를 출력한다.

 그 사이사이에 따옴표도 넣어야 해서

if문으로 한 사이즈보다 작게 돌면서 " , " 해줘야 한다.

 그다음에 다시 >로 닫아주기.

하면 끝!

 

배열로 연결리스트 만들어서 푼 거긴 한데

진짜 std list를 쓰면 어떨지 궁금해서 지피티에게 물어봤다.

그래도 배열로 연결리스트 쓰는 게 동적할당이 적어서 더 성능이 빠르다고 한다.

시간복잡도는 n*k개지만 말이다.

 

그래서 위에 식이 더 좋다고 해서 

그냥 이렇게 하기로 했다.

 

연결리스트는 이렇게 3문제가 끝이다.

뭔가 엄청 어려운데 문제는 많이 없어서..

... 그냥 지나치고 싶다 ㅎㅎㅋ

 

아! 답 전체는

 

고생했다!

강의들으러 가야겠다!!!