[java] 백준 알고리즘 11866번 조세퍼스 문제 0 풀이

List의 원리를 잘 이해하면 풀 수 있는 문제다. 

LinkedList는 index에 대해 자유로운 편이기 때문에 index 중간에 삽입하고 삭제하기가 쉽다.

arrayList는 index 기반이라 list 중간 index가 빠지면 다른 index의 데이터까지 복사해야하는 불상사가 생긴다.

그에 비하면 LinkedList는 index가 아닌 노드와 다음 노드 값만 연결하고 있어서 list 내의 값에 대한 복사가 없다. 

LinkedList로 넣은 값에 순서에 맞는 index만 계속해서 삭제해주면 된다.

** arrayList를 사용하면 안되는 건 아니다. index 기준이므로 상관없지만, 개념적으로 값의 삽입과 삭제가

   빠른 건 LinkedList로 배웠기 때문이다.

원하는 삭제 index보다 배열의 크기가 줄어든다치더라도 

문제를 보면 원형으로 앉아있기 때문에 index번째가 될 때까지 계속 돌아주면 된다.(비효율적일 것 같긴 하다

다른 분들은 나머지(%)를 통해서 구한 분들도 있었다.)

* 풀이 소스

 
public class Baekjoon11866 {
 
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());
        
        int totalPeople = Integer.parseInt(st.nextToken());
        int removeOrder = Integer.parseInt(st.nextToken());
        Queue<Integer> josephus = new LinkedList<>();
        
        for(int i=1; i<=totalPeople; i++) {
            josephus.add(i);
        }
        
        int calCount = 0;
        int outputOrder = 0;
        sb.append("<");
        while(outputOrder != totalPeople) {
            int pollNum = josephus.poll();
            calCount++;
            
            if(calCount == removeOrder) {
                sb.append(pollNum+", ");
                outputOrder++;
                calCount = 0;
            }else {
                josephus.add(pollNum);
            }
            
        }
        sb.delete(sb.length()-2, sb.length());
        sb.append(">");
        bw.write(sb.toString());
        bw.flush();
        
    }
 
}