지금의 기록이 미래의 자산이 된다.

• [Programmers] 42888. 오픈채팅방

  2023-03-26

  devFancy

  Algorithm
  • 성능 요약
  • 구분
  • Answer Code1(23.03.26)
  • 문제 풀이 - Answer Code1
  • Review
  • Reference

  문제 링크

  성능 요약

  • 메모리: 155 MB, 시간: 105.47 ms

  구분

  • 코딩테스트 연습 > 2019 KAKAO BLIND RECRUITMENT

  Answer Code1(23.03.26)

  import java.util.*;
  
  class Solution {
      public String[] solution(String[] record) {
          Map<String, String> idMap = new HashMap<>(); // (아이디 - 닉네임) Map
          int count = 0; // Change할 때마다 +1 증가
          
          for(int i = 0; i < record.length; i++) {
              String [] info = record[i].split(" ");
              
              if(info[0].equals("Leave")) {
                  continue;
              } else if(info[0].equals("Enter")) {
                  idMap.put(info[1], info[2]);
              } else {
                  idMap.put(info[1], info[2]);
                  count++;
              }
          }
          
          String[] answer = new String[record.length - count];
          int idx = 0;
          
          for(int i = 0; i < record.length; i++) {
              String [] info = record[i].split(" ");
              String nickname = idMap.get(info[1]);
              
              if(info[0].equals("Enter")) {
                  answer[idx++] = nickname + "님이 들어왔습니다.";
              } else if(info[0].equals("Leave")) {
                  answer[idx++] = nickname + "님이 나갔습니다.";
              }
          }
          
          return answer;
      }
  }
  

  문제 풀이 - Answer Code1

  • 아이디와 닉네임을 Map을 선언하여 idMap이라는 변수에 저장하고, 닉네임을 변경할 때마다 메시지에서 제외할 count를 증가하는 메서드를 구현한다.

  Map<String, String> idMap = new HashMap<>(); // (아이디 - 닉네임) Map
  int count = 0; // Change할 때마다 +1 증가
  
  for(int i = 0; i < record.length; i++) {
      String [] info = record[i].split(" ");
      
      if(info[0].equals("Leave")) {
          continue;
      } else if(info[0].equals("Enter")) {
          idMap.put(info[1], info[2]);
      } else {
          idMap.put(info[1], info[2]);
          count++;
      }
  }
  

  • 닉네임에 대한 탐색을 마치고 나서 return하기 위해 메시지에 담을 배열인 answer 선언한다.

  • 여기서 닉네임 변경한 것에 대해 채팅방 메시지에 표시되지 않으므로 메시지에서 제외할 count 만큼의 크기로 초기화한다.

  • 배열의 인덱스를 지정할 변수 idx도 선언한다.

  String[] answer = new String[record.length - count];
  int idx = 0;
  

  • 각 값을 공백을 기준으로 split하고, 들어오고 나가는 경우에 대해서만 메시지를 작성하여 저장한다.

  • 닉네임은 아이디를 key를 이용하여 idMap에서 value를 가져와서 사용한다.

  for(int i = 0; i < record.length; i++) {
      String [] info = record[i].split(" ");
      String nickname = idMap.get(info[1]);
      
      if(info[0].equals("Enter")) {
          answer[idx++] = nickname + "님이 들어왔습니다.";
      } else if(info[0].equals("Leave")) {
          answer[idx++] = nickname + "님이 나갔습니다.";
      }
  }
  

  Review

  • HashMap의 개념과 문제를 제대로 이해한다면 충분히 풀 수 있는 문제였다.

  • 해당 문제를 풀면서, HashMap의 개념을 제대로 깊이 이해할 필요가 생겼다는 계기가 되었다.

  Reference

  • [프로그래머스] 오픈채팅방 - Java
  Read All

  ---

