So when I die (the [first] I will see in (heaven) is a score list).
[ first in ] ( first out ).
Half Moon tonight (At least it is better than no Moon at all].
A rope may form )( a trail in a maze.
Help( I[m being held prisoner in a fortune cookie factory)].
([ (([( [ ] ) ( ) (( ))] )) ]).
 .
.

yes
yes
no
no
no
yes
yes

풀이

해당 문제는 스텍 자료구조를 이용해서 풀이하면 된다.

똑같이 구현을 했는데도 메소드로 추출해서 풀이했을때와 단순히 메인에 다 때려박았을때 메인은 20퍼센트에서 계속 틀렸다고 떴었다.

왜인지 아직까지도 이해가 안간다 (?)

여기서 제일 신경써야 할것은 ([)] 와 같이 ()() [][] 이런식으로 마무리되는 문자열만 yes 를 출력해야 된다는 것 이다.

그리고 마지막에도 스택이 비어있을때 yes 아니면 no 로 체크를 한번 더해준다. (해당 부분때문에 오답이 나온건가 싶기도 하다.)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;

public class a4949 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while(true){
            String str =br.readLine();
            if(str.equals(".")){
                break;
            }
            System.out.println(check(str));
        }
    }
    public static ArrayDeque<Character> deque = new ArrayDeque<>();
    public static String check(String str){
        deque.clear();
        for(int i=0; i<str.length();i++){
            char c = str.charAt(i);
            if(c=='(' || c=='[') {
                deque.push(c);
            }else{
                if(c==')'){
                    if(deque.isEmpty() || deque.peek()!='('){
                        return "no";
                    }else{
                        deque.pop();
                    }
                }else if(c==']'){
                    if(deque.isEmpty() || deque.peek()!='['){
                        return "no";
                    }else{
                        deque.pop();
                    }
                }
            }
        }
        if(deque.isEmpty()){
            return "yes";
        }else{
            return "no";
        }
    }

해당 문제의 시간 복잡도는 반복문이 상수회 실행되고 한 반복문 안에 조건문이 존재하기 때문에 O(n) 으로 표기하나..? 해당 부분은 배우지 않아서 아직 모르겠다. (정리된 글을 보아도 조건문이 존재할때의 시간복잡도는 아직 이해가 덜 되었다.)

힙

힙이란 뭘까 ? 🤔

• 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진트리이다.
  • 브랜치가 최대 2개이다. (이진)
  • 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리이다. (완전)
• 최소값과 최소값을 찾으면 O(logn)이 걸린다.
  • 배열에서 최소값과 최대값을 찾으려면 O(n)이 걸리기때문에 힙이 훨씬 빠르다.
  • 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용된다.

힙과 이진탐색 트리의 공통점과 차이점  🤔

• 차이점 ⇒ 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모노드, 그 다음 오른쪽 자식 노드 값이 가장 크지만 힙은 무조건 왼쪽부터 값을 집어넣는다.
  • 이진 탐색트리는 검색을 위한 구조이고, 힙은 최소값 최댓값을 구하기 위한 구조이다.
• 공통점 ⇒ 모두 이진트리이다. (최대 브랜치가 2개이다.)

최소 힙이냐, 최대 힙이냐에 따라서 추가적인 조건이 존재한다.

• 최대 힙 → 각 노드의 값이 자식 노드의 값보다 크거나 같다.
• 최소 힙 → 각 노드의 값이 자식 노드의 값보다 작거나 같다.
  • 따라서 가장 크거나 작은 값은 루트 노드에 존재하게 된다.

힙의 기본 동작

데이터 삽입

• 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워지는 형태로 삽입이 된다.
• 최대힙이라면 조건이 하나 더 존재한다. 항상 부모 노드가 자식노드보다 큰 값을 가져야한다.
  • 채워진 노드 위치에서 부모 노드보다 값이 클 경우 부모 노드와 위치를 바꿔준다. (계속해서 큰 값을 가진다면 루트노드로 갈때까지 위치를 바꾼다.)
  데이터 삭제
• 보통 삭제는 루트 노드를 삭제하는 것이 일반적이다.
  • 보통은 최소값/최대값 을 알기 위해서 힙을 사용하기 때문에 루트 노드를 삭제하는것이 일반적이다.
• 루트 노드가 삭제될시에, 남아있는 데이터의 오른쪽의 끝에 존재하는 노트를 루트 노드로 위치를 변경하고 자식노드와 값을 비교해서 다시 루트노드에 최소/최대값을 배치한다.

힙과 배열

• 힙에서는 보통 데이터를 배열에 저장한다.
  • 계산을 통해서 자식 노드와 부모 노드를 찾아낸다.
