TWpower Reading time ~3 minutes

Make multi processes environment by parallelly running command in background.


Environment and Prerequisite

  • Linux base system
  • Bash shell(/bin/bash)


Multi Process? Parallel Process? Multi Thread? Background Process?

  • In this post, I will run command or shell script in background by using & operator.
  • By searching, found that by using & operator it will make new child process(in new sub-shell) and run command or shell script in that process(in sub-shell)
  • Specifically, it is ambiguous that call above method as multi process or multi thread… However some of english materials said that & operator makes new child process so I call it as multi process in this post’s title. If there is anyone who know well about this, it is pleasure to give a comment.


Linux &(Ampersand) Opearator

What is & operator?

  • In linux, this operator make shell to run the command in the background, that is, it is forked and run in a separate sub-shell, as a job, asynchronously
  • Running command or script using &, that process will be run in background so that it is possible to keep doing other things in current shell.
  • Examples are below. Just add & to end of command.


& operator examples

  • (Example) Run sleep in background
$ sleep 10 &
[1] 79287
$ # Type enter to make below result
[1]+  Done                    sleep 10
  • (Example) Run shell script in background
  • Like below you can make stdout to log file by using command > filename &.
$ tee test_shell.sh << EOF
> #!/bin/bash
>
> echo 1
> sleep 1
> echo 2
> sleep 1
> echo 3
> EOF
echo 1
sleep 1
echo 2
sleep 1
echo 3
$ ./test_shell.sh > tmp_test_shell.log & # You can redirect stdout to specific file.


(Example) Run shell script function in background parallelly

Explanation

  • Make function and run that function with argument in background.
  • Below example script shows that main script pass array’s element to function and sleeps depends on random value . If there is no & operator then it will be run sequentially but if there is & operator then each process will be run in background separately.
  • Add log file to check each child process is run well.


Code

test_multi_process.sh

#!/bin/bash

function back_ground_process () {
	# Random number between 10 and 15
	sleep_time=$(($RANDOM*12345%6 + 10))

	echo "${1} will sleep for ${sleep_time} seconds"

	sleep ${sleep_time}

	echo "${1} sleep done!"
}

# array in shell script
arr=("a_worker" "b_worker" "c_worker")

# @ means all elements in array
for i in ${arr[@]}; do
    # run back_ground_process function in background
    # pass element of array as argument
    # make log file
    back_ground_process $i > ~/log_${i}.txt &
done
  • wait command wait until all child processes(which are made in current script) are done.

test_multi_process.sh(continue)

...
# @ means all elements in array
for i in ${arr[@]}; do
    # run back_ground_process function in background
    # pass element of array as argument
    # make log file
    back_ground_process $i > ~/log_${i}.txt &
done

# wait until all child processes are done
wait

echo "All background processes are done!"


Result

  • Check logs immediately after running script
  • We can notice that script is finished just after running the script
$ ./test_multi_process.sh
$ cat log_a_worker.txt && cat log_b_worker.txt && cat log_c_worker.txt
a_worker will sleep for 13 seconds
b_worker will sleep for 13 seconds
c_worker will sleep for 10 seconds
  • After 15 seconds, we can notice that all child processes are done well.
$ cat log_a_worker.txt && cat log_b_worker.txt && cat log_c_worker.txt
a_worker will sleep for 13 seconds
a_worker sleep done!
b_worker will sleep for 13 seconds
b_worker sleep done!
c_worker will sleep for 10 seconds
c_worker sleep done!


Applications

  • Use & to run process or daemon in background.
  • For example, you can minimize time for installing some files to multi server computers by running in background simultaneously and it is useful when keep using shell while running other programs in same shell.
  • Additionally, you can use it for multi processing or threading in shell script.


References

TWpower Reading time ~7 minutes

C++에서 트라이(Trie)를 구현해보고 기본 문제를 풀어보자.


환경

  • C++


트라이(Trie)란?

