1231번 - 중위순회

문제의 저작권은 SW Expert Academy에 있습니다.

1. 문제
    1-1. 링크
    1-2. 문제 해석
2. 코드
3. 실행시간

 

 

 

---

 

 

1. 문제

1-1. 링크

SW Expert Academy

 

1-2. 문제 해석

중위 순회에 대해 이해하고 있다면 쉽게 풀 수 있는 문제이다.

이 포스팅에서 중위순회에 대한 설명을 해두었다.

 

문제에서 정점의 번호가 차례대로 주어진다고 했지

트리 구조가 완전 이진트리라고 언급은 하지 않아서 괜히 어렵게 생각했었는데

그냥 완전 이진트리 구조라고 생각하고 풀면 된다.

 

2. 코드

public class Day7_1231_중위순회 {
	static char[] arr;
	static int size;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		for(int tc=1; tc<=10; tc++) {
			size = Integer.parseInt(br.readLine());
			arr = new char[size + 1];

			for(int i=1; i<=size; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				st.nextToken();
				arr[i] = st.nextToken().charAt(0);
			}

			sb.append('#').append(tc).append(' ');
			inOrder(1);
			sb.append('\n');
		}
		System.out.println(sb.toString());
	}

	public static void inOrder(int current) {
		if (current > size) {
			return;
		}
		
		inOrder(current * 2); // left
		sb.append(arr[current]);
		inOrder(current * 2 + 1); // right
	}
}

재귀함수를 호출하면서 사이즈를 넘어가는 걸 체크하고

왼쪽 노드, 부모 노드, 오른쪽 노드를 순서대로 호출하면 된다.

 

3. 실행시간

 

 

 

 

 

---

💡 느낀 점

• 또 1ms 차이가 나길래 조금이라도 줄여보고자 실험을 해봤는데 이상한 결과가 나왔다.
  • 1등: System.out.println("#" + tc + " ");
  • 공동 2등: sb.append("#" + tc + " ");
  • 공동 2등: sb.append('#').append(tc).append(' ');
• 무조건 StringBuilder가 더 빠를거라고 생각했는데 오히려 느린 모습을 보여줬다. (물론 오차범위 내이긴 하다)
• append() 안에 한 번에 넣는거랑 여러 번 append를 사용하는 건 동일한 실행 시간을 보여줬다.
• 물론 고작 몇 줄 출력하는거라 이걸로 결론을 단정 지을 수 없지만... 의외였다.

---