Leetcode에서 Find All Anagrams in a String 문제(Find All Anagrams in a String)를 풀다가 막혀서 discuss를 봤는데 Sliding Window Algorithm으로 풀이한 것이 있었다. 나중에 다시 볼 때 이해를 용이하게 하기 위해 간단히 그 방법을 남겨둔다.
알고리즘의 기본적인 접근법은 다음과 같다.
String에서 anagram의 조건은 다음과 같다.
이 알고리즘에서는 anagram에 존재하지 않는 character가 나타났는지를 확인하는 방식을 사용하지 않는다.
1번 조건은 HashMap과 counter를 이용하여 조건을 달성했는지 확인한다. Map에 character와 frequency를 넣고, 이것이 0에 도달하면 counter(초기값은 Map의 size(), 즉, anagram에 사용된 character 갯수)를 하나 줄여서 counter가 0에 도달하면 그 조건에 달성한 것으로 본다. 이때 주의할 점은 frequency는 negative값이 될 수 있다는 것이다. 예를 들어 anagram이 ‘aab’이고 입력 string이 ‘aaaaa’라면 ‘a’ entry의 값의 초기값은 2 이지만 마지막에 도달했을때는 -3이 되어 있을 것이다. 물론 counter는 0이 되어 있어 anagram에 사용된 횟수만큼의 ‘a’가 출현했음을 표시한다. 2번 조건은 start와 end의 길이를 anagram길이와 비교함으로써 달성한다. 예를 들어 비교하고자하는 string이 ‘aaab’이고 anagram이 ‘aab’이면 첫번째 a에서는 길이가 anagram의 길이보다 하나 더 길기 때문에 조건에 달성안되지만, start가 두번째 ‘a’인 경우에는 길이가 일치하게 된다.
위의 접근법을 이용한 알고리즘은 다음과 같다.
public class Solution {
public List<Integer> findAnagrams(String s, String t) {
List<Integer> result = new LinkedList<>();
if(t.length()> s.length()) return result;
Map<Character, Integer> map = new HashMap<>();
for(char c : t.toCharArray()){
map.put(c, map.getOrDefault(c, 0) + 1);
}
int counter = map.size();
int begin = 0, end = 0;
int head = 0;
int len = Integer.MAX_VALUE;
while(end < s.length()){
char c = s.charAt(end);
if( map.containsKey(c) ){
map.put(c, map.get(c)-1);
if(map.get(c) == 0) counter--;
}
end++;
while(counter == 0){
char tempc = s.charAt(begin);
if(map.containsKey(tempc)){
map.put(tempc, map.get(tempc) + 1);
if(map.get(tempc) > 0){
counter++;
}
}
if(end-begin == t.length()){
result.add(begin);
}
begin++;
}
}
return result;
}
}
Javascript가 지원하는 다양한 Object copy 방식 중 deepcopy를 지원하는 것은 무엇인지 확인해보자.
MDN에서는 다음과 같이 설명한다. 마치 deep copy가 가능한 듯한 설명이다.
간단히 아래와 같이 copy하면서 특정 프로퍼티 값을 업데이트 할 수 있다.
const object1 = {
a: 1,
b: 2,
};
const object2 = Object.assign({}, object1, {a: 100});
console.log(object2.a); //100
console.log(object2.b); //2
object나 array를 …를 이용해 프로퍼티들을 뽑아내고 object literal({})이나 array literal([])로 다시 object나 array를 구성하는 방식이다. 복사를 하면서 특정 프로퍼티의 값만 바꿀때 유용하다.
const object1 = {
a: 1,
b: 2,
};
const object2 = {...object1, a: 100}
console.log(object2.a); //100
console.log(object2.b); //2
const array1 = [1, 2, 3, 4];
const array2 = [...array1];
console.log(array2);//[1, 2, 3, 4]
위의 두가지 방식과는 달리 lodash 라이브러리를 이용하는 방식으로 lodash는 shallow copy를 지원하는 clone()과 deep copy를 지원하는 cloneDeep()이 있는데 여기서는 cloneDeep()만 살펴본다.
import * as _ from 'lodash';
const object1 = {
a: 1,
b: 2
};
const object2 = _.cloneDeep(object1);
object2.a = 100;
console.log(object2.a); //100
console.log(object2.b); //2
위의 3가지 방식이 deep copy를 지원하는지 테스트를 해보자. 방식은 다음과 같다.
다음과 같이 2단계 깊이의 object를 copy를 하고, 복사본의 프로퍼티의 값을 변경했을 때 원본의 값도 변경되었는지 보는 것이다. reference가 복사되어 원본의 값도 변한 경우 deep copy가 되지 않은 것이다.
const original = { a : {b : 2}};
아래와 같이 deep copy가 되지 못하여 original의 값도 변경되었다.
const original = { a : {b : 2}};
let copy = Object.assign({}, original);
copy.a.b = 100;
console.log(original.a.b); //expected: 2 but actual: 100
역시 아래와 같이 deep copy가 되지 못하여 original의 값도 변경되었다.
const original = { a : {b : 2}};
let copy = {...original};
copy.a.b = 100;
console.log(original.a.b); //expected: 2 but actual: 100
deep copy가 되어 original의 값은 변경되지 않았다.
const original = { a : {b : 2}};
let copy = _.cloneDeep(original);
copy.a.b = 100;
console.log(original.a.b); //2
deep copy가 필요한 경우 Object.assign()이나 spread(…) 를 사용하지 말고, lodash의 cloneDeep()을 사용하자.
예전에 uml 툴 소개 글을 쓴 적이 있는데, 온라인 UML 툴인 websequencediagrams을 써보고 Sequence diagram만은 websequencediagrams이 최고이고 그 이유는 마크다운스러운 접근법과 직관적인 사용법이 그 이유라고 했다. 그런데 오늘 plantuml을 사용해 보고 이게 제일 좋은 툴이라 생각했다. 왜냐하면 websequencediagrams인데 다운로드해서 로컬에서 사용가능하고, intelliJ에 plugin으로 사용가능하고, sequence diagram만이 아니라 자주 사용되는 다이어그램을 대부분 지원하고 있기 때문이다.
단점이라면 component의 위치지정(placement)이 맘대로 안된다는 것이다. 그냥 text 순으로 배치하면 좋겠는데 뒤죽박죽이 되게 배치해 버린다. (특히 유즈케이스 다이어그램) 그러함에도 그 장점이 너무 뛰어나기에 당분간 이 툴만 사용할 것 같다.
plantuml 설치는 homebrew를 이용해 하면 되고, intelliJ 플러그인은 설치하면 에러가 뜨는데 모두 구글링을 하면 쉽게 해결되는 것들이라서 지겨운 설명은 생략한다.
로그를 분석시 유용한 명령 조합을 살펴보자.
ls -al | sort -k 5 -nr | head -1 | cut -d " " -f 10 | xargs zmore
ls -al | sort -k 5 -nr | head -1 | cut -d " " -f 10 | xargs zgrep getConnection | wc -l
less AAA.txt | awk '{$NF="";sub(/[ \t]+$/,"")}1' > BBB.txt
BBB.txt: BBB.txt로 저장
한 폴더 안에 여러 gz파일이 있고, 각 gz파일안에 ERROR, WARN, INFO 등으로 마킹된 로그가 연속으로 나타나는데 에러의 경우 ‘Caused by. 에러 종류: 아이디’의 형태로 출력된다고 가정하자. 에러 종류별로 빈번한 것부터 빈번하지 않은 것까지를 정렬하고자 한다. 이를 위해서는 아이디를 제거하고 중복인 것의 갯수를 카운트해서 횟수 역순으로 정렬하자. 그리고 에러가 표시된 줄에 ‘batch’라는 단어가 들어가 있는 것은 무시해야 한다고 가정하자.
zgrep "Caused" *gz | grep -v batch | sed -e $'s/\|/\\\n/g' | awk '{$NF="";sub(/[ \t]+$/,"")}1' | sort | uniq -c | sort -nr > errors.txt
sed -e $’s/|/\\n/g’ : 줄안에 | 표시가 있으면 줄바꿈 |
errors.txt : 결과를 파일에 저장
로그를 분석하다보면 크기나 갯수 순으로 정렬해야 하는 경우가 많다. 이때 사용되는 sort 명령을 알아보자.
예제는 특정 폴더의 목록으로 하자.
Hochului-MacBook-Pro:Applications hochulshin$ ls -al
total 16
drwx------ 8 hochulshin staff 272 Dec 30 23:53 .
drwxr-xr-x+ 68 hochulshin staff 2312 Dec 30 23:53 ..
-rw-r--r--@ 1 hochulshin staff 6148 Aug 11 2015 .DS_Store
-rw-r-----@ 1 hochulshin staff 0 Aug 6 2015 .localized
drwx------@ 6 hochulshin staff 204 Dec 15 22:41 Chrome Apps.localized
drwxr-xr-x 3 hochulshin staff 102 Dec 6 21:45 SourceTree.app
drwxr-xr-x 3 hochulshin staff 102 Mar 19 2016 Ubuntu Linux 14.04 Desktop Applications.app
drwxr-xr-x 3 hochulshin staff 102 Jul 30 19:33 Ubuntu Linux Applications.app
sort는 기본적으로 줄의 맨 앞 글자를 알파벳 순으로 오름 정렬한다. 아래와 같이 특수 문자가 알파벳보다 우선되어 정렬됨을 알 수 있다.
Hochului-MacBook-Pro:Applications hochulshin$ ls -al | sort
-rw-r-----@ 1 hochulshin staff 0 Aug 6 2015 .localized
-rw-r--r--@ 1 hochulshin staff 6148 Aug 11 2015 .DS_Store
drwx------ 8 hochulshin staff 272 Dec 30 23:53 .
drwx------@ 6 hochulshin staff 204 Dec 15 22:41 Chrome Apps.localized
drwxr-xr-x 3 hochulshin staff 102 Dec 6 21:45 SourceTree.app
drwxr-xr-x 3 hochulshin staff 102 Jul 30 19:33 Ubuntu Linux Applications.app
drwxr-xr-x 3 hochulshin staff 102 Mar 19 2016 Ubuntu Linux 14.04 Desktop Applications.app
drwxr-xr-x+ 68 hochulshin staff 2312 Dec 30 23:53 ..
total 16
-r은 내림차순 정렬이다.
Hochului-MacBook-Pro:Applications hochulshin$ ls -al | sort -r
total 16
drwxr-xr-x+ 68 hochulshin staff 2312 Dec 30 23:53 ..
drwxr-xr-x 3 hochulshin staff 102 Mar 19 2016 Ubuntu Linux 14.04 Desktop Applications.app
drwxr-xr-x 3 hochulshin staff 102 Jul 30 19:33 Ubuntu Linux Applications.app
drwxr-xr-x 3 hochulshin staff 102 Dec 6 21:45 SourceTree.app
drwx------@ 6 hochulshin staff 204 Dec 15 22:41 Chrome Apps.localized
drwx------ 8 hochulshin staff 272 Dec 30 23:53 .
-rw-r--r--@ 1 hochulshin staff 6148 Aug 11 2015 .DS_Store
-rw-r-----@ 1 hochulshin staff 0 Aug 6 2015 .localized
-k는 줄의 맨 앞 문자가 아닌 공백을 기준으로 n번째 문자를 기준으로 정렬하는 것이다.
예제에서 9번째가 파일 이름이므로 파일이름으로 오름차순으로 정렬하려면 -k9옵션을 주면 된다.
Hochului-MacBook-Pro:Applications hochulshin$ ls -al | sort -k9
total 16
drwx------ 8 hochulshin staff 272 Dec 30 23:53 .
drwxr-xr-x+ 68 hochulshin staff 2312 Dec 30 23:53 ..
-rw-r--r--@ 1 hochulshin staff 6148 Aug 11 2015 .DS_Store
-rw-r-----@ 1 hochulshin staff 0 Aug 6 2015 .localized
drwx------@ 6 hochulshin staff 204 Dec 15 22:41 Chrome Apps.localized
drwxr-xr-x 3 hochulshin staff 102 Dec 6 21:45 SourceTree.app
drwxr-xr-x 3 hochulshin staff 102 Mar 19 2016 Ubuntu Linux 14.04 Desktop Applications.app
drwxr-xr-x 3 hochulshin staff 102 Jul 30 19:33 Ubuntu Linux Applications.app
-g은 알파벳 순이 아닌 숫자 크기 순으로 정렬하는 것이다. -k와 결합하여 적용해서 크기순으로 정렬해보자.
Hochului-MacBook-Pro:Applications hochulshin$ ls -al | sort -k5 -g
total 16
-rw-r-----@ 1 hochulshin staff 0 Aug 6 2015 .localized
drwxr-xr-x 3 hochulshin staff 102 Dec 6 21:45 SourceTree.app
drwxr-xr-x 3 hochulshin staff 102 Jul 30 19:33 Ubuntu Linux Applications.app
drwxr-xr-x 3 hochulshin staff 102 Mar 19 2016 Ubuntu Linux 14.04 Desktop Applications.app
drwx------@ 6 hochulshin staff 204 Dec 15 22:41 Chrome Apps.localized
drwx------ 8 hochulshin staff 272 Dec 30 23:53 .
drwxr-xr-x+ 68 hochulshin staff 2312 Dec 30 23:53 ..
-rw-r--r--@ 1 hochulshin staff 6148 Aug 11 2015 .DS_Store
비교하는 값이 동일할 경우 제거하는 옵션이다.
Hochului-MacBook-Pro:Applications hochulshin$ ls -al | sort -k5 -g -u
total 16
-rw-r-----@ 1 hochulshin staff 0 Aug 6 2015 .localized
drwxr-xr-x 3 hochulshin staff 102 Dec 6 21:45 SourceTree.app
drwx------@ 6 hochulshin staff 204 Dec 15 22:41 Chrome Apps.localized
drwx------ 8 hochulshin staff 272 Dec 30 23:53 .
drwxr-xr-x+ 68 hochulshin staff 2312 Dec 30 23:53 ..
-rw-r--r--@ 1 hochulshin staff 6148 Aug 11 2015 .DS_Store
이제 위에서 다룬 모든 옵션을 사용하여 크기 역순으로 중복을 제거하면서 파일을 정렬해보자.
Hochului-MacBook-Pro:Applications hochulshin$ ls -al | sort -k5 -g -u -r
-rw-r--r--@ 1 hochulshin staff 6148 Aug 11 2015 .DS_Store
drwxr-xr-x+ 68 hochulshin staff 2312 Dec 30 23:53 ..
drwx------ 8 hochulshin staff 272 Dec 30 23:53 .
drwx------@ 6 hochulshin staff 204 Dec 15 22:41 Chrome Apps.localized
drwxr-xr-x 3 hochulshin staff 102 Dec 6 21:45 SourceTree.app
-rw-r-----@ 1 hochulshin staff 0 Aug 6 2015 .localized
total 16
로그를 분석하다보면 call stack이 한 줄에 쭉 나와있는 경우가 있다. 이를 보기 편하게 만들기 위해서는 call stack의 API call 사이의 |를 줄바꿈 문자로 변경해야 한다. 이를 포함해 빠르게 문자열을 바꾸는 방법을 알아보자.
예제로할 파일 aaa.txt의 내용이 다음과 같다고 가정하자.
Hochului-MacBook-Pro:~ hochulshin$ cat sample.txt
1234|5678|90123
ABCD|EFG
abcd|efg
sed는 다른 리눅스 명령과 결합하여 문자열을 빠르게 변경할 수 있는 도구이다.
기본 명령은 다음과 같다.
Hochului-MacBook-Pro:~ hochulshin$ cat sample.txt | sed -e 's/ABCD/XXX/g'
1234|5678|90123
XXX|EFG
abcd|efg
패턴은 regex를 이용해서도 가능하다.
Hochului-MacBook-Pro:~ hochulshin$ cat sample.txt | sed -e 's/[Aa]..[Dd]/XXX/g'
1234|5678|90123
XXX|EFG
XXX|efg
sed의 적용 범위를 줄 번호로 지정할 수 있다. 1번째 줄과 두번째 줄만 적용하는 경우 다음과 같이 할 수 있다.
Hochului-MacBook-Pro:~ hochulshin$ cat sample.txt | sed -e '1,2 s/[Aa]..[Dd]/XXX/g'
1234|5678|90123
XXX|EFG
abcd|efg
sed에서 ‘'와 같은 문자를 처리하기 위해서는 다음과 같이 $를 넣어야 한다.
참고로 줄바꿈은 ‘\\n’이다.
Hochului-MacBook-Pro:~ hochulshin$ cat sample.txt | sed -e $'s/|/\\\n/g'
1234
5678
90123
ABCD
EFG
abcd
efg