트라이(Trie)의 형태 대해서

  • Trie: 트라이(Trie)란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다.
  • 위에 보이는 트리의 루트에서부터 자식들을 따라가면서 생성된 문자열들이 트라이 자료구조에 저장되어 있다고 볼 수 있습니다. 저장된 단어는 끝을 표시하는 변수를 추가해서 저장된 단어의 끝을 구분할 수 있습니다.
  • DFS 형태로 검색을 해보면 사진의 번호에 나와있듯이 to, tea, ted, ten, A, i, in, inn이라는 단어들이 자료구조에 들어가 있음을 알 수 있습니다.


트라이(Trie)의 예시

  • 직접 그린 Trie이며 주황색으로 된 노드들이 입력된 문자열들입니다.
  • 현재 be, bee, can, cat, cd가 들어가 있습니다.


사용목적

목적

  • 사용하는 이유는 문자열의 탐색을 하고자할 때 시간복잡도를 보면 알 수 있습니다. 단순하게 하나씩 비교하면서 탐색을 하는것보다 훨씬 효율적입니다. 단, 빠르게 탐색이 가능하다는 장점이 있지만 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있습니다.
  • 검색어 자동완성, 사전에서 찾기 그리고 문자열 검사 같은 부분에서 사용할 수 있다고 첨부된 자료에 나와있습니다.

시간 복잡도

  • 제일 긴 문자열의 길이를 L 총 문자열들의 수를 M이라 할 때 시간복잡도는 아래와 같습니다.
  • 생성시 시간복잡도: O(M*L), 모든 문자열들을 넣어야하니 M개에 대해서 트라이 자료구조에 넣는건 가장 긴 문자열 길이만큼 걸리니 L만큼 걸려서 O(M*L)만큼 걸립니다. 물론 삽입 자체만은 O(L)만큼 걸립니다.
  • 탐색시 시간복잡도: O(L), 트리를 타고 들어가봤자 가장 긴 문자열의 길이만큼만 탐색하기 때문에 O(L)만큼 걸립니다.


트라이(Trie)의 구현

공통

  • 알파벳 대문자를 기준으로 만들었습니다.
#include <cstdio>
#include <cstring>

#define ALPHABETS 26

// Convert char to array index
// All are base on capital
int char_to_index(char c){
	return c - 'A';
}


트라이(Trie) 코드

  • is_terminal: 단어의 끝임을 표시하는 변수입니다.
  • void insert(const char * key): 새로운 문자열을 트라이에 추가하는 코드입니다.
  • Trie* find(const char * key): key에 해당하는 문자열을 접두어로 가지고 있는지 확인하고 가지고 있다면 해당 접두어가 끝나는 부분의 위치를 반환합니다.
  • bool string_exist(const char * key): key에 해당하는 문자열이 포함되어 있는지 확인하는 코드입니다. 해당 key의 문자열이 있다면 true를 반환하고 없으면 false를 반환합니다.
struct Trie{

	bool is_terminal; // this represents end of string
	Trie * children[ALPHABETS];

	// Constructor
	Trie(): is_terminal(false){
		memset(children, 0, sizeof(children));
	}

	// Delete all children
	~Trie(){
		for(int i = 0; i < ALPHABETS; ++i){
			if(children[i])
				delete children[i];
		}
	}

	void insert(const char * key){
		if(*key == '\0'){
			is_terminal = true;
		}
		else{
			int index = char_to_index(*key);

			if(children[index] == 0)
				children[index] = new Trie();
			children[index]->insert(key + 1);
		}
	}

	Trie* find(const char * key){
		if(*key == 0){
			return this;
		}

		int index = char_to_index(*key);
		if(children[index] == 0){
			return NULL;
		}

		return children[index]->find(key+1);
	}

	bool string_exist(const char * key){
		if(*key == 0 && is_terminal){
			return true;
		}

		int index = char_to_index(*key);
		if(children[index] == 0){
			return false;
		}
		return children[index]->string_exist(key + 1);
	}

};


메인함수

  • 해당 함수들이 다 올바르게 작동하는지 확인하는 코드를 작성하였습니다.
