18th Koala 7주차

 

6주차는 입원이슈로.. 블로그를 작성하지 못했다.... (　-̥̥̥̥̥̥̥̥̥̥̥̥̥̥̥̥̥̥̥̥̥̥̥̥̥᷄д-̥̥̥̥̥̥̥̥̥̥̥̥̥̥̥̥̥̥̥̥̥̥̥̥̥᷅ )

 

뭐니뭐니 해도 건강이 최고라는걸 이번에 느꼈다 ㅜ.ㅜ

 

건강관리 더 열시미 해야지...!!

 

7주차는 모의테스트 문제를 설명해보려한다!  

 

스따뚜 ~  (  ˵•́ ᴗ •̀˵)

 

백준 1158번 : 요세푸스 문제0

 

이 문제는 1부터 N번까지 사람들이 원을 이루고 앉아 있을 때 양의 정수 K가 주어지면, K번째 사람을 제거하고 그다음 K번째 사람을 또 제거하는 과정을 반복한다. 이 과정을 모든 사람이 제거될 때까지 반복하며, 제거되는 순서를 출력하는 문제이다!!

 

요세푸스 문제는 자료구조 시간에 배운 큐를 쓰면 쉽게 가능할 것 같다는 생각이 들었다!!
1부터 N까지 큐에 넣은 다음, K-1명은 맨 뒤로 보내고 K번째 사람은 제거해버리는 방식으로 반복하면 된다. (｡・▿・｡)

 

1. 입력 및 초기화

int N, K;
cin >> N >> K;

queue<int> q;
vector<int> result;

// 1부터 N까지 큐에 미리 넣어두기
for (int i = 1; i <= N; ++i) {
    q.push(i);
}

 

큐를 이용해서 1~N까지 순서대로 세팅해두고 제거된 순서를 담을 result 벡터도 따로 선언하였다!

 

 

2. 큐 순환 및 제거

while (!q.empty()) {
    // K-1명은 맨 뒤로 보내기
    for (int i = 0; i < K - 1; ++i) {
        int front = q.front();
        q.pop();
        q.push(front);
    }

    // K번째 사람 제거해서 결과에 저장
    result.push_back(q.front());
    q.pop();
}

 

큐의 특성을 잘 이용해서 앞에서 꺼낸 뒤 다시 뒤로 보내는 식으로 K번째 순서를 만들어준다!
그렇게 만든 K번째를 pop해서 result에 저장하는 방식이다!!

 

 

3. 출력

cout << "<";
for (size_t i = 0; i < result.size(); ++i) {
    cout << result[i];
    if (i != result.size() - 1) cout << ", ";
}
cout << ">" << endl;

 

요세푸스 문제는 출력 포맷이 까다롭기 때문에, <숫자, 숫자, 숫자> 형식을 맞춰주는 게 중요하다!!

특히, 마지막 요소가 아니라면, ", "(쉼표+공백)를 같이 출력해줘야 하니까 if (i != result.size() - 1) 조건을 달아주었다. 

 

 

 

이번 문제는 문제 자체의 이해는 어렵지 않았고, 큐 구조를 활용하는 방식이 꽤 직관적이어서 재밌었다!!

특히 for문으로 K-1명은 돌리고, K번째만 pop()하는 흐름이 꽤 깔끔해서 뿌듯했다 (๑•̀ㅂ•́)و✧

8주차에는 꼭 모든 문제를 다 풀수있도록 열시미 시간배분을 해야겠다!! 

 

다사다난했던 8주차도 끗~!!!⌯>ㅅ•⌯ಣ