leeso

문제

https://leetcode.com/problems/find-all-anagrams-in-a-string/

s문자열이 주어졌을 때, p문자열이 모두 들어있는 모든 첫번째 인덱스를 return해준다.

풀이

1. p의 길이가 s의 길이보다 긴 경우, return 해준다.

2. 먼저 알파벳의 크기만큼 s와 p 배열을 만들어준다.

3. 문자의 길이가 정해져있으니까 왼쪽, 오른쪽 ++ 해주어 숫자를 비교해준다..

Java Code

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if (p.length() > s.length()) return new ArrayList<>();

        int[] sHash = new int[26];
        int[] pHash = new int[26];

        for (int i = 0; i < p.length(); i++) {
            pHash[p.charAt(i) - 'a']++;
            sHash[s.charAt(i) - 'a']++;
        }

        int left = 0, right = p.length();
        List<Integer> ans = new ArrayList<>();

        while (right < s.length()) {
            if (Arrays.equals(sHash, pHash)) ans.add(left);

            char acquire = s.charAt(right);
            sHash[acquire - 'a']++;

            char discard = s.charAt(left);
            sHash[discard - 'a']--;

            left++; right++;
        }
        
		//	두 배열이 같은 경우 left값을 정해준다.
        if (Arrays.equals(sHash, pHash)) ans.add(left);

        return ans;
    }
}

문제

https://leetcode.com/problems/validate-binary-search-tree/

트리가 주어지는데, 이 트리가 이진트리인지 판단한다.

풀이

1. 특정 노드를 기준으로, 왼쪽 자식 노드는 (B)는 부모노드(A)보다 값이 작아야하고, 오른쪽자식노드(C) 보다 커야한다.

B의 왼쪽 자식노드(D)는 B보다 작아야하며, 오른쪽 자식노드(E)는 B보다 커야되고, A보다는 작아야한다.

1. root 부터 isValidBST 함수를 실행한다.

* 이때 노드의 범위가 정수 범위이므로, Long 값의 최대, 최소값을 세팅해준다.

2. isValidBST() 함수에서 node가 null이면, true이다.

3. node의 값이 min 보다 작거나 같다면 false를 반환한다.

4. node의 값이 max 보다 크거나 같다면 false를 반환한다.

5. 왼쪽 자식노드가 유효한지 확인한다.

5-1.

isValidBST() 함수를 재귀 호출한다. 인자로 왼쪽 자식노드 node.left, 최소값으로 min 그리고 최대값으로 현재 노드의 값 node.val을 전달한다. (왼쪽 자식노드는 부모 노드보다 작아야 하기 때문에 최대 한계값으로 현재 노드의 값을 전달한다.)
5-2. 왼쪽 자식노드가 유효하지 않다면 false를 반환한다.

6. 오른쪽 자식노드가 유효한지 확인한다.
6-1. isValidBST() 함수를 재귀 호출한다. 인자로 오른쪽 자식노드 node.right, 최소값으로 현재 노드의 값 node.val 그리고 최대 한계값 max를 전달한다. (오른쪽 자식노드는 부모 노드보다 커야 하기 때문에 최소 한계값으로 현재 노드의 값을 전달한다.)
6-2. 오른쪽 자식노드가 유효하지 않다면 false를 반환한다.

7. 최종적으로 모든 노드가 유효하다면 true를 반환한다.

Java Code

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isBST(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    boolean isBST(TreeNode root,long min,long max)
    {
        if(root == null)
            return true;
        
        if(root.val <= min || root.val >= max)
            return false;
        
        boolean left = isBST(root.left,min,root.val);
        boolean right = isBST(root.right,root.val,max);
        return left && right;
    }
}

문제

https://leetcode.com/problems/linked-list-cycle-ii/

linked list에 head가 주어진다. 이때 사이클이 시작하는 노드를 return 한다. 없는 경우 null을 return 한다.

풀이

1. 사이클인지 판별한다.

2. 사이클인 경우 사이클의 진입부분을 찾는다.

"토끼와 거북이 알고리즘" 을 사용한다.

1. 거북이를 시작지점으로 옮긴다.

2. 토끼와 거북이가 만날 때까지 한칸씩 이동한다.

3. 둘이 만나는 지점이 사이클의 시작지점이다.

