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

• [Programmers] 42586. 기능개발

  2023-03-28

  devFancy

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

  문제 링크

  성능 요약

  • 메모리: 79.3 MB, 시간: 0.45 ms

  구분

  • 코딩테스트 연습 > 스택／큐

  Answer Code1(23.03.28)

  import java.util.*;
  
  class Solution {
      public int[] solution(int[] progresses, int[] speeds) {
          Queue<Integer> q = new LinkedList<>();
          List<Integer> answerList = new ArrayList<>();
          
          for(int i = 0; i < speeds.length; i++) {
              double remain = (100 - progresses[i]) / (double) speeds[i];
              int date = (int) Math.ceil(remain); //Math.ceil: 올림
              
              if(!q.isEmpty() && q.peek() < date) { //3 < 5
                  answerList.add(q.size());
                  q.clear();
              }
              q.offer(date);
          }
          
          answerList.add(q.size());
          
          int[] answer = new int[answerList.size()];
          
          for(int i = 0; i < answer.length; i++) {
              answer[i] = answerList.get(i);
          }
          
          return answer;
      }
  }
  

  Read All

  ---

• [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

  ---