-
[알고리즘-JAVA] 백준 알고리즘 1158번 - 조세퍼스 문제알고리즘 2019. 7. 31. 16:28
접근 과정
1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?원형으로 앉은 M명의 사람들중 K번째 사람을 제거하는 순열을 조세퍼스 순열이라고 하고
(M,K)로 나타낸다.
2. 나의 방식대로 문제를 재정의 하자.
원으로
3. 어떤 알고리즘과 자료구조를 사용할 것인가?큐, 반복문 사용 계획
4. 어떻게 계산할 것인가?
1) 입력Scanner를 통해서 입력받을 것이다.
2) 큐큐에 초기 숫자들을 넣어준 뒤에,
조세퍼스 순열 규칙에 따라서 하나씩 빼준다.
3) 반복문
조세퍼스 순열이 사라질때까지 계산을 반복할 때.
4) 시간 복잡도 계산
M개의 숫자를
K번 순회하므로
O(M*K)이다.
5. 주의할 점은 무엇인가?
특정번째 사람이 제거되었을때를 주의해서 봐야한다.또한 k와 M의 범위가 0에서 5000사이라는것.
6. 풀이 과정
K번째가 나올때까지 Queue의 맨앞을 맨 뒤로 보낸다.
이후 K번째가 나오면 지우고, StringBuilder에 추가시킨 뒤
다시 K번째가 나올때까지 Queue의 맨 앞을 맨 뒤로 보낸다.
전체 소스 코드
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Deque; import java.util.StringTokenizer; public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Deque<Integer> deque = new ArrayDeque<>(); StringBuilder sb = new StringBuilder("<"); StringTokenizer st = new StringTokenizer(br.readLine(), " "); int n = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken()); for (int i = 1; i <= n; i++){ deque.add(i); } while(!deque.isEmpty()){ for (int i = 0; i < k-1; i++){ deque.addLast(deque.removeFirst()); } sb.append(deque.removeFirst() + ", "); } System.out.println(sb.toString().substring(0,sb.length()-2) + ">"); } }
'알고리즘' 카테고리의 다른 글
[알고리즘-JAVA] 다이나믹 프로그래밍 (0) 2019.07.31 [알고리즘-JAVA] 문자열 길이재기 (0) 2019.07.31 [알고리즘-JAVA] 백준 알고리즘 1406번 - 에디터 (0) 2019.07.31 [알고리즘-JAVA] 백준 알고리즘 10799번 - 쇠막대기 (0) 2019.07.30 [알고리즘-JAVA] 백준 알고리즘 9012번 - 괄호 (0) 2019.07.30