1 10 1
20

NO
10

2 10 3
16
32

YES
3

풀이

힙 자료구조를 구현해 풀이하면 된다.

우선순위 큐를 이용하여 풀이했다.

문제 자체가 힌트가 다 주어져있다. 가장 큰 키부터 망치로 떄려서 절반으로 줄인다고 했으니

단순히 최대힙에서 루트 노드 데이터를 가져와 절반으로 나누고 다시 넣어주면 된다.

그리고 반복문에서 때리려는 거인의 키가 1이거나 센티가 더 크다면 break 해주면 된다.

출력문에서 원하는 그대로 루트 노드의 데이터가 센티의 키보다 작다면 yes 와 count 를, 크다면 no와 루트노드의 값을 출력하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long N = Integer.parseInt(st.nextToken());
        long  H = Integer.parseInt(st.nextToken());
        long T = Integer.parseInt(st.nextToken());
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2)-> o2-o1);
        int count =0;
        for(int i=0; i<N; i++){
            queue.add(Integer.valueOf(br.readLine()));
        }
        for(int i=0; i<T;i++){
            if(queue.peek()<H || queue.peek()==1){
                break;
            }
            queue.add(queue.poll()/2);
            count++;
        }
        if(queue.peek()<H){
            System.out.println("YES");
            System.out.println(count);
        }
        else if(queue.peek()>=H){
            System.out.println("NO");
            System.out.println(queue.peek());
        }
    }
}

시간복잡도는 반복문이 상수회 돌고 있기 때문에 O(1) 로 표기할 수 있다.

2

어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.
"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
____"재귀함수가 뭔가요?"
____"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
____마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
____그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
________"재귀함수가 뭔가요?"
________"재귀함수는 자기 자신을 호출하는 함수라네"
________라고 답변하였지.
____라고 답변하였지.
라고 답변하였지.

풀이

해당 문제는 재귀함수를 사용해 풀이하면 된다...

아무래도 재귀는 어렵게 느껴져서 다른 사람의 풀이를 참고했다.

해당 문제의 언더바가 쌓이고 줄어드는 모습은 스택에 메소드가 쌓이는 모습을 상상해보면 어느정도 이해가 된다.

재귀함수는 메소드가 차곡차곡 쌓이고 조건에 다다를때부터는 차곡차곡 빠지기 때문이다.

이것을 활용해 정적변수 언더바를 선언하고 재귀 함수가 호출될때마다 언더바에 ____를 더해준다면 조건에 다다를때 ____가 더해진만큼 다시 줄어들게 된다.

솔직히 이렇게 작성하면서도 크게 와닿는 부분은 없다. 재귀 부분은 브론즈부터 다시 풀어봐야겠다는 생각이 든다.

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

public class a17478 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        System.out.println("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.");
        recur(N);
    }
    static String underbar ="";
    public static void recur(int N){
        String line = underbar;
        if(N == 0){
            System.out.println(line+"\"재귀함수가 뭔가요?\"");
            System.out.println(line+"\"재귀함수는 자기 자신을 호출하는 함수라네\"");
            System.out.println(line+"라고 답변하였지.");
            return;
        }
            System.out.println(line+"\"재귀함수가 뭔가요?\"");
            System.out.println(line+"\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.");
            System.out.println(line+"마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.");
            System.out.println(line+"그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"");
        underbar+="____";
        recur(N-1);
        System.out.println(line+"라고 답변하였지.");
    }
}

힙

힙이란 뭘까 ? 🤔

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

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

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

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

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

힙의 기본 동작

데이터 삽입

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

힙과 배열

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

마무리  🤔

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

5
12 7 9 15 5
13 8 11 19 6
21 10 26 31 16
48 14 28 35 25
52 20 32 41 49

35

풀이

해당 문제는 마찬가지로 우선순위 큐를 사용하는 문제이다.

단순히 N*N의 표가 주어지고, N번째 큰 수를 구하는 것이기 때문에

우선순위 큐를 큰 순서대로 정렬시키고, 말그대로 N-1번을 poll 시킨 후 println에 poll()를 넣어주면 된다.

