[백준] 알고리즘 분류(구현,JAVA)2161번, 카드1

문제 링크

2161번: 카드1

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 1~N까지 순서대로 카드가 놓여져있습니다.

2. 카드가 한 장 남을 때까지 문제에서 설명한 행동을 반복합니다.

3. 버린 카드를 순서와 마지막 남은 카드를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 카드 1장이 남을 때까지 행동을 반복합니다.

 

3. 카드 버린 순서와 남은 카드를 결과로 출력합니다.

 

 

행동 시뮬레이션.

※카드의 정보를 Deque를 통해서 저장하여 행동을 진행하도록 하였습니다.

 

1. 맨 앞에 카드를 버린다.

 

2. 맨 앞에 카드를 맨 뒤로 보낸다.

 

3. 남은 카드의 횟수가 2개 이상일 때 다시 반복, 1개일 때 종료!

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N = 7

 

Deque

1

2

3

4

5

6

7

 

2. 카드 1장이 남을 때까지 행동을 반복합니다.

시뮬레이션 진행!

 

1. 맨 앞에 카드를 버린다.

 

2

3

4

5

6

7

DequeFirst : 1 버리기

 

2. 맨 앞에 카드를 맨 뒤로 보낸다.

 

3

4

5

6

7

2

DequeFirst : 2을 Dequeue.addLast() 추가

남은 카드가 2개 이상으로 행동 반복!

 

1. 맨 앞에 카드를 버린다.

 

4

5

6

7

2

DequeFirst : 3 버리기

 

2. 맨 앞에 카드를 맨 뒤로 보낸다.

 

5

6

7

2

4

DequeFirst : 4을 Dequeue.addLast() 추가

남은 카드가 2개 이상으로 행동 반복!

 

1. 맨 앞에 카드를 버린다.

 

6

7

2

4

DequeFirst : 5 버리기

 

2. 맨 앞에 카드를 맨 뒤로 보낸다.

 

7

2

4

6

DequeFirst : 6을 Dequeue.addLast() 추가

남은 카드가 2개 이상으로 행동 반복!

 

1. 맨 앞에 카드를 버린다.

2

4

6

DequeFirst : 7 버리기

 

2. 맨 앞에 카드를 맨 뒤로 보낸다.

 

4

6

2

DequeFirst : 2을 Dequeue.addLast() 추가

남은 카드가 2개 이상으로 행동 반복!

 

1. 맨 앞에 카드를 버린다.

 

6

2

DequeFirst : 4 버리기

 

2. 맨 앞에 카드를 맨 뒤로 보낸다.

 

2

6

DequeFirst : 2을 Dequeue.addLast() 추가

남은 카드가 2개 이상으로 행동 반복!

 

1. 맨 앞에 카드를 버린다.

 

6

DequeFirst : 2 버리기

 

2. 맨 앞에 카드를 맨 뒤로 보낸다.

 

6

DequeFirst : 6을 Dequeue.addLast() 추가

남은 카드가 1개이므로 종료!

 

 

3. 카드 버린 순서와 남은 카드를 결과로 출력합니다.

 

버린 카드 순서 : 1 3 5 7 4 2

 

남은 카드 : 6

 

1 3 5 7 4 2 6을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• 카드 1장이 남을 때까지 행동을 반복합니다.
• 버린 카드의 순서와 남은 카드를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

결과코드

import java.io.*;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        Deque<Integer> dq = new LinkedList<>();	//카드 저장 Deque
        //카드 저장!
        for(int i=1;i<=N;i++)
            dq.addLast(i);
        int count = 1;
        //행동 진행!
        while(!dq.isEmpty()){
            if(count % 2 == 1)	//카드 버리기 진행
                bw.write(dq.pollFirst() + " ");		//버린 카드 BufferedWriter 저장
            else{	//카드 옮기기 진행!
                int temp = dq.pollFirst();
                dq.addLast(temp);
            }
            count++;
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}