D : 시작점(head)에서 사이클 시작점까지의 거리
M : 사이클 시작점에서 둘이 만난 지점까지의 거리
R : 둘이 만난 지점부터 다시 사이클 시작점까지의 거리

거북이 = D + M
토끼 = 2(D + M) = 2D+2M

토끼는 거북이의 2배씩 움직이므로, 위의 수식은 쉽게 구할 수 있다.

이때 토끼가 이동한 경로는 시작점 -> 사이클 시작점 -> 둘이 만난 곳 -> 사이클 시작점 -> 둘이 만난 곳이 된다.

이제 토끼가 이동한 경로를 D,M,R을 사용하여 표시를 해보면 다음과 같다.

토끼 = D + M + R + M = D + R + 2M

이제 토끼가 이동한 거리를 표현한 수식이 2개가 되었다. 이 두 개를 가지고 R과 D의 관계를 계산할 수 있다.

2D + 2M = D+R+2M 
-> D = R

D = R, 즉, "시작점부터 사이클 시작점 까지의 거리"는 "둘이 만난 곳 부터 다시 사이클 시작점까지 가는 거리"와 같다.

이 알고리즘이 옳다는 것을 증명했으므로, 이를 사용해 구현하게 되면 어렵지 않게 문제를 해결할 수 있다.

Java Code

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null || head.next==null) return null;
        
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
               while(head!=slow){
                   head=head.next;
                   slow=slow.next;
               }
               return slow;
            }
        }
        return null;
    }
}

문제

https://leetcode.com/problems/first-bad-version/

n개의 버전[1, 2, ..., n]이 있고 첫 번째 불량 버전을 찾은 그 이후 다음 버전은 모두 불량이다.

버전이 잘못된지 여부를 반환하는 API bool isBadVersion(version) 이 제공된다.

API에 대한 호출 수를 최소화하여 첫 번째 불량 버전을 찾는 기능을 구현해야 된다.

풀이

1. 전체 버전에서 첫 번째와 마지막 버전을 지정한다.
2. 가장 중앙 버전의 불량여부를 확인한다.
3. 중앙 버전이 불량인 경우,
   1. 해당 제품의 이전 제품이 정상인 경우, 중앙값 리턴,
   2. 이전 제품도 불량이라면, 중앙제품 이전 제품을 마지막 버전으로 설정한다.
4. 중앙 버전이 정상인 경우 중앙 다음 제품을 최초 제품으로 설정한다.

Java Code

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        if(n==1) return 1;        
        
        int begin = 1;
        int end = n;
        int mid = (end - begin) / 2 + begin;
        
        while(true){
            if(isBadVersion(mid)){
                
                if(!isBadVersion(mid-1)){
                    return mid;
                } else {
                    end = mid-1;
                    mid = (end-begin) / 2 + begin;
                }
                
            } else {
                
                begin = mid+1;
                mid = (end-begin) / 2 + begin;
                
            }
        }
    }
}

문제

https://www.acmicpc.net/problem/1316

공부한 부분

최초 생각 : 해시에다가 일단 넣고, 스택에다가 넣은거 빼면서 비교하자
1. 해시셋에 입력, 이때 스택에도 같이 넣어줌 (스택 사용해서 문자 연속으로 나오는것 확인을 위해)

2. 스택에서 알파벳을 한개씩 빼서 이전의 알파벳과 같은지 검사해서 다른 경우의 개수를 세어준다.

3. 이때의 개수가 해시셋에 있는 개수와 같으면 그룹단어

Java Code

package week2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Stack;
import java.util.StringTokenizer;

public class boj1316 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        //해시에다가 일단 넣고, 스택에다가 넣은거 빼면서 비교?

        int answer = 0;
        for (int i = 0; i < N; i++) {

            st = new StringTokenizer(br.readLine());

            String input = st.nextToken();
            char[] arr = input.toCharArray();
            HashSet<Character> hs = new HashSet();
            Stack<Character> stack = new Stack<>();

            for (int j = 0; j < arr.length; j++) {
                hs.add(arr[j]);
                stack.push(arr[j]);
            }

            char temp1 = stack.pop();
            int count = 0;

            while (!stack.isEmpty()){

                char temp2 = stack.pop();
                if (temp1 != temp2) {
                    count++;
                    //System.out.println("count "+count);
                }
                temp1 = temp2;
            }

            if (count == hs.size()-1) {
                answer++;
            }


        }
        System.out.println(answer);
    }
}

