문제 풀이

[백준] 1764 - 듣보잡

문제 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다. 듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다. 출력 듣보잡의 수와 그 명단을 사전순으로 출력한다. 듣도 못한 사람의 HashSet 하나와, 보도 못한 사람의 HashSet 하나를 선언하여 각각 값을 ..

[백준] 10815 - 숫자 카드 (자바/Java)

문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이..

[백준] 4256 - 트리 (자바/Java)

문제 이진 트리는 매우 중요한 기본 자료 구조이다. 아래 그림은 루트 노드가 유일한 이진 트리이다. 모든 노드는 최대 2개의 자식 노드를 가질 수 있으며, 왼쪽 자식이 순서가 먼저이다. 노드 n개로 이루어진 이진 트리를 BT라고 하자. BT의 노드는 1부터 n까지 유일한 번호가 매겨져 있다. 아래 그림에 나와있는 BT의 루트는 3번 노드이다. 1번 노드는 오른쪽 자식만 가지고 있고, 4와 7은 왼쪽 자식만 가지고 있다. 3과 6은 왼쪽과 오른쪽 자식을 모두 가지고 있다. 나머지 노드는 모두 자식이 없으며, 이러한 노드는 리프 노드라고 부른다. BT의 모든 노드를 순회하는 방법은 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder)로 총 세 가지가 있다. 이 세 방법은 ..

[SWEA] 2819 - 격자판의 숫자 이어 붙이기

배열의 모든 원소에 대해 사방탐색을 6번 진행하는 것이다. dfs를 통해 구현하면 되는데, 한 번 방문한 원소도 다시 방문할 수 있으니 방문여부를 검사할 필요는 없다. 결과값의 중복을 제거하기 위해 hashSet을 사용하였다. 7개의 결과값을 담을 ans배열을 static으로 선언하여 depth가 1 증가할 때마다 ans[depth]에 수를 담았다. 모든 원소에 대해 dfs를 수행하고, ans배열의 0번 index에 초기값을 담아 진행한다. for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) { ans[0] = arr[i][j]; dfs(arr, i, j, 1); } dfs는 사방탐색으로 한다. 먼저 깊이가 7이 되면 결과값을 return한다. 그 다음 사..

[백준] 1991 - 트리 순회

문제 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식) 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트) 가 된다. 입력 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로..

[백준] 1182 - 부분수열의 합 (자바/Java) 재귀 부분집합

문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. 출력 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다. N개의 수 배열에 대한 부분집합 중에서 합이 S가 되는 경우의 수를 찾으면 된다. 그러나 부분수열의 크기가 양수이기 때문에 공집합은 제외해야 한다. 처음에는 sum을 더하는 식으로 했지만, 공집합을 제외하기 위해 boolean 배열을 통해 sum에 더할 것..

[백준] 11725 - 트리의 부모 찾기 (자바/Java)

문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 방법 자체는 dfs를 이용하면 돼서 어렵지 않은데, 메모리와 시간 초과 때문에 오래 걸렸다. 1을 루트로 하기 때문에 1을 시작으로 해서 dfs를 진행하고, 부모 노드를 찾아야 해서 HashMap에 각 child의 부모 노드를 value로 하여 값을 추가하였다. 처음에는 dfs를 각 노드를 찾을 때마다 반복해서 시간이 오래 걸렸는데, dfs는..

[백준] 2116 - 주사위 쌓기 (자바/Java)

문제 천수는 여러 종류의 주사위를 가지고 쌓기 놀이를 하고 있다. 주사위의 모양은 모두 크기가 같은 정육면체이며 각 면에는 1부터 6까지의 숫자가 하나씩 적혀있다. 그러나 보통 주사위처럼 마주 보는 면에 적혀진 숫자의 합이 반드시 7이 되는 것은 아니다. 주사위 쌓기 놀이는 아래에서부터 1번 주사위, 2번 주사위, 3번 주사위, … 의 순서로 쌓는 것이다. 쌓을 때 다음과 같은 규칙을 지켜야 한다: 서로 붙어 있는 두 개의 주사위에서 아래에 있는 주사위의 윗면에 적혀있는 숫자는 위에 있는 주사위의 아랫면에 적혀있는 숫자와 같아야 한다. 다시 말해서, 1번 주사위 윗면의 숫자는 2번 주사위 아랫면의 숫자와 같고, 2번 주사위 윗면의 숫자는 3번 주사위 아랫면의 숫자와 같아야 한다. 단, 1번 주사위는 마음..

[SWEA] 1231 - 중위 순회

트리가 완전 이진트리 형식으로 주어지기 때문에, 배열로 트리를 만들어서 구현하였다. 입력값 중 index와 해당 알파벳 말고는 사용하지 않아도 구현이 가능하다. (index도 사실 순서대로 들어오기 때문에 필요하지 않다) 배열의 index를 1부터 사용하여 i가 인덱스인 노드의 자식 노드는 각각 2*i, 2*i+1의 인덱스를 가진다. 이를 활용하면 배열을 이진트리처럼 활용하여 전위, 중위, 후위 순회가 가능하다. String[] tree = new String[N + 1]; for (int i = 0; i < N; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); int index = Integer.parseInt(st.nextToken()..

[SWEA] 1873 - 상호의 배틀 필드 (자바/Java)

shoot을 할 때 각 방향을 정의하기 위해 HashMap을 활용하였다. 각 방향을 key로 하고, 방향에 따라 달라지는 dr과 dc를 길이 2의 배열에 담아 value로 지정하였다. HashMap dir = new HashMap(); // 각 방향의 dr dc dir.put('', new Integer[] { 0, 1 }); dir.put('^', new Integer[] { -1, 0 }); dir.put('v', new Integer[] { 1, 0 }); 그리고 입력받은 문자열을 char 하나씩 문자열 배열로 만들었다. StringTokenizer st = new StringTokenizer(br.readLine()); int H = Integer.parseInt(st.nextToken()); /..