int main (){

	Trie * root = new Trie();

	const char * words[5] = {"be", "bee", "can", "cat", "cd"};

	for(int i = 0; i < 5; ++i){
		printf("insert: %s\n", words[i]);
		root->insert(words[i]);
	}

	printf("\n");

	printf("%s: be\n", root->find("be") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: can\n", root->find("can") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: a\n", root->find("a") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: cat\n", root->find("cat") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: c\n", root->find("c") != 0 ? "Prefix Exist" : "Prefix Not Exist");

	printf("\n");

	printf("%s: c\n", root->string_exist("c") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: be\n", root->string_exist("be") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: bee\n", root->string_exist("bee") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: candy\n", root->string_exist("candy") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: cd\n", root->string_exist("cd") != 0 ? "String Exist" : "String Not Exist");

	delete root;

	return 0;
}


전체코드

#include <cstdio>
#include <cstring>

#define ALPHABETS 26

// Convert char to array index
// All are base on capital
int char_to_index(char c){
	return c - 'A';
}

struct Trie{

	bool is_terminal; // this represents end of string
	Trie * children[ALPHABETS];

	// Constructor
	Trie(): is_terminal(false){
		memset(children, 0, sizeof(children));
	}

	// Delete all children
	~Trie(){
		for(int i = 0; i < ALPHABETS; ++i){
			if(children[i])
				delete children[i];
		}
	}

	void insert(const char * key){
		if(*key == '\0'){
			is_terminal = true;
		}
		else{
			int index = char_to_index(*key);

			if(children[index] == 0)
				children[index] = new Trie();
			children[index]->insert(key + 1);
		}
	}

	Trie* find(const char * key){
		if(*key == 0){
			return this;
		}

		int index = char_to_index(*key);
		if(children[index] == 0){
			return NULL;
		}

		return children[index]->find(key+1);
	}

	bool string_exist(const char * key){
		if(*key == 0 && is_terminal){
			return true;
		}

		int index = char_to_index(*key);
		if(children[index] == 0){
			return false;
		}
		return children[index]->string_exist(key + 1);
	}

};

int main (){

	Trie * root = new Trie();

	const char * words[5] = {"be", "bee", "can", "cat", "cd"};

	for(int i = 0; i < 5; ++i){
		printf("insert: %s\n", words[i]);
		root->insert(words[i]);
	}

	printf("\n");

	printf("%s: be\n", root->find("be") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: can\n", root->find("can") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: a\n", root->find("a") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: cat\n", root->find("cat") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: c\n", root->find("c") != 0 ? "Prefix Exist" : "Prefix Not Exist");

	printf("\n");

	printf("%s: c\n", root->string_exist("c") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: be\n", root->string_exist("be") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: bee\n", root->string_exist("bee") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: candy\n", root->string_exist("candy") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: cd\n", root->string_exist("cd") != 0 ? "String Exist" : "String Not Exist");

	delete root;

	return 0;
}


트라이(Trie)를 이용한 기본 문제

백준 온라인 저지 5052번

  • 전화번호 목록이 주어질 때 해당 번호들이 일관성이 있는지 확인하는 코드로 일관성이 있으면 YES를 없으면 NO를 출력하는 문제
  • 전화번호 목록들 중에 어떠한 번호가 다른 번호의 접두어가 되면 일관성이 없다고 판단한다. 다시 말해 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.
  • 링크: https://www.acmicpc.net/problem/5052


풀이 및 접근

  • 문자열을 처리하는 문제이며 나아가 접두어를 이용한 자료구조를 만들어야하기 때문에 트라이(Trie)를 사용해야함을 알 수 있습니다.
  • 방법1: 트라이에 모든 번호들을 저장하고 탐색하면서 문자열이 끝나기전에 is_terminal이 나오면 접두어가 존재하는 것이기 때문에 false를 반환해서 판단해줍니다.
  • 방법2: 트라이에 번호들을 추가하면서 현재 주어진 번호가 다른 번호의 접두어가 되는지 바로 판단합니다.


풀이 코드

방법1

  • 트라이에 모든 번호들을 저장하고 탐색하면서 문자열이 끝나기전에 is_terminal이 나오면 접두어가 존재하는 것이기 때문에 false를 반환해서 판단해줍니다.
#include <cstdio>
#include <cstring>

int char_to_index(char c){
	return c - '0';
}

struct Trie {

	bool is_terminal;
	Trie * next[10];
	Trie(): is_terminal(false) {
		memset(next, 0, sizeof(next));
	}

