572. Subtree of Another Tree

-

 Easy  이고, 예전에 풀어봤었고, tree 문제는 잘 파악만 하면 몇줄 안에 해결되는 문제여서 좀 만만하게 생각하고 풀었는데. 대실패. 


  • 논리적으로 생각하기보다, 풀었던 기억을 되살리려 했다. Tree 문제의 경우, signature 로 주어진 함수를 자식 node 로 recursive 하게 호출하면 해결되는 문제들을 많이 봐서, 그런식으로 접근하려고 했는데 다양한 edge case  에 번번히 실패
  • 그리고 결국 실행이 되긴 했는데 LTE 떠서 실패

recursive 하게 호출 하려면, 그 함수가 정확히 뭘 하는지 구분 해야한다. 이번 문제에선 recursive 하게 호출하되,  두 TreeNode 가 정확히 matching 되는지 체크하는 함수는 또 따로 recursive 로 돌리는것이 관건이었다. 말하자면 2개의 recursiv 함수가 있는 것이다.  null 체크를 제외한 주요 호출은 아래처럼 된다. 

public boolean isSubtree(TreeNode s, TreeNode t) {
    return exactSame(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
}

private boolean exactSame(TreeNode s, TreeNode t){
    if(s.val==t.val){
        return exactSame(s.left, t.left) && exactSame(s.right, t.right);
    }
    return false;
}


Complexity

  • tree s  의 node 개수를 S, tree t 의 node 개수를 T  라 한다면, 각각의 s 의 노드를 root 로 하는 subtree가 tree t 와 exactly matching 하는지 확인 하므로,  최악의 경우 O(ST) 가 되는것 같 다. 

Comments

Post a Comment

Popular posts from this blog

삼성전자 무선사업부 퇴사 후기

-
"잠깐 드릴 말씀이 있는데요."  8월 어느날. 갑작스런 내 메신저에, 이미 예상을 하셨는지도 모르겠다. 몇주간 보인 내 근무 태도와, 먼저 메신저로 이런말을 하는 적이 한번도 없는 내가 면담을 요청한거나 마찬가지니. 갑자기 죄송스럽지만, 퇴사를 하겠다고 말씀을 드렸다. 신입사원으로 입사한지 6년 반만이었다.  삼성전자. 글로벌 기업이지만. 그래서일까. 우리나라에서 사기업,대기업 하면 가장 많이 사람들의 입에 오르며, 연일 다양한 언론의 주목을 다각도로 받는 기업. 명절에 가족 친지들을 만나면, 어르신들은 항상 요즘 삼성 어떠냐, 라고 물으셨었다. 내가 어떤지보다는. 무선사업부. 사람들 일상에 제일 가까운 핸드폰을 만들기도 하고, 내가 다니던 동안은 성과급 이야기에 무선 이야기가 늘 빠지지 않았다. 많은 사업부들이 있지만, 적어도 내가 입사 할때는 많은 개발직군은 무선이 최우선 지망이었다. 사내 댓상에서 조차, 삼성에는 전자와 후자가 있고, 전자에는 무선만 있습니다 라는 이야기를. 무선이 아닐때 들었었다. 그땐. 부럽기도 하고 어이가 없기도 했는데. 네임밸류  주위에선 잘다니는 회사를 왜 나오려고 하냐고. 그 안이 전쟁이라면 바깥은 지옥이라고. 이런 말들을 해줬었다. 누구나 아는 회사를 다니면 편하다. 아무도 뭐하는 곳이냐고 묻지않는다. 어렵게 설명하지 않아도 된다. 부모님도, 아들 어디 취직했어? 라고 물어오는 질문들에 대답이 편하셨을테다. 모르는 사람에게 소개할때도 편하다. 이직을 준비하는 과정에서도 그랬다. 이런점이 편했고, 알게 모르게 사람들의 이미지에 적어도 밥벌이는 하겠구나 하는 이미지였으리라. 하는 생각이 든다.  인지도 언론의 기사 제목 뽑는 능력 덕분에, 바깥의 사람들은 삼성 직원이 엄청난 연봉을 받는줄 안다. 그러나 안에서는 어떻게 하면 돈을 더벌까, 더 모을까 이런 이야기들을 한다. 집을 사지 못해 전세를얻고, 회사 앞 수많은 오피스텔에서 다니는 사원들중 본인 소유인 사람은 얼마나 되려나. 임직원중에 부자들...
Read more

개발자 커리어로 해외 취업, 독일 이직 프로세스

-
요즘은 국내 IT 기업도 이런 프로세스를 많이 따라가고 있는것 같다. 아래는 내가 해외 이직을 목표로 준비하면서 밟았던 몇몇 프로세스 경험을 종합했다. 0.  최초 컨택 크게 두가지 경로가 있는데, 링크드인에 프로필을 업로드하고 관리를 하다보면 연락이 오는경우. 그리고 내가 직접 링크드인에서 지원을 하거나 회사 홈페이지의 오픈 포지션에서 지원을 하는 경우이다.  링크드인에 프로필을 업로드하고 관리를 하다보면, 메세지를 받게 된다. 두가지의 경우가 있는데, 하나는 헤드헌터로부터 받는 경우, 그리고 하나는 채용하는 회사의 HR 로부터 받는 경우이다.   헤드헌터의 경우 채용하는 회사의 이름이나 구체적인 정보를 오픈하지는 않는다. 자신의 고객이 인재를 구하고 있는데 너의 프로필이 매칭되는것 같다, 괜찮다면 짧게 소개하고 이야기를 하고싶다, 라는 식이다. 회사의 리크루터가 직접 컨택하는 경우도 있는데, 이때는 보통 팀 소개도 간략히 해주기도 한다. 우리회사의 이런 팀에서 어떤인재를 찾고 있는데 너의 프로필이 잘 어울리는것 같다. 전화를 통해 자세한 이야기를 하고싶다, 라고 온다.  처음엔 몰랐지만, 몇번 메세지를 받다보니 내용은 복붙하고 이름만 바꿔서 뿌리는것 같은 느낌이다. 내가 조건을 필터링해서 구인공고를 검색할 수 있듯이, 리쿠르터들도 키워드를 검색해서 매칭되는 프로필들에게 뿌릴 수 있는것 같다. 운좋게 가고싶었던 회사 인사팀으로부터 연락이와서 정성스레 답장을 보냈는데, 그 뒤로 아무런 응답이 없는 경우도 있었다. 직접 지원을 하는 경우에도,  끝끝내 답장이 오지 않는 경우가 더 많았던것 같다.  1. 첫번째 인터뷰 첫번째 인터뷰는 주로 전화 혹은 스카이프로 짧게 진행되었다. 헤드헌터나 인사팀과 서로 소개하는 식이었다. 주로 받는 질문은 이런것이었다. - 왜 한국을 떠나려고 하는지 - 왜 삼성을 떠나려고 하는지 - 여기서 일하는데 비자를 갖추고 있는지 - 일을 한다면 언제부터 일할 수 있는지 그러면서 ...
Read more

코드리뷰에 대하여

-
우리 개발팀에는 DoR, DoD,DoP 라는 것이 있다. 이전에는 겪어본적이 없는것들이다. 나중에 따로 정리를 하겠지만, 우선은 코드리뷰에 대해 정리를 해보려고 한다.  이전 회사에서도 코드리뷰가 있었다. 처음부터 있었던건 아니고, 나중에 생겼다. 하지만 반드시 reviewer 가 accept 해야 commit 이 되는것도 일부 모듈에 대해서만 적용되었기 때문에 모든 code commit  에 대해 approval  이 필요하지 않았다. 때로는 빨리 검증 받고 배포해야 하는데 review 안되서 이게 걸림돌이라는 느낌이 강했고, 어떤 경우엔 담당자가 나 혼자여서 review 를 해줄 사람이 없었다. 모듈별로 주담당-백업이 나뉘어 있었는데, 백업 모듈에 대해 review 를 하기엔 잘 알지 못하고, 주담당인 모듈에 대해선 누군가 review  를 해줘야하는데 오래 걸리니 걸림돌이 되고. 백업이 없는 경우는 review 가 없는 상황. code reivew  에 대한 인식이 없다가 생긴것은 좋았으나, 그것이 개발에서 꼭 필요한 일부분이라기 보단 형식적인 통과의례로서 병목처럼 여겨졌다. 여기서는 아니다. review 를 받지 못하면 merge 되지 않는다. 우리 팀은 이제 7명. 옆 팀은 더 많다. 한 9명 되나? frontenf, backend 가 한 팀에 있고,  내 모듈, 네 모듈의 개념이 아닌, 우리 팀의 모듈이다. 그래서 특별히 어려운 티켓을 제외하면 누구나 develop, review, test 를 할 수 있게 되어있다.  reviewer  를 찾는 문화도 있다. daily  에서, 혹은 팀 채널에서 티켓 개발이 끝났으니 reviewer  를 찾고 있다, 라든지, 지금 할거 없는데  도움 필요한 사람? 이런식으로 나서기도 한다.  review 도 대충하지 않는다. 철저하다. 여러번 퇴짜를 맞았다. 나도 마찬가지로 적극적으로 의견을 내려고 한다. 아무리...
Read more