1823 Find the Winner of the Circular Game

1823. Find the Winner of the Circular Game / c++ / Medium / 5분

문제 및 코드

문제 링크

class Solution {
public:
    int findTheWinner(int n, int k) {
        int removedCount = 0;
        vector<int> friends = vector<int>(n);
        for (int i = 0; i < n; ++i)
        {
            friends[i] = i + 1;
        }

        int currentPos = 0;

        while (friends.size() > 1)
        {
            currentPos = (currentPos + k - 1) % friends.size();
            friends.erase(friends.begin() + currentPos);
        }

        return friends.front();
    }
};

접근 방식

자료 구조 / 배열

1. 1번부터 n번까지의 친구가 있을 때, 마지막 한명이 남을 때까지 아래의 게임을 진행한다.
   1. 시작하는 사람을 포함해서 k번째 사람이 탈락한다.
   2. 다음 시작 번호는 탈락한 사람의 다음 번호
2. vector friends(n) 선언 후 각 원소를 1 ~ n 으로 초기화 해줬다.
3. friends 의 원소가 1개 남을 때 까지 아래를 반복
   1. currentPos 에 k - 1 만큼 더 한다. (자기 자신을 포함하므로 1 감소, currentPos 의 시작값은 0)
   2. currentPos 를 friends.size() 로 나머지값을 취해준다. (배열의 크기 밖으로 나가는 예외 처리)
   3. friends에서 currentPos번째의 원소를 빼준다.
4. friends.front()(마지막 남은 원소)를 반환
5. 해결

생각해 볼 점

1. 백준에서도 여러번 접해본 문제라 큰 어려움 없이 풀 수 있었다.
2. 배열의 삭제, 크기를 넘어가는 인덱스의 예외 처리가 중요한 것 같다.