	~Trie() {
		for (int i = 0; i < 10; ++i) {
			if (next[i]) {
				delete next[i];
			}
		}
	}

	void insert(const char * key) {

		if (*key == '\0') {
			is_terminal = true;
		}
		else {
			int index = char_to_index(*key);
			if (next[index] == 0)
				next[index] = new Trie();
			next[index]->insert(key + 1);
		}
	}

	bool find(const char * key) {

		if (*key == '\0') return true;

		// Return false if there is already terminal node before string is the end.
		if (is_terminal) return false;

		int index = char_to_index(*key);
		return next[index]->find(key + 1);
	}
};

int main() {

	int t;
	char phone_books[10000][11];
	scanf("%d", &t);

	while (t--) {
		int n;
		scanf("%d", &n);

		Trie * root = new Trie();
		for (int i = 0; i < n; ++i) {
			scanf("%s", &phone_books[i]);
			root->insert(phone_books[i]);
		}

		bool is_valid = true;
		for (int i = 0; i < n; ++i) {

			if (root->find(phone_books[i]) == false) {
				is_valid = false;
				break;
			}
		}
        delete root;
		printf("%s\n", is_valid ? "YES" : "NO");
	}
	return 0;
}

방법2

  • 트라이에 번호들을 추가하면서 현재 주어진 번호가 다른 번호의 접두어가 되는지 바로 판단합니다.
#include <cstdio>
#include <cstring>

int char_to_index(char c){
	return c - '0';
}

struct Trie {

	bool is_terminal;
	Trie * next[10];

	Trie(): is_terminal(false) {
		memset(next, 0, sizeof(next));
	}

	~Trie() {
		for (int i = 0; i < 10; ++i) {
			if (next[i]) {
				delete next[i];
			}
		}
	}

	bool insert(const char * key) {

		if (*key == '\0') {
			is_terminal = true;
			return true;
		}
		else {
			// If it is already terminal node then there is a prefix match
			if(is_terminal == true) return false;

			int index = char_to_index(*key);

			if (next[index] == 0)
				next[index] = new Trie();

			// If next node is already exists and current's next is end of string then there is a prefix match
			else if(next[index] != 0 && *(key + 1) == '\0'){
				return false;
			}
			return next[index]->insert(key + 1);
		}
	}
};

int main() {

	int t;
	char phone_books[10000][11];
	scanf("%d", &t);

	while (t--) {
		int n;
		scanf("%d", &n);

		Trie * root = new Trie();

		bool ret = true;

		for (int i = 0; i < n; ++i) {
			scanf("%s", &phone_books[i]);

			if (ret == false) continue;

			ret = root->insert(phone_books[i]);

		}

		delete root;
		printf("%s\n", ret ? "YES" : "NO");
	}
	return 0;
}


참고자료

TWpower Reading time ~7 minutes

Implement trie and solve basic problem in C++.


Environment and Prerequisite

  • C++


What is Trie?

About Trie

  • Trie: Trie is a tree shape data structure for efficiently searching and storing strings.
  • From root to leaf nodes are strings which stored in trie data structure. We can distinguish end of string by adding terminal variable to each node.
  • By searching DFS method in above picture, we can find that to, tea, ted, ten, A, i, in, inn strings are stored in data structure.


Example of Trie

  • Orange color nodes are inserted strings.
  • be, bee, can, cat, cd are stored in trie.


Purpose of Trie

Purpose

  • The reason why we use trie is in time complexity of string searching. It is much more efficient than linear searching. However there is advantage that searching is efficient but also drawbacks that it saves all children pointer in each node so trie takes many spaces.
  • It can be used in searching keyword autocomplete, searching in dictionary and spelling checking. Reference is in References

Time Complexity

  • Consider L as longest string and M as total number of strings.
  • Creation time complexity: O(M*L), There are total M strings and each string only takes at most L time so it takes O(M*L). Insertion itself takes O(L).
  • Searching time complexity: O(L), It takes at most O(L) of time. Because it is tree structure.


Trie Implementation

Common

  • Only consider capital alphabets
#include <cstdio>
#include <cstring>

#define ALPHABETS 26

// Convert char to array index
// All are base on capital
int char_to_index(char c){
	return c - 'A';
}


