[태그:] HackerRank

[HackerRank] 연락처

animato댓글 남기기

Tries: Contacts

아주 간단한 연락처 어플리케이션을 만들어 보자.

이 문제는 Trie라는 자료구조를 사용해서 푸는 문제이다. 사실 나는 Trie라는 자료구조를 이 문제를 통해 처음 알게 되었다. ‘트라이’ 라고 발음하는 것 같다. 역시 마찬가지로 간단하게 정리해 보자.

트라이(Trie):

500px-trie_example-svg
출처: 위키미디어 커먼즈
  • n-차 트리
  • 접두사 트리(prefix tree) 라고 부르기도 함
  • 루트는 빈 노드
  • 텍스트를 검색하는데 속도가 빠름

검색어 자동완성 기능에 이런 류의 자료 구조가 쓰이는 구나 싶었다.

문제는 두가지 요구사항이 있다.

  • add name: name 부분으로 입력된 문자열을 입력한다.
  • find partial: partial 부분으로 입력된 문자열로 시작하는 이름의 개수를 반환한다.

아래와 같이 풀어보았다.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
static class Trie {
public int countChildWordNode = 0;
public String value;
public Trie [] nodeArray = new Trie[26];
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
Trie root = new Trie();
for(int a0 = 0; a0 < n; a0++){
String op = in.next();
String contact = in.next();
if (op.equals("add")) {
add(contact, root);
} else if (op.equals("find")) {
System.out.println(find(contact, root));
}
}
}
public static void add(String name, Trie root) {
for (int i = 0; i < name.length(); i++) {
String value = name.substring(0, i+1);
char[] charArray = value.toCharArray();
int length = charArray.length;
int index = charArray[length-1] - 'a';
Trie newNode = root.nodeArray[index];
if (newNode == null) {
newNode = new Trie();
newNode.value = value;
}
newNode.countChildWordNode++;
root.nodeArray[index] = newNode;
root = newNode;
}
}
public static int find(String name, Trie root) {
for (int i = 0; i < name.length(); i++) {
String value = name.substring(0, i+1);
char[] charArray = value.toCharArray();
int length = charArray.length;
int index = charArray[length-1] - 'a';
Trie newNode = root.nodeArray[index];
if (newNode != null) {
root = newNode;
} else {
return 0;
}
if (name.equals(root.value)) {
return root.countChildWordNode;
}
}
return 0;
}
}
view raw tries-contacts.java hosted with ❤ by GitHub

문제를 풀면서 꽤 애를 먹었다. 트라이 자체를 만들어 내는 것은 그렇게 어렵지 않았으나 자식노드의 수를 구하는 부분에서 어려움이 있었다. 처음엔 트리를 모두 순회하며 해당 문자열로 시작하는 노드의 수를 모두 세도록 만들었으나 몇몇 케이스에서 타임아웃에 걸렸다.

문제를 푸는 핵심 키는 문자열을 입력 할 때 마다 입력시 거쳐가는 노드의 자식 카운트를 하나씩 올려주는 것이다. 트라이 특성 상 자료 입력 시 글자 하나 마다 하나의 노드를 거쳐 가도록 되어있으므로 본인을 접두사로 포함하는 자식의 개수는 그냥 순회하는 노드마다 카운트를 1씩 올려주면 된다. 거쳐갔던 자료들의 수를 유지하고 있다면 “거쳐갔던 자료들의 수 = 노드의 값을 접두사로 포함하고 있는 노드의 개수” 가 된다.

예를들어 “abc”, “abcd”, “abcdefg” 는 공통적으로 “a” – “ab” – “abc”라는 노드를 거쳐서 저장되었다. 노드를 거쳐갈 때 마다 카운트를 1씩 올렸다면 “a”, “ab”, “abc” 노드는 세 번 거쳐갔을 것이므로 각각 3을 갖고있고(a와 ab는 실제로 입력된 자료가 아니지만 abc가 입력될때 abc가 거쳐가면서 생성됨) “abcd”는 2(abcd와 abcdefg가 거쳐감), “abcde”, “abcdef”, “abcdefg” 는 각각 1을 갖고 있을 것이다(a와 ab의 경우와 같이 abcdefg가 생성될 때 abcde, abcdef가 생성됨).

문제를 풀면서 새로운 자료구조를 배우고 또 고민고민끝에 해결책을 생각해 내 풀어내어서 굉장히 즐거웠던 문제였다!

 

[HackerRank] 이진탐색트리가 맞나요?

animato댓글 남기기

이진트리가 주어지면, 그것이 이진탐색트리인지 감별하는 메소드를 만든다.

이진트리와 이진탐색트리를 구별해야 한다. 이진트리와 이진탐색트리를 간단히 정리하자면..

이진트리:

  • 트리의 각 노드가 최대 두 개의 자식을 갖는 트리