• 배열은 보통 인덱스가 0부터 시작하지만, 힙을 구현할때는 0번은 null로 만든 후 1번 인덱스부터 루트 노드의 값을 저장한다.
  • 부모노드와 자식 노드는 인덱스 번호만 계산 할 수 있으면 된다.
    • 자식노드의 인덱스 번호를 2로 나눈 몫을 부모 노드의 인덱스 번호로 사용한다.
    • 왼쪽 자식 노드의 인덱스 번호는 부모 노드의 인덱스 번호에 2를 곱한 값을 사용한다.
    • 오른쪽 자식 노드의 인덱스 번호는 부모 노드의 인덱스 번호에 2를 곱한 후 1을 더한 값이 사용된다.

마무리  🤔

• 우선순위 큐를 사용할때 힙과 기존 이진탐색 트리의 차이점을 설명 못했었는데, 이제 좀 설명을 할 수 있을것 같습니다.
  • 최대힙 같은 경우에는 자식노드가 부모노드보다 값이 작거나 같아야 합니다.
  • 이진 탐색 트리같은 경우에는 검색을 위한 자료구조이고, 완전 이진트리는 최소값 최대값 을 구하기 위한 자료구조라는것을 알게되었습니다.

9 77
11 33 11 77 54 11 25 25 33

11 11 11 33 33 25 25 77 54

풀이

해당 문제는 해시 자료구조를 이용해 풀이하는 문제이다. 

C의 값이 과연 필요할까? 싶다. 단순 N의 값만 가지고 문제를 풀이했다.

빈도순서대로 정렬해 출력하는 문제이지만 , 가장 신경써야 할 문제는 빈도가 같다면 먼저 등장한 숫자가 앞으로 나오도록 정렬하는 것이다.

그래서 순서를 저장하는 linked hashmap 을 사용하면 된다!

일단 전체적인 흐름은 Integer,Integer 를 갖는 해시 맵을 만들어주고 각 값을 집어넣는다. 이때 put 메소드에 벨류 자리는 getOrDefault 로 키가 존재한다면 밸류를 가져와 +1를 시켜주고, 존재하지 않는다면 0을 입력해주는 것이다.

인덱스를 저장하기 때문에 단순히 다른 작업을 거칠 필요 없이 compareTo 재정의를 벨류값으로 내림차순으로 정의해주면 된다.(빈도가 많을수록 앞으로 오기 때문에)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;

public class a2910 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int C = Integer.arseInt(st.nextToken());
        HashMap<Integer,Integer> map = new LinkedHashMap<>();
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            int n = Integer.parseInt(st.nextToken());
            map.put(n,map.getOrDefault(n,0)+1);
        }
        Set<Map.Entry<Integer,Integer>> set = map.entrySet();
        set = set.stream().sorted((o1, o2) -> o2.getValue() - o1.getValue()).collect(Collectors.toCollection(LinkedHashSet::new));
        StringBuilder sb = new StringBuilder();
        set.forEach(o->{
            for(int i=0; i<o.getValue();i++){
                sb.append(o.getKey()).append(" ");
            }
        });
        System.out.println(sb);
    }
}

3 4
ohhenrie
charlie
baesangwook
obama
baesangwook
ohhenrie
clinton

2
baesangwook
ohhenrie

풀이

해당 문제는 해시 자료구조를 이용해 풀이하는 문제이다.

단순히 듣도 보도 못한 사람을 구하는 문제이므로, 듣지 못한 사람이 보지 못한 사람 명단에도 존재할때 해당 이름을 리스트에 넣어놓고 정렬후 출력하면 된다.

해시 자료구조는 키를 입력하고 같은 값이 존재한다면 벨류를 바꾸고 존재하지 않는다면 데이터를 해당 인덱스에 저장하지만, 해시 셋은 단순 벨류가 없이 키만 존재하기 때문에 같은 키가 존재한다면 false 를 리턴한다. 

set.add(name) 이 false 일시에 배열에 add 하고 출력하도록 풀이했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class a1764 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        List<String> arr= new ArrayList<>();
        HashSet<String> set = new HashSet<>();
        for(int i=0; i<N; i++){
            set.add(br.readLine());
        }
        for(int i=0; i<M; i++){
            String str = br.readLine();
            if(!set.add(str)){
                arr.add(str);
            }
        }
       arr.sort(String::compareTo);
        System.out.println(arr.size());
        for (String s : arr) {
            System.out.println(s);
        }
    }
}

시간 복잡도는 단순 상수회만 반복하기 때문에 O(1) 이다.

해쉬테이블 🤔

• 키에 데이터를 맵핑할 수 있는 데이터구조이다.
  • 키와 값을 어떻게 맵핑할까? → 해쉬 펑션에 키를 넣으면 키를 저장할 수 있는 주소를 리턴을 해준다.(인덱스) 해당 주소에 키에 해당하는 값을 저장한다.
  • 해시 펑션은 뭘까? → 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수이다. (데이터가 어떻든간에 고정된 길의의 값으로 리턴해준다.)
• 해쉬테이블에 저장한다면 어떤 키던간에 해시 펑션을 이용하면 해당 데이터의 위치를 리턴해주기 때문에 빠른 탐색 속도를 보여준다.
• 해쉬테이블 ⇒ 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
  • 슬롯 : 해쉬 테이블에서 한 개의 데이터를 저장할 수 있는 공간