Trie Code

  • is_terminal: It represents end of string.
  • void insert(const char * key): Add new string to trie structure.
  • Trie* find(const char * key): Check if trie has key(passed string argument) as prefix. If it has key as prefix then return end of key prefix node.
  • bool string_exist(const char * key): Check if trie has key(passed string argument). If it has key then return true. If not then return false.
struct Trie{

	bool is_terminal; // this represents end of string
	Trie * children[ALPHABETS];

	// Constructor
	Trie(): is_terminal(false){
		memset(children, 0, sizeof(children));
	}

	// Delete all children
	~Trie(){
		for(int i = 0; i < ALPHABETS; ++i){
			if(children[i])
				delete children[i];
		}
	}

	void insert(const char * key){
		if(*key == '\0'){
			is_terminal = true;
		}
		else{
			int index = char_to_index(*key);

			if(children[index] == 0)
				children[index] = new Trie();
			children[index]->insert(key + 1);
		}
	}

	Trie* find(const char * key){
		if(*key == 0){
			return this;
		}

		int index = char_to_index(*key);
		if(children[index] == 0){
			return NULL;
		}

		return children[index]->find(key+1);
	}

	bool string_exist(const char * key){
		if(*key == 0 && is_terminal){
			return true;
		}

		int index = char_to_index(*key);
		if(children[index] == 0){
			return false;
		}
		return children[index]->string_exist(key + 1);
	}

};


Main Function

  • Add check code in main function.
  • Main function checks whether trie works well.
int main (){

	Trie * root = new Trie();

	const char * words[5] = {"be", "bee", "can", "cat", "cd"};

	for(int i = 0; i < 5; ++i){
		printf("insert: %s\n", words[i]);
		root->insert(words[i]);
	}

	printf("\n");

	printf("%s: be\n", root->find("be") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: can\n", root->find("can") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: a\n", root->find("a") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: cat\n", root->find("cat") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: c\n", root->find("c") != 0 ? "Prefix Exist" : "Prefix Not Exist");

	printf("\n");

	printf("%s: c\n", root->string_exist("c") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: be\n", root->string_exist("be") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: bee\n", root->string_exist("bee") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: candy\n", root->string_exist("candy") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: cd\n", root->string_exist("cd") != 0 ? "String Exist" : "String Not Exist");

	delete root;

	return 0;
}


All codes

#include <cstdio>
#include <cstring>

#define ALPHABETS 26

// Convert char to array index
// All are base on capital
int char_to_index(char c){
	return c - 'A';
}

struct Trie{

	bool is_terminal; // this represents end of string
	Trie * children[ALPHABETS];

	// Constructor
	Trie(): is_terminal(false){
		memset(children, 0, sizeof(children));
	}

	// Delete all children
	~Trie(){
		for(int i = 0; i < ALPHABETS; ++i){
			if(children[i])
				delete children[i];
		}
	}

	void insert(const char * key){
		if(*key == '\0'){
			is_terminal = true;
		}
		else{
			int index = char_to_index(*key);

			if(children[index] == 0)
				children[index] = new Trie();
			children[index]->insert(key + 1);
		}
	}

	Trie* find(const char * key){
		if(*key == 0){
			return this;
		}

		int index = char_to_index(*key);
		if(children[index] == 0){
			return NULL;
		}

		return children[index]->find(key+1);
	}

	bool string_exist(const char * key){
		if(*key == 0 && is_terminal){
			return true;
		}

		int index = char_to_index(*key);
		if(children[index] == 0){
			return false;
		}
		return children[index]->string_exist(key + 1);
	}

};

int main (){

	Trie * root = new Trie();

	const char * words[5] = {"be", "bee", "can", "cat", "cd"};

	for(int i = 0; i < 5; ++i){
		printf("insert: %s\n", words[i]);
		root->insert(words[i]);
	}

	printf("\n");

	printf("%s: be\n", root->find("be") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: can\n", root->find("can") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: a\n", root->find("a") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: cat\n", root->find("cat") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: c\n", root->find("c") != 0 ? "Prefix Exist" : "Prefix Not Exist");

	printf("\n");

	printf("%s: c\n", root->string_exist("c") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: be\n", root->string_exist("be") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: bee\n", root->string_exist("bee") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: candy\n", root->string_exist("candy") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: cd\n", root->string_exist("cd") != 0 ? "String Exist" : "String Not Exist");

	delete root;

	return 0;
}