이진탐색트리:

  • 이진트리이면서..
  • 모든 노드의 값은 해당 노드의 모든 왼쪽 자식들의 값보다 커야 함
  • 모든 노드의 값은 해당 노드의 모든 오른쪽 자식들의 값보다 작아야 함
  • 같은 값을 허용하는가는 정의 하기 나름 (본 문제에서는 같은 값은 없다고 정의했다) 

    binary_tree_28oriented_digraph29
    이진트리지만 이진탐색트리는 아님 (이미지 출처: 위키피디아)
200px-binary_search_tree-svg
이진탐색트리(이미지 출처: 위키피디아)

 

다음과 같이 이진탐색트리를 판정하는 코드를 만들었다.

/* Hidden stub code will pass a root argument to the function below. Complete the function to solve the challenge. Hint: you may want to write one or more helper functions.
The Node class is defined as follows:
class Node {
int data;
Node left;
Node right;
}
*/
boolean checkBST(Node root) {
if (root.left == null && root.right == null) {
return true;
} else {
if (checkBST(root.left) && checkBST(root.right)) {
int leftTreeMaxValue = treeMaxValue(root.left);
int rightTreeMinValue = treeMinValue(root.right);
if (leftTreeMaxValue < root.data && root.data < rightTreeMinValue) {
return true;
} else {
return false;
}
} else {
return false;
}
}
}
int treeMaxValue(Node root) {
if (root.left == null && root.right == null) {
return root.data;
} else {
int leftValue = treeMinValue(root.left);
int value = root.data;
int rightValue = treeMinValue(root.right);
if (leftValue < value) {
if (value < rightValue) {
return rightValue;
} else {
return value;
}
} else {
if (leftValue < rightValue) {
return rightValue;
} else {
return leftValue;
}
}
}
}
int treeMinValue(Node root) {
if (root.left == null && root.right == null) {
return root.data;
} else {
int leftValue = treeMinValue(root.left);
int value = root.data;
int rightValue = treeMinValue(root.right);
if (leftValue > value) {
if (value > rightValue) {
return rightValue;
} else {
return value;
}
} else {
if (leftValue > rightValue) {
return rightValue;
} else {
return leftValue;
}
}
}
}
view raw check-BST.java hosted with ❤ by GitHub

이진트리를 구별하는 코드는 별로 어렵지 않았지만 그 안에 이진탐색트리 조건을 같이 담는 과정이 조금 까다로웠다.

[HackerRank] 두 스택 이야기

animato댓글 남기기

Queues: A Tale of Two Stacks

두 개의 스택을 이용해 큐를 만드는 문제. 인풋값을 다루는 메인함수는 주어져 있고 큐만 만들면 된다. 큐에 필요한 스택 변수와 함수도 얼개는 만들어져있는 상태에서 구현만 하면 된다.

제약조건은 인풋값과 관련된 것 외에는 특별히 신경써야 할 것은 없는 것 같다.

스택과 큐를 간단히 정리하면,

스택(Stack):

  • Last-In-First-Out(LIFO) 후입선출
  • push: 스택에 값을 넣는다.
  • pop: 스택의 맨 앞에서 값을 하나 가져온다. 가져온 값은 스택에서 제거된다. (꺼낸다)
  • peek: 스택의 맨 앞에서 값을 하나 가져온다. 가져온 값은 스택에서 제거되지 않는다.

큐(Queue):

  • First-In-First-Out(FIFO) 선입선출
  • enqueue: 큐의 끝에 값을 넣는다.
  • dequeue: 큐의 맨 앞에서 값을 하나 가져온다. 가져온 값은 큐에서 제거된다. (꺼낸다)
  • peek: 큐의 맨 앞에서 값을 하나 가져온다. 가져온 값은 큐에서 제거되지 않는다.

 

다음과 같이 스택 두개를 이용해 하나의 큐를 만들었다.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static class MyQueue<T> {
Stack<T> stackNewestOnTop = new Stack<T>();
Stack<T> stackOldestOnTop = new Stack<T>();
public void enqueue(T value) { // Push onto newest stack
stackNewestOnTop.push(value);
}
public T peek() {
if(stackOldestOnTop.empty()) {
while (!stackNewestOnTop.empty()) {
stackOldestOnTop.push(stackNewestOnTop.pop());
}
}
return stackOldestOnTop.peek();
}
public T dequeue() {
if(stackOldestOnTop.empty()) {
while (!stackNewestOnTop.empty()) {
stackOldestOnTop.push(stackNewestOnTop.pop());
}
}
return stackOldestOnTop.pop();
}
}
public static void main(String[] args) {
MyQueue<Integer> queue = new MyQueue<Integer>();
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
for (int i = 0; i < n; i++) {
int operation = scan.nextInt();
if (operation == 1) { // enqueue
queue.enqueue(scan.nextInt());
} else if (operation == 2) { // dequeue
queue.dequeue();
} else if (operation == 3) { // print/peek
System.out.println(queue.peek());
}
}
scan.close();
}
}
view raw two-stacks-queue.java hosted with ❤ by GitHub

