[코딩테스트합격자되기-자바편] 문제15. 요세푸스 문제

💡 해당 풀이는 코딩 테스트 합격자되기 - 자바편 에서 발췌된 내용을 바탕으로 작성되었습니다.

 

문제

 

내용

 

N명의 사람이 원 혀앹로 서 있습니다. 각 사람은 1부터 N까지 번호표를 갖고 있습니다. 그리고 임의의 숫자 K가 주어졌을 때 다음과 같이 사람을 없앱니다.

 

 

이 문제는 유대인 역사가인 플라비우스 요세푸스가 만든 문제입니다.

 

• 1번 번호표를 가진 사람을 기준으로 K번째 사람을 없앱니다
• 없앤 사람 다음 사람을 기준으로 하고 다시 K번째 사람을 없앱니다.

 

N과 K가 주어질 때 마지막에 살아있는 사람의 번호를 반환하는 solution()함수를 구현해주세요.

 

 

 

기록하기

💡 어디까지 생각해봤는지 단계적으로 기록해봅니다.

 

풀이

풀이 시간

 

시작 시각	종료 시각	총 소요 시간
23:09	23:23	14분

 

 

문제 분석

제약 사항 파악 & 테스트 케이스 작성

 

• N과 K는 1 이사 1000 이하의 자연수입니다.

 

 

입력값 분석

💡 입력값을 분석하면 문제에서 요구하는 알고리즘의 시간 복잡도를 간접적으로 파악할 수 있습니다.

 

N	K	return
5	2	3

 

의사 코드 작성

 

💡 의사 코드는 동작 중심으로 작성하는 것이 중요합니다.

💡 의사 코드는 문제 해결 순서로 작성합니다.

💡 의사 코드를 충분히 테스트해봅니다.

solution(N, K) {
    int answer = 1;
    // 큐 생성
    Queue<Integer> queue = new ArrayDeque<>();

    // 큐 채워넣기
    for (int i = 1;i <= N;i++) {
        queue.add(i);
    }

    int counter = 1;
    while (!queue.isEmpty()) {
        int first = queue.poll();
        if (counter == K) {
            answer = first;
            counter = 1;
        } else {
            queue.add(first);
            counter++;
        }
    }
    return answer;
}

 

 

구현

 

public static int solution(int N, int K) {  
    int answer = 1;  

    Queue<Integer> queue = new ArrayDeque<>();  

    for (int i = 1; i <= N; i++) {  
        queue.add(i);  
    }  
    int counter = 1;  
    while (!queue.isEmpty()) {  
        int first = queue.poll();  
        if (counter == K) {  
            answer = first;  
            counter = 1;  
        } else {  
            queue.add(first);  
            counter++;  
        }  
    }  
    return answer;  
}

 

 

 

복기하기

저자 권장 시간	권장 시간 복잡도
30분	O(N*K)

 

 

답안과 나의 풀이를 비교해보세요

public static int solution(int N, int K) {  
    Queue<Integer> deque = new ArrayDeque<>();
    // 1부터 N까지의 번호를 deque에 추가
    for (int i = 1; i <= N; i++) {  
        deque.addLast(i);  
    }

    // 2. deque에 하나의 요소가 남을 때까지 반복
    while (deque.size() > 1) {
        // 3. K번째 요소를 찾기 위해 앞에서부터 제거하고 뒤에 추ㅏ
        for (int i = 0; i < K; i++) {
            deque.addLast(deque.pollFirst());
        }
        // 4. K번째 요소 ㅔ거
        deque.pollFirst();
    }
    // 5. 마지막으로 남은 요소 반환
    return deque.pollFirst();  
}

• 내거 정확도도 맞는지 모르겠다.

 

요약하기

• N은 전체 사람 수, K는 제거된 사람의 번호이다.
• K-1번 poll하고 1번 add 하는 동작을 N번 반복하므로 최종 시간 복잡도는 O(N*K)이다.