[SWEA] 9429. Directory

[9429. Directory]

문제

---

트리 구조를 만들어 필요한 함수를 생성해야한다.

포인트

---

계속해서 런타임 에러가 발생하였다. 최적화의 문제인가 싶어서 계속해서 고쳐나갔다.

최적화에 대해서 보면

1. string 값의 길이가 최대 6이므로 int 값으로 압축한 뒤 그 값을 들고 관리함으로써 시간을 절약할 수 있다. (문자열 압축)

2. 문제에서 생성되는 디렉토리의 수가 정해졌기 때문에 node pool 을 사용할 수 있다. 그러면 이제 자식 관계를 포인터로 관리할 일이 없어진다, 무슨 말이냐면, 미리 선언한 노드 풀에서 x번 노드를 가져온다고 하면, 그냥 주소를 저장하지 말고 x번 노드가 자식에 있다고 넣어주기만 하면 된다. 즉, 자식이 뭐가 있는지를 정수형으로도 관리할 수 있다.

3. 노드에서 자식의 개수는 30으로 제한두었기 때문에 라이브러리를 사용하기보다 30 크기의 배열을 생성해서 관리할 수 있다.

하지만 3번을 구현하려하자 4번째 테스트케이스에서 자꾸 무한루프에 빠지게되어 문제가 발생했다.

근데 허무하게도 결국 문제는 처음 제출한 코드에서 node pool을 50,000 이 아니라 100,000 을 잡아주니 바로 통과됐다. 아마 copy 하는 과정에서 생긴 디렉토리 때문이 아닐까 싶다.

아래는 최적화하기전 코드에 poll 만 늘린 코드이다.

코드

---

import java.util.*;

class UserSolution {

	private final static int NAME_MAXLEN = 6;
	private final static int PATH_MAXLEN = 1999;
	static int cnt = 0;
	static node9429[] nodes;
	static node9429 head;

	void init(int n) {
		nodes = new node9429[100000];
		head = getNode("/");
	}

	void cmd_mkdir(char[] path, char[] name) {
		node9429 node = getNode(String.valueOf(name).substring(0, name.length - 1));
		String[] p = String.valueOf(path).substring(0, path.length - 1).split("/");
		node9429 parent = head;

		for (int i = 1; i < p.length; i++) {
			for (node9429 n : parent.child) {
				if (n.name.equals(p[i])) {
					parent = n;
					break;
				}
			}
		}
		parent.child.add(node);
	}

	void cmd_rm(char[] path) {
		String[] p = String.valueOf(path).substring(0, path.length - 1).split("/");
		node9429 parent = head;
		node9429 postDir = parent;

		for (int i = 1; i < p.length; i++) {
			postDir = parent;
			for (node9429 n : parent.child) {
				if (n.name.equals(p[i])) {
					parent = n;
					break;
				}
			}
		}
		postDir.child.remove(parent);

	}

	void cmd_cp(char[] srcPath, char[] dstPath) {
		String[] srcP = String.valueOf(srcPath).substring(0, srcPath.length - 1).split("/");
		String[] dstP = String.valueOf(dstPath).substring(0, dstPath.length - 1).split("/");

		node9429 srcDir = head;
		for (int i = 1; i < srcP.length; i++) {
			for (node9429 n : srcDir.child) {
				if (n.name.equals(srcP[i])) {
					srcDir = n;
					break;
				}
			}
		}

		node9429 dstDir = head;
		for (int i = 1; i < dstP.length; i++) {
			for (node9429 n : dstDir.child) {
				if (n.name.equals(dstP[i])) {
					dstDir = n;
					break;
				}
			}
		}


		dstDir.child.add(copy(srcDir));

	}

	node9429 copy(node9429 node) {
		node9429 temp = getNode(node.name);

		Iterator<node9429> iter = node.child.iterator();
		while (iter.hasNext()) {
			temp.child.add(copy(iter.next()));
		}

		return temp;
	}

	void cmd_mv(char[] srcPath, char[] dstPath) {
		String[] srcP = String.valueOf(srcPath).substring(0, srcPath.length - 1).split("/");
		String[] dstP = String.valueOf(dstPath).substring(0, dstPath.length - 1).split("/");

		node9429 srcDir = head;
		node9429 postDir = srcDir;
		for (int i = 1; i < srcP.length; i++) {
			postDir = srcDir;
			for (node9429 n : srcDir.child) {
				if (n.name.equals(srcP[i])) {
					srcDir = n;
					break;
				}
			}
		}

		node9429 dstDir = head;
		for (int i = 1; i < dstP.length; i++) {
			for (node9429 n : dstDir.child) {
				if (n.name.equals(dstP[i])) {
					dstDir = n;
					break;
				}
			}
		}

		postDir.child.remove(srcDir);
		dstDir.child.add(srcDir);

	}

	int cmd_find(char[] path) {
		String[] p = String.valueOf(path).substring(0, path.length - 1).split("/");
		node9429 parent = head;
		for (int i = 1; i < p.length; i++) {
			for (node9429 n : parent.child) {
				if (n.name.equals(p[i])) {
					parent = n;
					break;
				}
			}
		}
		Queue<node9429> queue = new LinkedList<>();

		int sum = -1;
		queue.add(parent);
		while (!queue.isEmpty()) {
			node9429 node = queue.poll();
			Iterator<node9429> iter = node.child.iterator();
			while (iter.hasNext()) {
				queue.add(iter.next());
			}
			sum++;
		}

		return sum;
	}

	node9429 getNode(String name) {
		nodes[cnt] = new node9429(name);
		return nodes[cnt++];
	}
}

class node9429 {
	String name;
	List<node9429> child;

	public node9429(String name) {
		this.name = name;
		child = new ArrayList<>();
	}
}