스택 두 개 중 하나는 선입된 값이 가장 위(stackOldestOnTop, 출구스택)에 있도록 하고 다른 하나는 후입된 값이 가장 위(stackNewestOnTop, 입구스택)에 있도록 한다. enqueue시에는 입구스택에 스택의 push를 활용하여 값을 쌓고 dequeue시에는 출구스택에서 값을 빼 낸다. 출구스택에 값이 없을 땐 입구스택에서 값을 모두 가져와서 출구스택에 push한 뒤 출구스택의 맨 앞에서 값을 빼낸다. peek도 dequeue와 같은 방식으로 만들되 출구스택에서 값을 빼지(pop)않고 peek 한다.

예를들어, 큐에 1, 2, 3 을 순서대로 넣는다고 가정하면, 1-2-3 이 enqueue 될 때는 입구스택에 값을 쌓기 때문에 입구스택에 3|2|1] 이런 식으로 쌓이게 된다. 여기서 dequeue를 하려면 (1부터 빼내려면) 입구스택에 있는 모든 값을 출구스택으로 옮겨야 한다. 옮기는 과정에서 입구스택에서 값을 빼낼 땐 3-2-1의 순서대로 값이 빠지게 되고 빠지는 순서 그대로 다시 출구스택에 push하면 1|2|3] 이런식으로 값이 쌓이게 될 것이다. 이렇게 모두 옮기고 난 후 출구스택의 맨 앞 값을 빼내면 1이 빠진다. (dequeue)

한번 풀게 되면 스택과 큐의 특성을 둘 다 자연스럽게 익히게 되는 괜찮은 문제인 것 같다.

[HackerRank]Linked List Cycle 탐지

animato댓글 남기기

HackerRank 라는 온라인 코딩 연습 사이트가 있다.

여기의 문제를 풀어보고 어떻게 풀었는가에 대한 설명과 소감 그리고 배운점을 글로 (꾸준히) 남겨볼까 한다. 나는 평범한 개발자이기에 아마 고민고민끝에 겨우 풀어내고 난 뒤 다른 사람들의 모범답안을 보고 감탄하는 패턴으로 흘러가지 않을까 싶다 ㅋㅋ

Linked Lists: Detect a Cycle

“Easy” 로 분류된 간단한 문제부터 풀어봤다.  간단한 구조로 만들어진 링크드 리스트의 사이클을 탐지해 내는 코드를 만드는 것이다. 사이클이 있으면 true, 없으면 false를 리턴하는 함수를 만들면 된다.

제약조건은 리스트 사이즈는 최소 0부터 최대 100까지.

다음과 같이 풀어보았다.

/*
Detect a cycle in a linked list. Note that the head pointer may be 'null' if the list is empty.
A Node is defined as:
class Node {
int data;
Node next;
}
*/
boolean hasCycle(Node head) {
Node target = head;
if (target == null) {
return false;
}
int i = 0;
while (target.next != null) {
if (i == 100) {
return true;
}
target = target.next;
i++;
}
return false;
}
view raw linked-list-cycle.java hosted with ❤ by GitHub

사이클이 없는 링크드리스트라면 링크의 최대 개수는 노드의 최대 개수 – 1 일 것이다. 이 문제에선 제약조건으로 노드의 최대 개수는 100으로 되어있기 때문에 노드를 쭉 순회하면서 링크의 개수를 세다가 링크의 개수가 100이 되는 순간 사이클이 있다고 판단하도록 만들었다.

처음부터 이렇게 전략을 짜서 코딩 하진 못했고 이렇게 저렇게 코드를 만들다 보니 이런 해법을 찾게 되었다. 다 풀고(사이트 판정을 모두 통과) 나서 들었던 생각은 만약 노드 개수 제약조건이 없거나 매우 클 경우엔 문제가 있지 않을까 하는 생각이 들었다. 그러면서 다른 사람들은 어떻게 풀었을까 Disscussion을 보고 역시나.. 생각지도 못한 방법으로 풀어낸 멋진 답들이 있었다.

천천히 하나씩 노드를 순회하는 포인터와 한번에 두개씩 빠르게 노드를 순회하는 포인터를 계속 비교하다 보면 사이클이 있다면 언젠가는 두 포인터가 가리키는 노드가 같을것이다라는 일종의 “토끼와 거북이” 알고리즘이 인상적이었다. 찾아보니 토끼와 거북이 알고리즘은 사이클 탐지의 꽤 고전적인 알고리즘이었다. (관련링크: https://en.wikipedia.org/wiki/Cycle_detection https://www.quora.com/How-does-Floyds-cycle-finding-algorithm-work-How-does-moving-the-tortoise-to-the-beginning-of-the-linked-list-while-keeping-the-hare-at-the-meeting-place-followed-by-moving-both-one-step-at-a-time-make-them-meet-at-starting-point-of-the-cycle)

쉬운 문제였지만 막상 처음 풀땐 마냥 쉽게 느껴지지는 않았던거 같고 풀고 나서도 더 생각해볼 점과 배워볼만한 여지를 제공해줬던 문제였다. 괜찮았다.