자바랑 코덕코덕

[문제]

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

[문제 풀이]

배열과 해쉬맵 두가지 방법으로 입력을 받아서 문제를 해결하였다.

먼저 입력 받은 N 크기 만큼 노드를 만들었다.

노드가 왼쪽, 오른쪽 자식이 있다면 아래 코드와 같이 넣어주었다.

루트부터 시작해서 전위, 중위, 후위 순위를 아래  코드와 같이 돌려주었다.

[코드 - 배열]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int N;
    static Node[] arr;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new Node[N];
        for (int i=0; i<N; i++) {
            arr[i] = new Node((char)(i + 'A'));
        }

        for (int i=0; i<N; i++) {
            char n, l, r;
            String s = br.readLine();
            n = s.charAt(0);
            l = s.charAt(2);
            r = s.charAt(4);
            if (l != '.') {
                arr[n-'A'].left = arr[l-'A'];
            }
            if (r != '.'){
                arr[n-'A'].right = arr[r-'A'];
            }
        }

        // 전위 순회
        preOrder(arr[0]);
        sb.append("\n");
        // 중위 순회
        inOrder(arr[0]);
        sb.append("\n");
        // 후위 순회
        postOrder(arr[0]);
        sb.append("\n");

        System.out.println(sb);
    }

    static void preOrder(Node node) {
        sb.append(node.ch);
        if (node.left != null) preOrder(node.left);
        if (node.right != null) preOrder(node.right);
    }

    static void inOrder(Node node) {
        if (node.left != null) inOrder(node.left);
        sb.append(node.ch);
        if (node.right != null) inOrder(node.right);
    }

    static void postOrder(Node node) {
        if (node.left != null) postOrder(node.left);
        if (node.right != null) postOrder(node.right);
        sb.append(node.ch);
    }

    static class Node {
        char ch;
        Node left;
        Node right;

        public Node(char ch) {
            this.ch = ch;
        }
    }
}

[코드 - 해쉬 맵]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {

    static int N;
    static Map<Character, Node> map = new HashMap<>();
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        for (int i=0; i<N; i++) {
            map.put((char)('A'+i), new Node((char)('A'+i)));
        }

        for (int i=0; i<N; i++) {
            char n, l, r;
            String s = br.readLine();
            n = s.charAt(0);
            l = s.charAt(2);
            r = s.charAt(4);
            if (l != '.') {
                map.get(n).left = map.get(l);
            }
            if (r != '.'){
                map.get(n).right = map.get(r);
            }
        }

        // 전위 순회
        preOrder(map.get('A'));
        sb.append("\n");
        // 중위 순회
        inOrder(map.get('A'));
        sb.append("\n");
        // 후위 순회
        postOrder(map.get('A'));
        sb.append("\n");

        System.out.println(sb);
    }

    static void preOrder(Node node) {
        sb.append(node.ch);
        if (node.left != null) preOrder(node.left);
        if (node.right != null) preOrder(node.right);
    }

    static void inOrder(Node node) {
        if (node.left != null) inOrder(node.left);
        sb.append(node.ch);
        if (node.right != null) inOrder(node.right);
    }

    static void postOrder(Node node) {
        if (node.left != null) postOrder(node.left);
        if (node.right != null) postOrder(node.right);
        sb.append(node.ch);
    }

    static class Node {
        char ch;
        Node left;
        Node right;

        public Node(char ch) {
            this.ch = ch;
        }
    }
}

[실행 결과 - 배열]

[실행 결과 - 해쉬 맵]

실행 결과는 위와 같다.

[문제]

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

[문제 풀이]

전위 순회 (루트, 왼쪽, 오른쪽) 로 입력이 들어올때 노드를 생성하며 tree 구조로 만들어 주었다.