우선순위 큐는 최소 최대값 탐색이 O(1)만에 가능하기 때문에 최댓값 우선으로 정렬한 후 출력하면 된다. (입력은 O(n)인데.. 이부분을 보완하면 좋을거같다는 생각이 든다 🤔)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class a2075 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2-o1);
        int N = Integer.parseInt(br.readLine());
        for(int i=0; i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                queue.add(Integer.valueOf(st.nextToken()));
            }
        }
        for(int i=0; i<N-1;i++){
            queue.poll();
        }
        System.out.println(queue.poll());

    }
}

3 1
3 2 6

16

4 2
4 2 3 1

19

풀이

해당 문제는 우선순위 큐로 풀이하면 되는 문제이고 x,y를 가장 작은 수로 가져와서 더한 후 덮어씌우면 된다.

우선순위 큐는 같은값으론 정렬이 안되고 기본 정렬이 작은것부터 내려오게 데이터를 삽입하기 때문에 단순히 우선순위 큐를 만들어주고 값을 넣어준후, 큐에서 수 2개를 poll 하고 더한 후 그 두 수를 다시 add 해주면 된다 .

여기서 주의해야할것은 데이터 타입을 long 으로 선언해주어야 한다.

단순히 int 로 한다고 치면 , 조건에 나와있는대로 더하면 범위를 넘어갈것이다.

해당 문제는 바로 최소값을 구할 수 있기 때문에 O(1)의 시간복잡도를 가진다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class a15903 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long N = Integer.parseInt(st.nextToken());
        long M = Integer.parseInt(st.nextToken());
        PriorityQueue<Long> queue = new PriorityQueue<>();
         st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            queue.add(Long.valueOf(st.nextToken()));
        }
        for(int i=0;i<M;i++) {
            long a = queue.poll();
            long b = queue.poll();
            queue.add(a + b);
            queue.add(a + b);
        }
        long sum = queue.stream().mapToLong(Long::longValue).sum();
        System.out.println(sum);
    }
}

트리구조

• 트리는 노드와 연결을 할 수 있는 브랜치를 이용해서 사이클을 이루지 않도록(순회하지 않도록) 구성한 데이터 구조이다.
• 트리는 넓은 범위로 정의를 한 것이고, 그중에서 익혀야 할 구조는 이진트리 구조이다. (탐색 알고리즘을 구현할 때 꼭 사용된다.)

알아둘 용어

• 노드 : 트리에서 데이터를 저장하는 기본 요소
• 루트 노드 : 최상단 노드
• 이진트리 : 노드의 최대 브랜치가 두 개이다. (두 개의 가지를 가지고 있다.)
• 이진 탐색 트리 : 왼쪽 노드는 윗 노드의 값보다 작은 값, 오른쪽 노드는 윗 노드의 값보다 큰 값이 들어간다.
• 어떤 노드의 상위 노드 → 부모 노드 / 어떤 노드의 하위 노드 → 자식 노드
• 최상단에 위치한 노드는 Level 0 , 두 번째는 Level 1 등 각각의 레벨에 번호를 붙인다.
• Depth : 트리에서 노드가 가질 수 있는 최대 Level (밑으로 얼마나 뻗어있느냐)
• 형제 노드 : 동일한 부모 노드를 가진 노드
• Leaf Node : 자식 노드가 하나도 없는 노드

이진 탐색 트리

이진트리와 정렬된 배 열간의 비교?

• 배열은 원하는 값을 찾으려면 값이 나올 때까지 돌아야 한다.
• 이진트리는 노드를 탐색해서 효율적으로 값을 검색한다.

이진 탐색 트리 구조/삽입/탐색 구현해보기

public class NodeMgmt{ 
	Node head = null;
	public class Node{ 
		Node left; //각각 오른쪽 왼쪽을 가리키는 브랜치를 가진다.
		Node right;
		int value;
		public Node(int data){
			this.value = data;
			this.left = null;
			this.right = null;
		}
	}
}

데이터 넣는 메서드 구현해보기

트리구조는 생각하지 못한 케이스가 많기 때문에 서브 케이스를 만들어서 각각을 구현하는 방식으로 구현하면 좋다.