• 전체적인 흐름 ? → 키와 데이터를 입력하면 해쉬 펑션은 입력된 키를 바탕으로 인덱스 번호를 반환해 해당 데이터가 저장될 수 있는 공간을 배열로 할당한 후, 키에 따른 데이터를 저장한다.
  • 탐색시에는 키를 입력하면 해쉬 펑션은 인덱스를 리턴해주기 때문에 불필요한 탐색을 할 필요 없이 데이터의 유무를 판단해 해당 인덱스의 데이터로 바로 접근이 가능하다.

해쉬 테이블의 장단점과 주요 용도 🤔

• 장점
  • 데이터 저장/읽기 속도가 빠르다.(처음부터 탐색할 필요 없이 해당 인덱스에 바로 접근이 가능하기 때문에)
  • 해쉬는 키에 대한 데이터가 있는지 확인이 쉽다.(중복 확인이 쉽다.)
• 단점
  • 일반적으로 저장 공간이 좀 더 많이 필요하다.
  • 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요하다.
• 주요 용도
  • 검색이 많이 필요한경우
  • 저장,삭제,읽기가 빈번한경우
  • 캐쉬 구현시 (중복 확인이 쉽기 때문이다.)

해쉬 충돌(컬리젼)을 위한 알고리즘 (키는 다르지만 해쉬 펑션으로 인한 반환값이 같을때) 🤔

체이닝 기법 (순회를 하기 때문에 시간이 좀 걸린다.)

• 개방 해슁 또는 오픈 해슁 기법중 하나이다. (해쉬 테이블 저장공간 외의 공간을 활용하는 기법 /그래서 오픈이라는 개념을 가진다.)
• 충돌이 일어나면 링크드 리스트를 사용해서 데이터를 추가로 뒤에 연결시켜서 저장한다.
• 기존의 슬롯에 키와 연결용 next 객체를 새로 멤버변수로 선언해준다.
• 이미 해당 슬롯이 있다면? 해당 슬롯을 참조하는 prevSlot / findSlot 객체를 생성해 key가 같다면 벨류 값을 바꾸고, 다르다면 순회를 하면서 null을 찾을때까지 포인터를 연결 후 새로 슬롯을 생성해 데이터를 저장한다.

리니어 프로빙 기법

• 폐쇄 해슁 기법중 하나이다. (해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법이다. / 해쉬 테이블 저장공간 안에서 해결을 하기 때문에 폐쇄 라는 용어가 붙는다.)
• 충돌이 일어나면 해당 해쉬 어드래스의 다음 어드래스부터 맨 처음 나오는 빈 공간에 저장하는 기법이다.
  • 저장공간 활용도를 높이기 위한 기법이다.
• 마찬가지로 key를 함께 저장한다.
• 해당 슬롯에 데이터가 존재한다면? 계속 뒤 인덱스로 순회를 하면서 null이 나올때까지 탐색 후 null이 존재하지 않는다면 저장을 하지 않는다.

해쉬 테이블 시간복잡도 🤔

• 일반적인 경우 (컬리젼이 없다면) O(1)
• 최악의 경우 (컬리전이 모두 발생하는 경우) O(n)
• 리니어 프로빙, 체이닝 기법 둘 다 동일하다.

해쉬 테이블의 경우는 일반적인 경우를 기대하고 작성한다.

검색에서 해쉬 테이블의 사용 예

• 배열에 데이털르 저장하고 검색할때는 O(n) 이지만 이상적인 해쉬 테이블 케이스에서 데이터를 검색할때는 O(1)이다. → 배열은 무조건 반복문을 이용하지만 해쉬 테이블은 해쉬펑션이 인덱스를 리턴해주기 때문에 O(1)이다.

마무리 🤔

• 단순히 아무생각없이 사용하던 해쉬맵이 이름과 밸류를 통으로 저장해버리는 줄 알았는데 기본 원리는 키는 해쉬펑션으로 인하여 인덱스를 반환해주면 밸류를 가져오지만, 충돌이 일어날 시에 대비하기 위해서 키도 같이 저장하는구나! 를 알게되었습니다.
• 해쉬 테이블이 어떻게 동작하는지 알 수 있게 되었습니다.
• 단순히 해쉬 테이블 자료구조를 사용하는 API를 이용하는것이 아니라 적절한 사용이 맞는지 판단해 최대한 충돌이 일어나지 않는 상황에서 해쉬 자료구조를 택한다면 좋은 성능을 발휘할 것 같습니다.
• 체이닝 기법, 리니어 프로빙 기법이 해쉬 충돌 해결방안 이긴 하지만 전체적으로 돌아가는 구조를 보니 그냥 충돌 자체가 안나는게 최적의 상황인것 같습니다. 자주 충돌이 날 수 있는 상황이라면 다른 자료구조를 사용하는게.. 🤔
• 적절한 해쉬 펑션을 어떻게 만드는지가 가장 중요한것 같습니다. 해당 부분에 대해서 공부할 필요가 있다고 느껴졌습니다.