백준 1158번 요세푸스 문제 자바 Java (☆공부 231일차)

1158 요세푸스 문제

https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

 

 

 

 

---

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

---

문제

---

 

 

---

과정 생각해보기

---

 

https://gimbalja.tistory.com/159

공부 81일차: 백준 1158번 요세푸스 문제 자바 Java

 

4달 전에 풀었던 문제

 

 

이때 출제자가 의도한 대로 큐를 사용해서 풀어봤으니, 이번엔 리스트 이용해 풀어보았다

 

숫자를 뒤로 보내면서 큐에 넣었다가 빼는 작업을 반복했던 이전과 달리 위치만 찾아 바로 제거한

 

막히는 부분은 백준 정답 코드 중 시간이 빠른 풀이를 참고했다

 

 

 

---

정답 인정 코드

---

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder("<");    // < 붙이고 시작
        ArrayList<Integer> list = new ArrayList<>();
        
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        for(int i = 0; i < n; i++) {
            list.add(i+1);
        }
        
        int idx = 0;    
        // 처음부터 k-1로 초기화하고 sb.append(list.get(idx)); 하는 방법도 있지만 코드 중복
        while(!list.isEmpty()) {
            idx = (idx+k-1)%n;    // 뺄 자리 추적
            sb.append(list.get(idx));
            if(n != 1) {    // 끝에 , 안 붙이기 위함
                sb.append(", ");
            }
            list.remove(idx);
            n--;
        }
        sb.append(">");
        System.out.println(sb.toString());
    }
 
}
 

 

 

 

---

리스트를 이용한 최근 풀이가 훨씬 빠르다(그래서 시작해본 것도 있지만)