• [Programmers] 17687. [3차] n진수 게임

  2023-03-24

  devFancy

  Algorithm
  • 성능 요약
  • 구분
  • Answer Code1(2023.03.24)

  문제 링크

  성능 요약

  • 메모리: 74.5 MB, 시간: 2.43 ms

  구분

  • 코딩테스트 연습 > 2018 KAKAO BLIND RECRUITMENT

  Answer Code1(2023.03.24)

  ```java class Solution { public String solution(int n, int t, int m, int p) { StringBuilder convert = new StringBuilder(); StringBuilder answer = new StringBuilder();

  Read All

  ---

• 기본적인 그래프 기법 : DFS, BFS

  2023-03-23

  devFancy

  DataStructure
  Read All

  ---

• 그래프

  2023-03-21

  devFancy

  DataStructure
  • 그래프

  이 글의 코드와 정보들은 책을 공부하며 정리한 내용을 토대로 작성하였습니다.

  그래프

  • 그래프는 트리보다 복잡하다.

  • 사실 트리가 그래프의 한 종류에 속한다.

  • 하지만 트리와 달리 한 노드에 부모가 여럿 있을 수 있고 사이클이 만들어질 수 있다는 점이 다르다.

  • 그리고 노드 자체가 아닌 노드 사이의 링크에도 값 또는 가중치가 있을 수 있다.

  • 이렇게 다른 노드를 가리키는 기능 외에 별도의 정보를 담을 수 있는 링크를 에지(edge)라고 부른다.

  • 그래프를 수학적 기호로 표현하면 $G = (V, E)$ 으로 쓰이고, V는 Vertex의 약자로 꼭짓점(=Node)을 의미하고, E는 Edge의 약자로 간선을 의미한다.

  • 에지에는 당방향 에지와 양방향 에지가 있으며, 단방향 에지가 들어 있는 그래프는 방향성 그래프(directed graph), 양방향 에지만 들어 있는 그래프는 무방향성 그래프(undirected graph)라고 부른다.

  • [그림 6-4]에는 방향성 그래프, [그림 6-5]에는 무방향성 그래프가 나와 있다.

  

  • 그래프 자료구조에서 많이 쓰이는 방법 가운데 하나로 인접 리스트(Adjacency list) 또는 인접 행렬(Adjacency Matrix)를 들 수 있다.

  • 인접 리스트는 그래프의 각 노드에 인접한 노드들을 연결 리스트로 표현하는 자료구조다.

  

  • n개의 vertics와 e개의 edges를 가진 무방향성 그래프인 G에서 edge의 최대 수는 O(n+e) 이다.

  • 인접 행렬은 노드 개수만큼의 차원 수로 만들어지는 정사각형 형태의 2차원 배열로 표현하는 자료구조다.

  

  • n개의 vertics와 e개의 edges를 가진 무방향성 그래프인 G에서 edge의 최대 수는 O(n^2) 이다.
  Read All

  ---

• 트리

  2023-03-20

  devFancy

  DataStructure
  • 트리

  이 글의 코드와 정보들은 책을 공부하며 정리한 내용을 토대로 작성하였습니다.

  트리

  • 트리는 0개 이상의 다른 노드에 대한 레퍼런스가 들어 있는 노드(데이터 원소)로 구성된다.

  • 트리를 그림으로 표현하면 아래와 같다.

  

  • 연결 리스트에서와 마찬가지로 노드는 구조체 또는 클래스로 표현되며, 트리는 포인터 또는 레퍼런스만 있다면 어떤 언어로든 구현할 수 있다.

  • 객체지향 언어에서는 보통 노드의 공통적인 부분을 하나의 클래스로 정의하고, 노드에 들어가는 데이터를 위해 서브클래스를 만들어서 사용한다.

  • 실제 코딩을 할 때는 children은 비공개(private)로 선언하고 그 배열을 건드리기 위한 메서드만 공개하는 방법을 써야 할 것이다.

  • 정수가 저장되는 클래스를 메서드와 생성자를 모두 제대로 갖춘 자바로 만든다면 다음과 같은 식의 코드를 쓰면 된다.

  public abstract class Node {
      private Node[] children;
      
    public Node( Node[] children) {
        this.children = children;
    }
    
    public int getNumChildren() {
        return children.length;
    }
    
    public Node getChildren(int index) {
        return children[index];
    }
  }
  
  public class IntNode extends Node {
      private int value;
      
      public IntNode (Node [] children, int value) {
          super(children);
          this.value = value;
      }
      
      public int getValue() {
          return value;
      }
  }
  

  • 다음은 [그림 6-1]을 참고해서 트리와 관련된 용어들을 몇 가지 정리했다.

  

  • 부모(Parent) : 다른 노드를 가리키는 노드는 그 노드의 부모가 된다. 루트를 제외한 모든 노드에는 부모가 하나씩 있다.

    • [그림 6-1]에서 B는 D, E, F의 부모 노드가 된다.

  • 자식(Child) : 루트를 제외한 모든 노드는 그 노드를 가리키는 노드의 자식이 된다.

    • [그림 6-1]에서 D, E, F는 B의 자식 노드가 된다.

  • 자손(Descendant) : 특정 노드로부터 자식 노드로 이어지는 경로를 따라 도달할 수 있는 모든 노드는 그 특정 노드의 자손이다.

    • [그림 6-1]에서 D, E, F, H, I, J, K는 모두 B의 자손이다.

  • 조상(Ancestor) : 어떤 노드를 자손으로 삼고 있는 노드는 모두 그 노드의 조상이다.

    • 예를 들어 A, B, D는 모두 I의 조상이다.

  • 잎(Leaves) : 자식이 없는 노드를 잎이라고 부른다. G, H, I, K는 모두 잎이다.

  Read All

  ---