백준 1158 - 요세푸스 문제

1,2,3,4,5,6,7의 데이터가 저장되어 있고, k가 3이라면,

1,2,4,5,6,7 ----<3,

1,2,4,5,7 ------<3,6

1,2,4,5 --------<3,6,7 ---->배열을 돌면서 3번째마다 숫자를 뽑아서 수열을 만들면 된다.

 

-해결방법 

 

1. 첫 크기인 N과 K를 받고 이를 저장, N에 크기에 맞게 첫 배열을 초기화

2. 배열의 처음부터 끝까지 카운터등이 돌면서 3번째마다 값을 빼온다. (배열에서 모든 값이 빠져나갈 때까지 순환해야함)

 

배열 기반 풀이 

 public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        ArrayList al = new ArrayList();

        String[] input = br.readLine().split(" ");
        StringBuilder sb = new StringBuilder();
        sb.append("<");
        int index = Integer.parseInt(input[1]);
        int turn=0;
        for(int i=0; i<Integer.parseInt(input[0]);i++){
            al.add(i+1);
        }

        while(!al.isEmpty()){//원 배열이 empty일때 까지 반복 
            //계속 순환하기 위해 k를 더해주고 이를 배열의 길이로 나눈 나머지를 구한다
            turn = (turn+index)%al.size();

            if(turn == 0){ //나누어 떨어지는 경우 (나머지 0)이면, 맨 마지막을 의미 그 자리의 값 출력
                sb.append(al.get(al.size()-1));
                al.remove(al.size()-1);
                turn = al.size(); //인덱스의 마지막으로 두기 

            }else {
                sb.append(al.get(turn-1));//실제 index와 위치는 -1해줘야함
                al.remove(turn - 1);
                turn--;
            }
            if(al.size()>=1) sb.append(", ");
            else sb.append(">");

        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

 

queue이용해서 문제풀이시 

 

 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Queue<Integer> qe = new LinkedList();
        String[] input = br.readLine().split(" ");
        StringBuilder sb = new StringBuilder();
        sb.append("<");

        int index = Integer.parseInt(input[0]);
        int k = Integer.parseInt(input[1]);
        for (int i = 0; i < index; i++) {
            qe.offer(i+1);
        }
		//0~큐에 저장된 문자열 인덱스 끝까지 반복
        for(int i=0; i<index-1;i++){
            for(int j=0; j<k-1;j++){ //앞에 두개는 뒤로 보내기
                qe.offer(qe.peek());
                qe.poll();
            }
            sb.append(qe.peek()+", "); //3번째 단어는 빼기 
            qe.poll();
        }
        //마지막 남아있는 문자처리 
        sb.append(qe.peek()+">");
        bw.write(sb.toString());
        bw.flush();
        bw.close();

훨씬 간편하게 풀 수 있다.

 

 

-배운점 

 

> 일정한 규칙을 가지고 배열을 순회시키기 (배열길이 n, 규칙 k, i는 증가연산)

   k = (k*i) % n 

->k가 배열길이보다 작으면, 배열 안에서 순환 -> k에서 배열 길이만큼 나눈(차감) 나머지 만큼 순환

-> 단 나누어 떨어져서 0이되는 경우 k는 맨처음이 아니라 , 배열의 마지막인 것으로 조정할 필요있음