[1835]카드

Benjamin·2022년 7월 6일

BAEKJOON

목록 보기

6/70

문제

알고리즘

문제요약

이 문제는 이해하기에 어려워서 예시로 스스로의 이해에 도움을 주었다. 예제에 나와있듯 N에 4를 입력했다고 가정해보자. 마지막에 4카드 한장이 남았다는것은, 이전에 맨 앞 카드를 뒤로 보내는 작업을 3번 반복한 후, 맨 윗 카드를 올렸더니 3이되었다는말이다. 따라서 3번째 작업순서를 거꾸로 거슬러가보면, 3 4 -> 4 3 -> 3 4 -> 4 3 이다. 또 이전에는 2번째작업이기때문에 앞에서 했던 작업을 2번 반복한 후, 맨 윗 카드를 올렸을 때 2였을것이다. 따라서 이 작업을 거꾸로 거슬러보면, 2 4 3 -> 3 2 4-> 4 3 2이다. 또 이전 작업은 첫 작업이었을것이다. 따라서 1 4 3 2 -> 2 1 4 3 일것이다. 그렇게 카드 초기 순서는 '2 1 4 3이 되고, 이를 출력하면 정답처리되는것이다.

사용할 수 있는 자료구조

Deque사용
양쪽으로 값을 추가할 수 있어야하므로, 양쪽에서 데이터의 추가,삭제가 가능한 덱이 적합할것으로 보인다.

생각한 알고리즘

마지막 카드를 입력받기때문에, 초기 카드순서로 하는 작업을 N을 기준으로 거꾸로 시행하면 될 것이다. 따라서 N을 입력받고, N--을 첫번째 원소로 추가한다. 그리고 맨 뒤 원소를 조회하여 같은수를 맨앞에 추가한 후 조회한 맨 뒤 원소는 삭제하는 작업을 N-1번 반복한다.
이런 작업을 N-- == 2 일때까지만 반복하고, 마지막 결과를 순서대로 출력한다.

시간복잡도

예상

Deque에서 왼쪽에 원소추가O(1) 작업을 N-1번. 맨 앞 원소 조회O(1), 맨 뒤에 조회한 원소 추가O(1)하는 작업 총 2(1+2+...+(N-1))번.
-> 총 (N-1) + (N^2 -N) = N^2 -1 이므로, O(N^2)이다.
N이 가장 클 때 최악의 케이스인데, 이때에는 시간복잡도가 10^6이다. 이는 1억보다 작으므로 1초안에 가능할것으로 판단된다.

결과

308ms

작성한 코드

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
import java.util.Iterator;

public class Main {

	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		Deque<Integer> deque = new ArrayDeque<Integer>();
		
		
		int num = kb.nextInt();
		int n = num;
		
		deque.addFirst(num);
		
		if(num ==1) {
			System.out.println("1");
			return;
		}
		else {
			deque.addFirst(num-1);
			while(true) {
				n --;
				for(int r = n; r >0; r --) {
					int last = deque.peekLast();
					deque.addFirst(last);
					deque.pollLast();
				}
				if(n == 1) break;
				deque.addFirst(n-1);
			}
			
		}
		Iterator iter = deque.iterator(); // 초기에 선언하면 출력이 안됨. 
		while(iter.hasNext()) {
			System.out.print(iter.next() + " ");
		}
		return;

	}

}

헤맸던부분과 해결방법 및 느낀점

처음에 입력받은 N을 Deque에 넣어주지않고, 너무 로직만 생각해서, N-1만 원소로 추가하면서 시작하였다.
-> 분석 : 백지에 그림을 그린다 생각하고, 초기작업부터 사소한 모든것을 로직에 담아야겠다.
콘솔에서 N을 입력받은 후 출력이 되지않는 문제가 발생했다. 커서는 다음줄로 잘 넘어가있는데, 다른 입력이 되는 상황은 아니었기때문에 출력에 문제가 발생했음을 알았다.
-> 원인 및 분석 : Iterator객체생성을 main()초기에 해주었기때문이었다. iterator 객체가 선언되는 시점이 중요하다. 객체가 생성되는 시점에 요소를 얻고자 접근하는 컬렉션에 접근하기때문에, 접근하는 컬렉션의 데이터가 이 이후에 추가 혹은 삭제되어도 iterator객체에는 반영되지않는다.

위 이미지는 deque객체를 생성하자마자 iterator객체를 생성해주었을때 디버깅한 결과이다. 첫 while문을 돌때에도 'reamaning == 0'임을 확인할 수 있다. 이는 탐색할 원소가 없는것을 의미한다.
-> 해결방법 : Iterator는 접근하고자하는 컬렉션의 데이터값들 작업이 완료된 후, 객체를 생성하고 사용하여서 해결하였다.

위 이미지는 while(iter.hasNext()) {}을 작성하기 전에 바로 iterator객체를 생성해주었을때 iter디버깅 결과이다. 콘솔에 4를 입력하였을때, 정확하게 첫 while문에서 탐색해야할 원소가 4개로 잘 적용된것을 알 수 있다.