[백준] 회전하는 큐(1021)

https://www.acmicpc.net/problem/1021

1021번: 회전하는 큐

 처음에는 디큐로 구현을 시도했다.

Deque<Integer> dq = new ArrayDeque(); 

 타깃 넘버가 큐의 맨 앞으로 올 때까지 연산을 반복하며 연산 횟수를 구했다.  그리고 총 연산 횟수에는 가까운 쪽으로 이동시킨 경우의 연산 횟수를 더해 주었고, 타깃 넘버를 큐에서 제거하며 하나씩 처리했다. 

int result = 0;
for (int i = 0; i < n; i++) {
	int move = 0;
	while (dq.peekFirst() != targetNumber[i]) {	
		dq.addLast(dq.pollFirst());	
		move++;
	}
    
	// 2번 연산 반복보다 3번 연산 반복이 가까운 경우
	if(move > dq.size()/2)	
		move = dq.size() - move;
	
	result += move;
	dq.pollFirst();
}

 그런데 시간 초과! 매 연산마다 연산의 결과를 큐에 적용했기 때문으로 생각했다. 타깃 넘버가 큐의 맨 뒤에 있는 경우 큐의 크기만큼 요소의 삭제와 삽입을 반복한다. 그래서 자료구조를 변경하고 타깃 넘버의 인덱스 값을 이용해서 한방에 큐의 맨 앞까지의 이동거리를 구하기로 했다. 연산의 결과는 Collections 클래스의 rotate() 메서드를 사용해 큐의 상태를 변경했다. 그리고 빠른 입출력을 위해 BufferedReader와 BufferedWriter를 사용해보았다. 하지만 입출력이 많은 문제는 아니었고, 원인은 다른 데에 있었다. 큐를 만들고 초기값을 1부터 추가할 때, 주어진 크기가 아닌 테스트 케이스의 크기 10까지만 큐에 추가해준 것이 문제였다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
			
		int size = sc.nextInt();
		int n = sc.nextInt();
		
		int[] targetNumber = new int[n];
		for (int i = 0; i < n; i++) {
			targetNumber[i] = sc.nextInt();
		}
		
		LinkedList<Integer> q = new LinkedList<>();	
		for (int i = 1; i <= size; i++) {
			q.add(i);
		}
		
		int count = 0;
		for (int i = 0; i < n; i++) {
			int position = q.indexOf(targetNumber[i]);
			if (position > q.size()/2)
				count += q.size()-position;
			else 
				count += position;
			Collections.rotate(q, q.size()-position);
			q.remove(0);
		}
		
		System.out.println(count);
	}
}

 위 코드를 제출하며 성공!

 

 아래는 최근 '클린 코드'의 의미있는 이름과 함수 부분을 읽고 그것을 적용해보려고 변경해보았다. 기존 프로그램이 워낙 작고, 코드는 더 길어졌지만, "코드는 위에서 아래로 이야기처럼 읽혀야 좋다."를 떠올리며 메인 함수를 고쳐보았고 (주석으로 이야기를 쓰라는 게 아니었을 텐데), 변수명과 메서드명을 구체적이고 서술적으로 지어보는 것, 인자를 결정하고 함수를 만드는 연습이 된 것 같다. 일단 이렇게 저렇게 코드 변경해보기!

 

import java.util.*;

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

		// 입력 받는 부분
		Scanner sc = new Scanner(System.in);
		int size = sc.nextInt(); // 큐의 크기
		int n = sc.nextInt(); // 타겟 넘버의 수
		int[] targetNumber = new int[n];
		for (int i = 0; i < n; i++) 
			targetNumber[i] = sc.nextInt();

		// 주어진 크기의 수가 채워진 큐 만들기
		List<Integer> queue = makeQueueWithNumbers(size);

		// 큐와 타깃넘버들을 이용해 연산수 계산
		int result = calculateTotal(queue, targetNumber);

		// 결과 출력
		System.out.println(result);
	}

	static LinkedList<Integer> makeQueueWithNumbers(int size) {
		LinkedList<Integer> list = new LinkedList<>();
		for (int i = 1; i <= size; i++)
			list.add(i);
		return list;
	}

	static int calculateTotal(List<Integer> queue, int[] targetNumber) {
		int resultTotal = 0;

		for (int i = 0; i < targetNumber.length; i++) {
			// 큐 내의 타깃 넘버의 위치
			int position = queue.indexOf(targetNumber[i]);
			// 타깃 넘버를 찾는데 호출된 연산수
			resultTotal += calculateEach(position, queue.size());
			// 큐에 연산을 수행 -> 큐의 맨 앞으로 보냄
			Collections.rotate(queue, queue.size()-position);
			// 타깃 넘버 제거
			queue.remove(0);
		}

		return resultTotal;
	}

	static int calculateEach(int position, int queueSize) {
		if (position > queueSize / 2)
			return queueSize - position;
		else
			return position;
	}

}