만들어진 tree 구조에서 후위 순회를 하며 결과를 하나씩 출력해 주었다.

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static Node root;
    static StringBuilder sb = new StringBuilder();

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        root = new Node(stoi(br.readLine()));

        // 노드 생성 트리 생성
        String n;
        while(true) {
            n = br.readLine();
            if (n == null || n.equals("")) break;
            Node node = new Node(stoi(n));
            connectNode(root, node);
        }

        // 후위 순회
        postOrder(root);
        System.out.println(sb);
    }

    static void postOrder(Node node) {
        if (node.left != null) postOrder(node.left);
        if (node.right != null) postOrder(node.right);
        sb.append(node.num).append("\n");
    }

    static void connectNode(Node cur, Node next) {
        if (next.num < cur.num) {
            if (cur.left != null) {
                connectNode(cur.left, next);
            } else {
                cur.left = next;
            }
        } else {
            if (cur.right != null) {
                connectNode(cur.right, next);
            } else {
                cur.right = next;
            }
        }
    }

    static class Node {
        int num;
        Node left;
        Node right;

        Node(int num) {
            this.num = num;
        }
    }
}

[실행 결과]

이와 같이 나온다.

[문제]

널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

[문제 풀이]

우선순위 큐는 힙으로 구현되면 위 문제는 우선순위 큐로 규현해야 하는 문제이다.

자바에서 우선순위 큐는 PriorityQueue로 구현 할 수 있다.

기본으로 최소힙으로 구현되어 있기 때문에 문제에서 0이 입력 받을 때마다 queue가 비어 있지 않다면 그냥 출력해 주면 되는 문제이다.

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {

    static int N;
    static PriorityQueue<Integer> queue = new PriorityQueue<>();

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        N = stoi(br.readLine());

        for (int i=0; i<N; i++) {
            int x = stoi(br.readLine());

            if (x==0) {
                if (queue.isEmpty()) sb.append(0).append("\n");
                else {
                    sb.append(queue.poll()).append("\n");
                }
            } else {
                queue.offer(x);
            }
        }

        System.out.println(sb);
    }
}

[실행 결과]

실행 결과는 위와 같다.

[문제]

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

[문제 풀이]

우선 집의 좌표를 배열에 다 넣어주고 오름차순으로 정렬한다.

이분 탐색을 이용해서 두 공유기 사이의 최대 거리를 찾아줄 것이다.

가능한 범위는 1 부터  마지막 집과 첫 집 사이의 거리이므로

s = 1, e = arr[N-1] - arr[0]으로 초기화 시켜주었다.

그 다음 m = (s+e)/2 가 된다.

공유기 설치한 마지막 집을 left라고 두자.

left와 다음 집 사이의 거리가 m 보다 크면 공유기를 설치할 수 있으므로 cnt를 증가시키고 left = arr[i] 가 된다.

공유기 설치가 끝나면 문제에서 주어진 c개인지 확인해야한다.

공유기를 설치한 cnt 값이 c보다 많거나 작다면 m을 늘려주어야 하므로

ans = m, s = m+1로 만들어준다.

c보다 크면 m을 줄여주어야 한다. 따라서 e = m-1이 된다.

다 돌면 ans를 출력해 주면 된다.

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	static int N, C;
	static int[] arr;
	
	static int stoi(String s) {
		return Integer.parseInt(s);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = stoi(st.nextToken());
		C = stoi(st.nextToken());
		arr = new int[N];
		
		for (int i=0; i<N; i++) {
			arr[i] = stoi(br.readLine());
		}
		Arrays.sort(arr);
		
		int ans = 0;
		
		int s = 1;
		int e = arr[N-1] - arr[0];
		while (s <= e) {
			int m = (s + e) / 2;	// 거리
			int left = arr[0];		// 이전 공유기 설치한 집
			int cnt = 1;			// 공유기 설치한 갯수
			
			for (int i=1; i<N; i++) {
				// 차이가 m 보다 크면 설치 가능
				if (arr[i] - left >= m) {
					cnt++;
					left = arr[i];
				}
			}
			// 공유기 설치 끝
			
			// 설치한 공유기가 C보다 많거나 같으면 줄여야함
			if (C <= cnt) {
				ans = m;
				s = m + 1;
			} else {	// 설치한 공유기가 부족하면 늘려야 함
				e = m - 1;
			}
		}
		System.out.println(ans);
	}
}

[실행 결과]

결과는 위와 같다.