2022년 10월 ~ 2022년 12월 까지 NEXTSTEP에서 진행하는 우아한테크캠프PRO에 참여했다.

2개월간 진행했지만, 길다면 길고 미션을 진행할 때는 너무 짧게만 느껴졌던,, 작년 가장 열심히 살았던 2개월인 것 같아 회고 및 후기를 적어본다.

1. 참여계기

우연히 지인이 직장인을 위한 교육이 있다고 우테캠Pro 링크를 보내줘서 알게 되었다.

클린코드, TDD, 리팩토링 등 평소에 관심있던 부분에 대해 실제로 강의를 해주고, 리뷰어분들이 코드리뷰를 해준다고 했다.

3년차가 넘어가면서 성장하기 위한 무언가를 해야겠다고 생각했을 때 교육과정에 대해 보게 되어 수강해야겠다고 결심했다.

우테캠Pro는 신청서 작성 + 프리코스 미션을 진행한 후 교육생을 선발된다.

자소서 작성하듯.. 열심히 신청서를 작성했고, 프리코스 미션도 열심히 해서 제출한 후 선발되었다.

2. 커리큘럼과 주차별 후기

일단 1,2,3,5,7 주차는 코드작성 위주의 강의와 미션이다.

1주차 때 TDD가 어떤 것인지, 미션하는 사이클에 대해 경험한다.

2주차 때는 JPA를 활용해서 코드를 작성한다. 3,4,5 주차때는 단계별 요구사항에 대해 직접 구현하고 테스트코드 작성하는 방법을 익힌다.

7주차는 이미 작성되어있는 코드를 리팩터링하고, 테스트코드도 작성한다. 7주차가 가장 어렵고 시간이 많이 소비되었다.

4,6,8 주차는 인프라적인 요소들도 같이 진행하는 미션이였다.

실제로 서버를 구성하고, 부하테스트도 직접 진행했다. 가장 기억남는건 AWS를 사용하면서 인프라 구성에 대해 이해하고 서브넷, 프라이빗 클라우드, 퍼블릭 클라우드, nginx, docker와 같은 내용을 직접 사용해보고 실습해본 것이였다. 실제 회사에서는 인프라팀에서 따로 해주는 경우가 많다보니 내부적인 내용은 전부 이해하지 않고 있었는데 회사에서도 어떻게 구성되어 있겠구나 다시 한번 생각해 볼 수 있어서 좋았다. 그렇지만 이때 미션이 가장 익숙하지 않아서 힘들었다. 

3. 결론

8주간 꾸준히 미션을 하고, 막판에 크리스마스때까지 미션을 하면서 너무 빡세긴 했지만.. 수료했다!!!! 

기존에 회사에서 작성하던 코드 외에 TDD, ATDD를 해보면서 기존의 개발 방법에 대해 다시 돌아보게 되면서 새로운 관점을 얻게 된 것 같다. 주변에 개발자가 있다면 무조건 추천하고 싶다. 내가 혼자 학습하고 연습해보고 싶었던 내용들을 직접 구현해보고, 실력있는 리뷰어분들께 리뷰받을 수 있어서 너무 좋았다. 책을 보면서 일방적으로 학습하는 것이 아니라 코드를 직접 짜보고 어떻게 구현하는게 더 좋을지 리뷰어분과 이야기도 나누면서 개발할 수 있어서 좋은 경험이였다. 마지막 날 포비님이 해주셨던 말씀중에 인상깊은 말이 있어서 다이어리에 적어두었다. 가끔 내가 나태해질 때 읽어보려고 한다.

아이템 15. 클래스와 멤버의 접근 권한을 최소화하라

잘 설계된 컴포넌트 : 클래스 내부 데이터와 내부 구현 정보를 외부 컴포넌트로부터 얼마나 잘 숨겼는가.

구현과 API를 깔끔히 분리하는 것 

--> 정보 은닉, 캡슐화

정보 은닉의 장점

1. 시스템 개발 속도를 높인다.

- 여러 컴포넌트를 병렬로 개발할 수 있다.

