[JAVA 기본 알고리즘] 백준 알고리즘 1158번 / 조세퍼스

이번 문제는 뽑기와 비슷했습니다. 일정한 규칙에 의해 뽑힐때 총량이 줄어들었어요.

그래서 처음에 하나하나 제외시키는 알고리즘으로 짜보았습니다.

import java.util.*;
public class whtpvjtm {
    static Scanner sc = new Scanner(System.in);
    static int n=sc.nextInt(); static int m=sc.nextInt();
    static int io[]= new int[n];
    static int x=0;static int a=0;
    public static void out(){
        int cnt=0;
        for(int i=x;;i++) {
            if(io[i]==0) cnt++;                
            if (cnt==m) {
                if(a==n-1) {
                    System.out.print((i+1)+">");
                    return;
                }
                System.out.print((i+1)+", ");
                io[i]=1;
                x=i;
                a++;
                return;
            }
            if(i==(n-1))i=-1;
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.print("<");
        for(int i=0;i<n;i++) {
            out();
        }        
    }
 
}
 

이리저리 생각해보다가 코딩을 하다보니 조금은 난잡해졌는데요.. 조금 더 다듬는다면 보는사람도 편하게,

불필요한 비교도 줄일 수 있을 것으로 예상됩니다. 조건문으로 io배열을 통하여 출력된 수인지 아닌지를

비교해보고 제외하는 알고리즘입니다.

import java.util.Scanner;
 
public class wef {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int io[]= new int[n];
        int ia[]= new int[n];
        int x=1;int cnt=0;
        System.out.print("<");
        for(int i=0;;i++) {
            if(ia[i]==0) {
                io[i]=x;
                x++;
                if(io[i]%m==0) {
                    ia[i]=1;
                    cnt++;
                    if(cnt==n) {
                        System.out.print(i+1+">");
                        break;    
                    }
                System.out.print(i+1+", ");
                }
            }
            if(i==(n-1))i=-1;
        }
            
    }
 
}
 

이 코드는 제가 첫번째 코드를 짜다가 생각이나서 짜본 알고리즘입니다. 생각을 많이하고 짜서 그런지 코드가 

짧고 사람이 보기에는 편하다는 장점이 있습니다. 다만 경우의 수를 줄이지 않고 모든 수를 계속 카운트 하면서

진행되기 때문에 숫자가 커졌을때는 실행시간이 기하급수적으로 늘어난다는 단점이 있습니다.