[알고리즘/자바] 백준 2164번 - 카드2

2164번: 카드2

 

문제에서 알려준 동작을 정직하게 Java의 Stack을 통해 구현했다. 

1부터 N까지의 숫자를 Stack에 넣고, while문을 통해 문제에서 제시한 동작을 수행하도록 했다. 아니나 다를까 시간초과ㅠㅠ 이렇게 하면 정답은 나오겠으나 입력 N이 커질수록 수행 속도가 떨어져 시간초과가 발생한다. 아래는 시간초과가 발생했던 코드.

( Java의 Stack을 썻던 이유는 Queue와 달리 Stack은 add를 통해 Top이 아닌 Bottom에도 데이터를 넣을 수 있기때문었다. )

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
 
 
public class Main {
    
    public static void main(String[] args) throws IOException{
        
        
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String in = br.readLine();
        
    
        int ans = solve(Integer.valueOf(in)); 
        
        bw.write(ans + "\n");
        
        
        bw.flush();
        bw.close();
    }
    
    public static int solve(int n) {
        
        Stack<Integer> stack = new Stack<>();
        for(int i=n; i>0; i--) {
            stack.push(i);
        }
        
        while(stack.size() > 1) {
            
            stack.pop();
            int toBottom = stack.pop();
            stack.add(0, toBottom);
 
        }
        
        return stack.pop();
    }
}
 

 

 

 

시간을 줄이기 위해 이런저런 그림을 그리다가 "홀수번째에 있는 카드는 무조건 버려진다"라는 아이디어에서 아래 그림을 도출했다. 홀수와 짝수의 경우 처리방법이 다르니 N이 6인 경우와 5인경우를 모두 테스트해본다. 

 

N이 6인 경우. 1을 버리고 그다음 카드인 2는 보존카드에 보관한다. 그리고 3을 버리고 4를 보존카드에 보관한다. 

현재상태가 모두 비워질때까지 같은 작업을 반복하면 한 사이클이 완료된다.

보존 카드에 있는 2, 4, 6을 현재상태 영역으로 꺼내고 다시 위에서 했던 작업을 반복한다.  보존카드에 있는 영역에 카드가 하나뿐이므로 작업을 중단한다. 정답은 4. 

N이 5인 경우. 

N이 짝수인 경우 이부분에서 N이 홀수인 경우와 차이가 발생한다. 현재 상태에 남아있는 5를 버리면, 다음번에 카드 하나를 보존카드로 보내야하는데 더이상 남은 카드가 없다. 이때는 보존카드에 가장 마지막에 들어간 2를 꺼내 다시 push해준다. 

현재 상태에는 4,2가 있으며, 4를 버리고 나면 2만 남는다. 따라서 정답은 2.

N이 5이건 6이건 현재상태에 있는 카드의 홀수번째는 항상 버려진다는 점을 알 수 있다.

위 그림을 코드로 풀면 아래와 같다. 

 
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
 
public class Main {
    
    public static void main(String[] args) throws IOException{
        
        
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String in = br.readLine();
        
        ArrayList<Integer> numbers = new ArrayList<Integer>();
        for(var i=1; i<Integer.valueOf(in)+1; i++) {
            numbers.add(i);
        }
        
        int ans = solve( numbers ); 
        
        bw.write(ans + "\n");
        
        bw.flush();
        bw.close();
    }
    
    public static int solve(ArrayList<Integer> current) {
        
        // 현재상태 영역에 카드가 1개뿐이라면 작업을 종료한다.
        if(current.size() == 1 ) {
            return current.get(0);
        }else {
            // 보존영역을 하나 만든다.
            ArrayList<Integer> keep = new ArrayList<>();
            for(var i=0; i<current.size(); i++) {
                
                // 홀수번째는 버리고 짝수번째만 보존영역에 담는다. 
                if( (i+1) % 2 == 0) keep.add(current.get(i));
            }
            
            // 현재상태 영역에 있던 카드의 갯수가 홀수개였으면 추가작업을 진행한다. 
            if(current.size() % 2 == 1 ) {
                int poll = keep.remove(0);
                keep.add(poll);
            }
            
            // keep에 있는 카드를 현재상태 영역으로 보내고 다시 작업을 시작한다.
            return solve(keep);
        }
    }
}