2. 시스템 관리 비용을 낮춘다.

- 각 컴포넌트를 더 빨리 파악하여 디버깅할 수 있고, 다른 컴포넌트로 교체하는 부담도 적다.

3. 정보 은닉 자체가 성능을 높여주지는 않지만, 성능 최적화에 도움을 준다.

4. 소프트웨어 재사용성을 높인다.

- 그 컴포넌트와 함께 개발되지 않은 낯선 환경에서도 유용하게 쓰일 가능성이 크다.

5. 큰 시스템을 제작하는 난이도를 낮춰준다.

- 시스템 전체가 완성되지 않은 상태에서도 개별 컴포넌트의 동작을 검증할 수 있기 때문에

자바는 정보 은닉을 위한 다양한 장치를 제공한다.

접근 제어 메커니즘은 클래스, 인터페이스, 멤버의 접근성을 명시한다.

각 요소의 접근성은 그 요소가 선언된 위치와 접근 제한자(private, protected, public)로 정해진다.

기본 원칙 : 모든 클래스와 멤버의 접근성을 가능한 한 좁혀야 한다.

- 소프트웨어가 올바로 동작하는 한 가장 낮은 접근 수준을 부여해야 한다.

가장 바깥이라는 의미의 톱레벨 클래스와 인터페이스에 부여할 수 있는 접근 수준은 package-private과 public 두 가지이다. 

public : 공개 API

package-private : 해당 패키지 안에서만 사용

멤버(필드, 메서드, 중첩 클래스, 중첩 인터페이스)에 부여할 수 있는 접근 수준은 4가지 이다.

1. private : 멤버를 선언한 톱레벨 클래스에서만 접근할 수 있다.

2. package-private : 멤버가 소속된 패키지 안의 모든 클래스에서 접근할 수 있다. 

3. protected : package-private의 접근 범위를 포함하며, 이 멤버를 선언한 클래스의 하위 클래스에서도 접근할 수 있다.

4. public : 모든 곳에서 접근할 수 있다.

클래스의 공개 API를 세심히 설계한 후, 그 외의 모든 멤버는 private으로 만든다.

같은 패키지의 다른 클래스가 접근해야하는 멤버만 package-private으로 풀어준다.

private과 package-private멤버는 모두 해당 클래스의 구현에 해당하므로 공개 API에 영향을 주지 않는다.

- Serializable을 구현한 클래스에서는 의도치 않게 공개 API가 될 수도 있다.

public 클래에서는 멤버의 접근 수준을 package-private 바꾸는 순간 그 멤버에 접근할 수 있는 대상 범위가 넓어진다.

클래스의 protected 멤버는 공개 API이므로 영원히 지속돼야 한다.

protected 멤버의 수는 적을수록 좋다.

멤버 접근성을 좁히지 못하게 방해하는 제약 : 상위 클래스의 메서드를 재정의할 때는 그 접근 수준을 상위 클래스에서보다 좁게 설정할 수 없다.

-> 상위 클래스으 ㅣ인스턴스는 하위 클래스의 인스턴스로 대체해 사용할 수 있어야 한다는 규칙(리스코프 치환 원칙)을 지키기 위해 필요하다.

테스트만을 위해 클래스, 인터페이스, 멤버를 공개 API로 만들어서는 안된다.

-> 테스트 대상과 같은 패키지에 두면 package-private 요소에 접근할 수 있기 때문

public 클래스의 인스턴스 필드는 public이 아니어야 한다.

클래스에서 public static final 배열 필드를 두거나 이 필드를 반환하는 접근자 메서드를 제공해서는 안된다.

//보안 허점이 숨어있다.
public static final Thing[] VALUES = {...};

//방법1.
private static final Thing[] PRIVATE_VALUES = { ... };
public static final List<Thing> VALUES =
    Collections.unmodifiableList(Arrays.asList(PRIVATE_VALUES));

//방법2.
private static final Thing[] PRIVATE_VALUES = { ... };
public static final Thing[] values() {
    return PRIVATE_VALUES.clone();
}

방법 1. public 배열을 private로 만들고 public 불변 리스트를 추가하는 것

방법 2. 배열을 private로 만들고 그 복사본을 반환하는 public 메서드를 추가하는 방법(방어적 복사)