Trie Basic Problem

Baekjoon Online Judge 5052

  • Check if phone number list is in consistency. Print YES if it is in consistency if not then print NO.
  • In consistency means that any number is not prefix to other numbers.
  • Link: https://www.acmicpc.net/problem/5052


Solution and Method

  • It is string processing problem and also it contains prefix processing so using trie data structure is solution.
  • Solution 1: Insert all phone numbers to trie and search all phone numbers. If there is terminal node(is_terminal value is true) before end of the phone number, then return false.
  • Solution 2: Check inserted phone number is prefix to other numbers when insert into trie.


Solution Codes

Solution 1

  • Insert all phone numbers to trie and search all phone numbers. If there is terminal node(is_terminal value is true) before end of the phone number, then return false.
#include <cstdio>
#include <cstring>

int char_to_index(char c){
	return c - '0';
}

struct Trie {

	bool is_terminal;
	Trie * next[10];
	Trie(): is_terminal(false) {
		memset(next, 0, sizeof(next));
	}

	~Trie() {
		for (int i = 0; i < 10; ++i) {
			if (next[i]) {
				delete next[i];
			}
		}
	}

	void insert(const char * key) {

		if (*key == '\0') {
			is_terminal = true;
		}
		else {
			int index = char_to_index(*key);
			if (next[index] == 0)
				next[index] = new Trie();
			next[index]->insert(key + 1);
		}
	}

	bool find(const char * key) {

		if (*key == '\0') return true;

		// Return false if there is already terminal node before string is the end.
		if (is_terminal) return false;

		int index = char_to_index(*key);
		return next[index]->find(key + 1);
	}
};

int main() {

	int t;
	char phone_books[10000][11];
	scanf("%d", &t);

	while (t--) {
		int n;
		scanf("%d", &n);

		Trie * root = new Trie();
		for (int i = 0; i < n; ++i) {
			scanf("%s", &phone_books[i]);
			root->insert(phone_books[i]);
		}

		bool is_valid = true;
		for (int i = 0; i < n; ++i) {

			if (root->find(phone_books[i]) == false) {
				is_valid = false;
				break;
			}
		}
        delete root;
		printf("%s\n", is_valid ? "YES" : "NO");
	}
	return 0;
}

Solution 2

  • Check inserted phone number is prefix to other numbers when insert into trie.
#include <cstdio>
#include <cstring>

int char_to_index(char c){
	return c - '0';
}

struct Trie {

	bool is_terminal;
	Trie * next[10];

	Trie(): is_terminal(false) {
		memset(next, 0, sizeof(next));
	}

	~Trie() {
		for (int i = 0; i < 10; ++i) {
			if (next[i]) {
				delete next[i];
			}
		}
	}

	bool insert(const char * key) {

		if (*key == '\0') {
			is_terminal = true;
			return true;
		}
		else {
			// If it is already terminal node then there is a prefix match
			if(is_terminal == true) return false;

			int index = char_to_index(*key);

			if (next[index] == 0)
				next[index] = new Trie();

			// If next node is already exists and current's next is end of string then there is a prefix match
			else if(next[index] != 0 && *(key + 1) == '\0'){
				return false;
			}
			return next[index]->insert(key + 1);
		}
	}
};

int main() {

	int t;
	char phone_books[10000][11];
	scanf("%d", &t);

	while (t--) {
		int n;
		scanf("%d", &n);

		Trie * root = new Trie();

		bool ret = true;

		for (int i = 0; i < n; ++i) {
			scanf("%s", &phone_books[i]);

			if (ret == false) continue;

			ret = root->insert(phone_books[i]);

		}

		delete root;
		printf("%s\n", ret ? "YES" : "NO");
	}
	return 0;
}


References

TWpower Reading time ~1 minute

도커(Docker) 이미지 이름과 태그 목록을 awk과 tail 명령어를 이용해 가져오는 방법을 알아보자


