[백준] 1966번 : 프린터 큐 - JAVA [자바] _ 얕은복사/깊은 복사

안녕하세요.

오늘은 백준1996번의 풀이와 제가 놓치고 있었던 얕은복사/깊은복사 에 대해 설명하려고 합니다.
 
www.acmicpc.net/problem/1966

 

 

 

• 문제

 

 

 

 

 

---

• 풀이(코드)

 

 

import java.util.*;



public class Main {
	
	public static class Document {
		int order;
		int priority;
	}
	// 뒤에 자신보다 큰 원소가 있는지 구하는 메서드 
	public static boolean hasLargeElementAfter(int priority, int order, Queue<Document> queue) {
		Queue<Document> copy = new LinkedList<>(queue);
		while(copy.size()>0) {
			Document tmp = copy.poll();
			if(tmp.priority>priority)
				return true;
		}

		return false;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		for (int i=0; i < T; i++) {
			Queue<Document> queue = new LinkedList<>();
			
			boolean flag = true;
			int N = sc.nextInt();
			int M = sc.nextInt();
			for (int j = 0; j < N; j++) {
				int priority = sc.nextInt();
				Document document = new Document();
				document.order = j;
				document.priority = priority;
				queue.offer(document);
			}
			int cnt = 0;

			
			while (queue.size() > 0) {
				Document tmp = queue.poll();
				// 자신보다 우선순위가 큰 원소가 있다면
				if (hasLargeElementAfter(tmp.priority, tmp.order, queue)) {
					queue.offer(tmp); //다시 큐에 더한다.
				}
				else { //출력해도 괜찮은 상태
					cnt++;
					if(tmp.order==M) {
						break;
					}
				}
			}
			
			System.out.println(cnt);
		

		}

	}
}

 

 

 

 

---

• 알고리즘[접근방법]
  1. 큐에 원소를 순서대로 저장한다.
  2. 저장한 원소를 앞에서부터 꺼낸다.
  3. 이때, 큐의 뒤에 자신보다 우선순위가 큰 원소가 있다면, 다시 큐의 맨 끝에 넣는다.
  4. 큐의 뒤에 자신보다 큰 원소가 없다면, 다음 원소를 꺼낸다.
  5. N번째 문서를 꺼낼 수 있을 때까지 반복한다.

우선 우선순위와 입력순서를 같이 큐에 저장해야하기 때문에, Document 객체를 만들어 우선순위와 입력 순서를 저장했습니다.

public static class Document {
	int order;
	int priority;
}

 

 

 

처음에는 단순히 PriorityQueue로 구현하면 끝나는 간단한 문제라고 생각했습니다. 

그렇지만 1(0) - 1(1) - 9(2) - 1(3) - 1(4) - 1(5) 순서대로 PriorityQueue에 들어온다면,

9(2) - 1(3) - 1(4) - 1(5) - 1(0) - 1(1) 순서로 출력이 되어야하는데,

9(2) - 1(3) - 1(4) - 1(5) - 1(0) - 1(1) 순서로 출력이 되는 것을 깨달았습니다.

 

결국 큐로 직접 저 로직을 구현해야되는 것을 알았습니다.

이때 고민해 봐야할 것은, "해당 원소를 지금 출력해도 되는가?" 입니다.

만약, 1-1-9 처럼 뒤에 자신보다 우선순위가 큰 원소(9)가 있다면, 출력하지 않고 다시 큐의 맨 뒤에 삽입해야합니다.

 

그래서 뒤에 자신보다 큰 원소가 있는지만 판별한다면, 간단히 풀 수 있는 문제가 됩니다.

이는 현재큐를 끝까지 순회하면서 구하면 됩니다.

이때 조심해야할 것은 큐를 순회할 때, 원래큐가 아닌 복사한 큐를 순회해야하는 것 입니다.

큐는 모든 원소를 순회하려면 어쩔수없이 poll()/remove() 해야하고, 이는 원래큐를 변형시킵니다.

 

제가 이 문제를 풀면서 발생했던 문제는,

뒤에 자신보다 큰 원소가 있는지 구하고 나면 큐에 저장되었던 값들이 이상해지는 것이었습니다.

분명 큐를 복사해서 원소를 순회했는데 문제가 발생했고, 이는 제가 얕은 복사를 한 큐를 사용해서 발생한 문제였습니다.

 

 

얕은복사와 깊은복사에 대해 간단히 정리해보면 다음과 같습니다.

구분	얕은 복사 (Shallow Copy)	깊은 복사 (Deep Copy)
원시 타입 필드	값을 복사 (독립적)	값을 복사 (독립적)
참조 타입 필드	같은 객체를 참조 (주소값만 복사)	새로운 객체를 생성하여 완전히 복사
영향 관계	원본 또는 복사본 중 하나가 변경되면 서로 영향을 미침	원본과 복사본은 서로 독립적으로 변경됨
사용 시기	객체 내부의 참조 필드가 공유되어도 문제가 없을 때	객체의 모든 필드가 독립적이어야 할 때
예시 상황	배열을 얕은 복사하면, 원본과 복사본이 같은 배열을 참조	배열을 깊은 복사하면, 원본과 복사본이 각기 다른 배열을 참조
코드	Person person1 = person.clone();	Person person1 = new Person(person.clone());

 

즉 얕은복사는, 복사한 객체의 주소를 가리키게 되어 값 변경 시 원본 객체도 같이 변경됩니다.

하지만 깊은복사는, 복사한 객체의 값을 갖는 새로운 객체이기 때문에 값 변경 시 원본 객체에 영향을 미치지 않습니다.

 

 

자신보다 큰 우선순위를 갖는 원소가 있는지 구하는 메서드에서 주의해야할 부분은 다음과 같습니다.

public static boolean hasLargeElementAfter(int priority, int order, Queue<Document> queue) {
		Queue<Document> copy = new LinkedList<>(queue);
        // Queue<Document> copy = queue는 얕은 복사라 원본큐에 영향을 미친다.
		while(copy.size()>0) {
			Document tmp = copy.poll();
			if(tmp.priority>priority)
				return true;
		}

		return false;
}