public boolean insertNode(int data){
		//CASE1: 노드가 하나도 없을때
		if (this.head==null){
			this.head = new Node(data); //노드를 새로 만들어준다.
				} else{
				//CASE2: Node 가 하나 이상 있을때
				Node findNode = this.head; //노드를 가져와서 브랜치를 연결해준다.
				while(true){
				// CASE 2-1 : 현재 Node의 왼쪽에 Node가 들어가야 할때 (값이 작을때)
				if (data < findNode.value){
					if(findNode.left!=null){
						findNode = findNode.left; //노드가 존재하면 밑으로 점점 내려오면서 값을 넣어준다.
						}else{
					findNode.left = new Node(data);
					break;}
				// CASE 2-2 : 현재 Node 의 오른쪽에 Node가 들어가야 할때
					} else //값이 부모 노드보다 더 클때
						{if(findNode.right != null){
						findNode = findNode.right;
					}else{
					findNode.right = new Node(data);
					break;
					}
				}
			}
		return true;
		}
	}
}
// 밑으로 내려가면서 연결/혹은 삽입 해준다.
			
	

• 순서를 정리해보자
  • 이진트리를 구현할 때, 최상위 노드를 만들어주고 각 노드별로 왼쪽, 오른쪽을 가리키는 브랜치와 데이터를 넣을 객체 변수를 선언해준다.
  • 값을 저장할 시에는 만약에 루트 노드가 존재하지 않는다면 루트 노드에 새 노드를 참조시켜주고, 존재한다면 밑으로 내려오면서 값을 저장한다.
  • 밑으로 내려오는 로직은 값이 부모 노드보다 작으면 while문으로 각 브랜치로 내려와 노드가 존재한다면 참조시켜주고 존재하지 않는다면 연결해주는 식으로 노드가 존재하지 않을 때까지 Level을 늘리며 내려간다.

탐색 메서드 구현해보기

데이터를 가진 노드가 있는지/없는지를 체크하고 있으면 해당 노드를 리턴하도록 구현한다.

마찬가지로 각각의 케이스를 나눠서 구현하면 좋다.

public Node search(int data){
	if(this.head==null){ //트리가 비어있다면 null을 반환한다.
		return null;
		}else{
			Node findNode = this.head;
			while(findNode !=null){ //노드가 존재한다면 탐색을 실행한다.
				if(findNode.value == data){  //노드의 데이터가 검색을 원하는 데이터와 값이 같다면
					return findNode;
					}else if(data < findNode.value){ //데이터가 작다면 왼쪽 브랜치로 넘어가서 반복한다.
						findNode = findNode.left;
						} else{
							findNode = findNode.right;  //더 크다면 오른쪽 브랜치로 넘어가서 반복한다.
						}
				}
				return null;  //탐색했지만 없다면 null을 반환한다.
			}
		}
	}

이진 탐색 트리의 노드 삭제법

자식 노드가 없는 Leaf Node의 삭제

• 해당 노드의 부모 노드의 브랜치를 끊어버리면 된다.

자식 노드가 하나인 부모노드 삭제

• 해당 노드의 부모 노드의 브랜치를 해당 노드의 자식 노드로 연결해준다.

자식 노드가 두 개인 부모 노드 삭제

• 삭제할 노드의 오른쪽 노드에서 가장 왼쪽에 있는 (가장 값이 작은) 연결한다.

이진 탐색 트리 삭제 구현해보기

각각의 케이스로 나눠서 구현해보자. (삭제할 노드가 존재하는지도 체크해야 한다.)

삭제를 할 노드를 탐색하는 로직을 먼저 구현한다.

public boolean deleteNode(int value){
		boolean searched = false;
		Node currParentNode = this.head;
		Node currNode = this.head;
		// 노드가 하나도 없을때
		if(this.head ==null){
				return false;
				}
		// 노드가 하나만 있고, 해당 노드가 삭제할 노드일때
		else {
		if(this.head.value == value && this.head.left == null && this.head.right==null){
				this.head = null;
				return true;
				}
			while(currNode !=null){
				if(currNode.value = value){
					searched = true;
					break;
					}else if(value< currNode.value){
					currParentNode = currNode; //값이 일치하지 않고 작다면 왼쪽으로 내려간다.
					currNode = currNode.left 
				}else {
					currParentNode = currNode; //크다면 오른쪽으로 간다.
					currNode = currNode.right; 
			}
		}
		if(searched == false){
					return false;
			}
		}
	}
}
// 여기까지 실행된다면 currNode 에는 해당 데이터를 가지고 있는 노드가 담겨있다.
// currParentNode 에는 해당 노드의 부모 노드가 참조된다.