환경

  • Linux 기반 시스템
  • Bash shell(/bin/bash)
  • Docker
  • awk, tail 명령어


도커(Docker) 이미지 이름 및 태그 가져오기

(기본) 도커 이미지 관련한 목록들 가져오기

$ sudo docker images
REPOSITORY          TAG                 IMAGE ID            CREATED             SIZE
nginx               latest              f68d6e55e065        2 weeks ago         109MB
nginx               stable              ac44715da54a        5 weeks ago         109MB
ubuntu              latest              7698f282e524        2 months ago        69.9MB
centos              centos7.5.1804      cf49811e3cdb        4 months ago        200MB
centos              latest              9f38484d220f        4 months ago        202MB
hello-world         latest              fce289e99eb9        6 months ago        1.84kB


도커 이미지들 ID 가져오기

  • -qa 옵션을 이용해 ID들 가져오기
  • -qa: 모든 이미지들을 보여주며 다른 정보들은 표시하지 않고 ID만 표시합니다.
$ sudo docker images -qa
f68d6e55e065
ac44715da54a
7698f282e524
cf49811e3cdb
9f38484d220f
fce289e99eb9


도커 이미지들 이름 가져오기

  • tail -n +2을 이용해 첫줄을 제외하고 두번째줄부터 목록들을 가져오기 위해 사용하며 첫줄은 각 열에 관한 설명이기 때문에 제외합니다.
  • awk를 이용해 첫번째 열에 대한 부분들만 가져옵니다.
  • $1는 첫번째 열을 의미합니다.
$ sudo docker images | tail -n +2 | awk '{print $1}'
nginx
nginx
ubuntu
centos
centos
hello-world


도커 이미지들 태그 가져오기

  • 위의 방법과 동일한 방법으로 awk명령어에서 변수만 $1에서 $2로 변경
  • $2는 두번째 열을 의미합니다.
$ sudo docker images | tail -n +2 | awk '{print $2}'
latest
stable
latest
centos7.5.1804
latest
latest


도커 이미지들을 태그와 함께 가져오기

  • 위의 방법과 동일한 방법으로 awk명령어에서 변수와 식을 조금 추가
$ sudo docker images | tail -n +2 | awk '{print $1":"$2}'
nginx:latest
nginx:stable
ubuntu:latest
centos:centos7.5.1804
centos:latest
hello-world:latest


참고자료

TWpower Reading time ~1 minute

Pring docker images name and tag list with using awk and tail command.


Environment and Prerequisite

  • Linux base system
  • Bash shell(/bin/bash)
  • Docker
  • awk, tail command


Get docker images name and tag list

$ sudo docker images
REPOSITORY          TAG                 IMAGE ID            CREATED             SIZE
nginx               latest              f68d6e55e065        2 weeks ago         109MB
nginx               stable              ac44715da54a        5 weeks ago         109MB
ubuntu              latest              7698f282e524        2 months ago        69.9MB
centos              centos7.5.1804      cf49811e3cdb        4 months ago        200MB
centos              latest              9f38484d220f        4 months ago        202MB
hello-world         latest              fce289e99eb9        6 months ago        1.84kB


Get docker images ID

  • Use -qa option to get IDs
  • -qa: Show all docker images and only show images ID
$ sudo docker images -qa
f68d6e55e065
ac44715da54a
7698f282e524
cf49811e3cdb
9f38484d220f
fce289e99eb9


Get docker images name

  • Use tail -n +2 command to exclude first line(first line is header of each column) and to print from second line.
  • Use awk to get first column.
  • $1 means first column
$ sudo docker images | tail -n +2 | awk '{print $1}'
nginx
nginx
ubuntu
centos
centos
hello-world


Get docker images tag

  • Use same awk command like above except modify variable from $1 to $2
  • $2 means second column
$ sudo docker images | tail -n +2 | awk '{print $2}'
latest
stable
latest
centos7.5.1804
latest
latest


Get docker images name with tag

  • Use same awk command like above except modify variable and expression
$ sudo docker images | tail -n +2 | awk '{print $1":"$2}'
nginx:latest
nginx:stable
ubuntu:latest
centos:centos7.5.1804
centos:latest
hello-world:latest


Reference