문제 해석
- 첫번째 줄에 카드의 장(N)개를 입력 받으면, 1번이 제일 위에 가고, N이 제일 아래 가도록 카드를 놓는다.
- 카드를 모두 놓았다면, 제일 위에 있는 카드를 바닥에 버리고, 제일 위에 있는 카드를 아래에 있는 카드 밑으로 옮긴다. 이러한 과정을 반복해서 마지막에 남게되는 카드를 구하는 프로그램을 작성하면 된다.
- 이해하기 쉽게 그림으로 표현하면 아래와 같다.
코드
import java.io.*;
public class Main {
static int[] queue; // 정수를 저장하는 큐
static int front, back;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); // 명령어의 개수
//크기를 N*2를 한 이유는 배열을 옮길 때 크기를 N으로 지정했을 경우,
// 자리를 모두 바꿔야하는 경우가 생긴다.
// 하지만, 크기를 2배로 늘리면 그럴 수고가 없어 진다.
// index는 1부터 시작할 것이므로 (0을 제외) 따라서 2*N -1가 아니라 2*N을 사용할 것이다.
queue = new int[N*2]; //정수 1~N개 만큼 저장하는 큐 배열 초기화
front = 1; //맨 앞의 요소 인덱스 1(0부터 시작하지 않고 1부터 시작하기 때문에)
back = N; //맨 뒤의 요소 인덱스 N
// 1이 제일 위에 가고 N이 제일 아래 가도록 카드를 놓는 것이기 때문에 1~N까지 반복
for(int i = 1; i <= N; i++) {//배열 N부터 1까지 채워넣기
queue[i] = i;
}
br.close();
solution(N); //답을 구하는 솔루션 메소드
System.out.println(queue[front]);
}
static void solution(int N){
while(N-- > 1) { //인덱스를 1부터 지정했기 때문에 N이 1이 될때까지 반복한다.(인덱스 시작이 1이다)
//(1) 제일 위에 있는 요소를 버리고, 제일 위에 있는 카드를 밑으로 옮기는 작업
front++;
queue[back + 1] = queue[front];
//(2) 기존 인덱스 값을 모두 바꾼 것이 아니기 때문에 back+1에 현재 제일 위에 있던 카드를 밑으로 저장했기 때문에
// back도 증가시켜준다.
back++;
//(3) 제일 위에 있는 요소를 버렸기 때문에 front값도 증가시켜준다.
// 2번 증가시키는 이유는 제일 위에 있는 요소를 먼저 버리고 나서의 또 제일 위에 있는 카드를 가장 밑으로 옮기기 때문
front++;
}
}
}- 코드에 대한 설명은 주석으로 작성해 두었다.
결과
느낀 점
- 문제는 어떤 문제인지 해석했으면서 코드로 만드는 데 오래 걸리는 게 회의감....이 든다.