삭제할 노드가 Leaf Node 인 경우

• 단순히 삭제할 노드의 부모 노드의 자식 노드 연결을 끊어버리면 된다.

if(currNode.left == null && currNode.right) {
			if(value<currParentNode.value){ // 
				currParentNode.left =null; //branch 연결을 끊어준다.
				currNode = null;
				}else{
				currParentNode.right =null;
				currNode = null;
			}
return true;
}

삭제할 노드가 자식 노드를 한 개만 가지고 있을 경우

단순히 부모 노드의 연결을 자식 노드로 바꿔주면 된다.

• 삭제할 노드의 부모 노드의 데이터와 해당 노드의 데이터를 비교한다.
  • 해당 노드의 자식 노드가 왼쪽/오른쪽에 있는지 판단해 부모 노드의 데이터보다 값이 작다면 왼쪽에 , 크다면 오른쪽에 브랜치를 연결해준다.

// 자식 노드가 왼쪽에 있을경우
else if ( currNode.left!=null && currNode.right==null ){
		if(value < currParentNode.value){ //부모 노드보다 작다면 왼쪽에 연결한다.
		currParentNode.left = currNode.left;
		currNode = null;
			}
		else{
			currParentNode.right = currNode.left;
			currNode = null;
			}
		return true;
// 자식 노드가 오른쪽에 있을경우
else if ( currNode.left ==null && currNode.right !=null ){
		if(value < currParentNode.value){ //단순히 반대로 실행한다.
			currParentNode.left = currNode.right;
			currNode = null;
			}else{
				currParentNode.right = currNode.right;
				currNode = null;
			}
		return true;

삭제할 노드가 자식 노드를 두 개 가지고 있을 경우

• 삭제할 노드의 오른쪽 자식 중, 가장 작은 값을 삭제할 노드의 부모 노드가 가리키도록 한다.
  • 삭제할 노드가 부모 노드의 왼쪽에 있고, 삭제할 노드의 오른쪽 자식 중 , 가장 작은 값을 가진 노드의 자식 노드가 없을 때
  • 삭제할 노드가 부모 노드의 왼쪽에 있고, 삭제할 노드의 오른쪽 자식 중 , 가장 작은 값을 가진 노드의 오른쪽에 자식 노드가 있을 때
    • 가장 작은 값을 가진 노드의 자식 노드가 왼쪽에 있는 경우는 없다. 왜냐하면 왼쪽 노드가 있다는 것은 해당 노드보다 더 작은 값을 가진 노드가 있다는 뜻이기 때문이다.

이해하기 어렵다면 각각의 케이스를 외워버리는 것도 좋은 방법이다.

해당 부분은 너무 복잡해서 나중에 한번 더 수강할 예정입니다 🤔

시간 복잡도 

• 트리의 depth를 h라고 한다면 O(h)
• n개의 노드를 가진다면 o(logn) ⇒ 이진트리가 균형 잡혀 있을 때의 평균 시간 복잡도이다.
  • 한번 실행시마다 50%의 실행할 수도 있는 명령을 제거한다는 의미이다.
• 최악의 경우에 링크드 리스트 등과 동일한 성능을 보여준다. ( o(n))

느낀 점

• 이진트리가 무엇인지 알고는 있었으나 어떻게 구현하는지는 몰랐는데, 이번 기회가 1차적으로 구조가 이해가 되는 느낌입니다.
• 확실히 값을 저장하고 탐색할 때는 크게 힘든 게 없지만, 삭제할 때는 다른 자료구조와 달리 트리의 복잡도에 따라서 머리로만 그리는 것도 어려운 느낌입니다. 확실히 케이스가 많은 것 같습니다.
  • 별개로 해당 자료구조를 구현한 자바의 트리 API들이 해당 부분들을 다 구현해놓은 상태인지 궁금합니다. 찾아봐야겠습니다 🤔
• 단순히 탐색에 좋은 자료구조라고 생각해서 무분별하게 사용하다간 다른 자료구조보다 시간 복잡도가 더 나올 수 있는 상황이 생길 것 같습니다. 특히나 값이 같거나 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) 이다.