<h3>코딩 테스트 준비 일지 7 일차</h3><ul class="tight" data-tight="true"><li>응시 사이트 :<a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/"> LeetCode</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/problems/deepest-leaves-sum/description/">Deepest Leaves Sum</a></li><li>난이도 : 중하</li></ul>Given the <code spellcheck="false">root</code> of a binary tree, return the sum of values of its deepest leaves.<img src="https://image.until.blog/sin0105/article/1717236308772" alt="until-380">Example 1:<pre spellcheck="false"><code>Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15</code></pre>Example 2:<pre spellcheck="false"><code>Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 19</code></pre>&nbsp;Constraints:<ul class="tight" data-tight="true"><li>The number of nodes in the tree is in the range <code spellcheck="false">[1, 104]</code>.</li><li><code spellcheck="false">1 &lt;= Node.val &lt;= 100</code></li></ul><h3>문제 풀이 접근</h3>이전에 타겟넘버와 같은 DFS / BFS 유형을 볼 때 이런 느낌의 트리노드들을 어떻게 더할지, 이런 부분에 대해서 이해하고 넘어가서 비교적 쉬웠다 시간으로만 보면 31분 정도 걸렸다. 이것저것 하다보니...그림과 제목을 보자마자, 아! 이거 그냥 끝단에 위치한 변수끼리 더해주면 되네! 라는 느낌을 받았고, 문제와 입출력으로 확신했다.문제 해결 플로우는 아래와 같다. 1. root 가 주어지고 왼쪽 오른쪽을 노드로 입력해서 준다. 즉, Depth 값에 대한것은 줄 생각이 없다. 2. 고로 내가 Depth 값을 유추하는 로직을 돌려서 Depth 값을 가진 Value와 매칭해서 저장해 놓는다. 3. 이후 데이터 세팅이 끝나면 내 Depth 값이랑 동일한 value 가져와서 더해서 리턴한다. 이 정도 까지 풀이 유추를 했으면 문제 다풀었다.<h3>정답 작성 코드 ( C# )</h3><pre spellcheck="false"><code>/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * public int val;
 * public TreeNode left;
 * public TreeNode right;
 * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
public class Solution {
public static int s_iFindDepth; // 깊이 값
public List&lt;KeyValuePair&lt;int, int&gt;&gt; depthValueList = new List&lt;KeyValuePair&lt;int, int&gt;&gt;(); // 깊이값에 대한 Value 값을 나타내기 위한 변수

public int DeepestLeavesSum(TreeNode root)
{
 int resValue = 0;
 s_iFindDepth = 0; // 으로 초기화

 DFS(root, 0);

 var findPair = depthValueList.FindAll(rhs =&gt; rhs.Key == s_iFindD
 for (int i = 0; i &lt; findPair.Count; ++i)
 {
 var Value = findPair[i].Value;
 resValue += Value;
 }

 return resValue;
}

public void DFS(TreeNode node, int depth) // 깊이 값
{
 if (s_iFindDepth &lt; depth)
 {
 s_iFindDepth = depth; // Depth 값이 더 크다면 
 }

 int value = node.val;

 depthValueList.Add(new KeyValuePair&lt;int, int&gt;(depth, value));

 if (node.left != null)
 DFS(node.left, depth + 1);

 if (node.right != null)
 DFS(node.right, depth + 1);
}
</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1717237207192" alt="until-381"><h3>프로젝트에서 바로 돌릴 수 있는 코드 ( C# )</h3>TC1 번에 한해서 돌려볼 수 있는 코드다. 위의 구성만 바꾸면 2도 되고 다른 구성도 가능하다.<pre spellcheck="false"><code>using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Runtime.InteropServices;
using System.Security.Authentication;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Web;
using System.Xml.Linq;/*URL : https://leetcode.com/problems/deepest-leaves-sum/
*/namespace CodingTestProj
{
internal class Program
{
static void Main(string[] args)
{
// TC1.
// Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
// Output: 15 TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
TreeNode node7 = new TreeNode(7);
TreeNode node8 = new TreeNode(8); node1.left = node2;
 node1.right = node3;

 node2.left = node4;
 node2.right = node5;

 node3.left = null;
 node3.right = node6;

 node4.left = node7;
 node4.right = null;

 node5.left = null;
 node5.right = null;

 node6.left = null;
 node6.right = node8;

 Solution solution = new Solution(); ;
 int result = solution.DeepestLeavesSum(node1);
 Console.WriteLine(result);
}

public class TreeNode
{
 public int val;
 public TreeNode left;
 public TreeNode right;
 public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
 {
 this.val = val;
 this.left = left;
 this.right = right;
 }
}

public class Solution
{

 public static int s_iFindDepth; // 깊이 값
 public List&amp;amp;lt;KeyValuePair&amp;amp;lt;int, int&amp;amp;gt;&amp;amp;gt; depthValueList = new List&amp;amp;lt;KeyValuePair&amp;amp;lt;int, int&amp;amp;gt;&amp;amp;gt;(); // 깊이값에 대한 Value 값을 나타내기 위한 변수

 public int DeepestLeavesSum(TreeNode root)
 {
 int resValue = 0;
 s_iFindDepth = 0; // 으로 초기화

 DFS(root, 0);

 var findPair = depthValueList.FindAll(rhs =&amp;amp;gt; rhs.Key == s_iFindDepth);
 for (int i = 0; i &amp;amp;lt; findPair.Count; ++i)
 {
 var Value = findPair[i].Value;
 resValue += Value;
 }

 return resValue;
 }

 public void DFS(TreeNode node, int depth) // 깊이 값
 {
 if (s_iFindDepth &amp;amp;lt; depth)
 {
 s_iFindDepth = depth; // Depth 값이 더 크다면 
 }

 int value = node.val;

 depthValueList.Add(new KeyValuePair&amp;amp;lt;int, int&amp;amp;gt;(depth, value));

 if (node.left != null)
 DFS(node.left, depth + 1);

 if (node.right != null)
 DFS(node.right, depth + 1);
 }
}}}</code></pre>

코딩테스트 항해99 클럽 - 7일차

[코딩테스트 일지 - 99클럽] 7일차 - Deepest Leaves Sum

<h3>코딩 테스트 준비 일지 6 일차</h3><ul class="tight" data-tight="true"><li>응시 사이트 :<a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/"> </a><a target="_blank" rel="noopener noreferrer nofollow" href="https://programmers.co.kr/">프로그래머스</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/problems/deepest-leaves-sum/description/"> </a><a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/courses/30/lessons/1844">게임 맵 최단거리</a></li><li>난이도 : 중</li></ul><h6>문제 설명</h6>ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.S X O O O O X O X O O X O O O O O O X O X X X X DS : 시작지점 D : 도착지점위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다. 아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.<ul class="tight" data-tight="true"><li>첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.</li></ul>R X O O O R X O X O R X R R R R R R X R X X X X RR : 이동한 경로<ul class="tight" data-tight="true"><li>두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.</li></ul>R X R R R R X R X R R X R O R R R R X R X X X X R R : 이동한 경로 위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다. S X O O O O X O X O O X O O O O O O X X X X X X R만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.<h5>제한사항</h5><ul class="tight" data-tight="true"><li>maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.<ul class="tight" data-tight="true"><li>n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.</li></ul></li><li>maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.</li><li>처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.</li></ul><hr><h5>입출력 예</h5>maps answer [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1<h3>문제 풀이 접근</h3>이런 문제는 최단거리 경로 탐색할 때, 아주 잘나오는 문제다. 맵을 먼저 주고, 여기서 최단거리 경로를 탐색하라라는 것이다. 나는 이 문제에서 아쉽게도 DFS 개념을 먼저 떠올려서 58분 정도에 DFS 개념을 활용하여 TC를 모두 패스했는데, 효율성 TC가 모두 실패했다.도저히 DFS로는 효율성 TC를 패스할 방법이 생각나지 않아, 방법론의 문제라고 생각하고 다른 사람들의 풀이를 참고했다. 역시나 BFS로 푸는게 정답이었고, Depth 기반으로 찾는 DFS는 경로를 앞에서 찾던 뒤에서 찾던 결국 마지막의 경로 Value를 비교하기 전까지는 최단거리인지 알 수 없다. 단, BFS는 다르다. Breath First 이기 때문에 인접한 노드 ( 트리 상 가로 축 으로 생각하면 편하다 ) 를 탐색하여 가장 먼저 끝나는게 결국 최단거리다. 이래서 최단거리 보장이 되는 것.이런 문제는 플로우가 간단하긴한데 참고할 static 변수들이 조금 있는편이다..<ol class="tight" data-tight="true"><li>map 의 X, Y 축으로 이동할 맥스 값을 찾는다. 5x5 배열이라면 좌상을 0,0 기준 시 4</li><li>방문했는지 체크를 위한 변수를 map 변수와 동일하게 넣는다. </li><li>map 과 현재 위치값, 이동해서 넘어온 카운트 값 등등을 갱신하면서 이동한다.</li><li>이동할때는 visit 변수의 값이 true 가 되었는지, direction 을 통해 0 보다 작게, Max 보다 크게 맵밖으로 나갔는지 체크해서 이동할 수 있는지 여부를 확인하면서 이동한다.</li><li>목적지에 도착했을 경우, 이동한 값이 최단거리라고 판단될 때 이동 값을 갱신한다.</li></ol><h3>작성 코드 ( C# ) - 효율성 실패 DFS 코드 </h3><pre spellcheck="false"><code>using System;

class Solution {
 
 static public bool[,] isVisited;
 static public int[] dirYAxis = new int[4] { 0, 0, -1, 1 }; // 
 static public int[] dirXAxis = new int[4] { 1, -1, 0, 0 }; // 
 static public int[] GoalPos;
 static public int limitXPos = 0;
 static public int limitYPos = 0;
 static public int result = 0;
 
 public int solution(int[,] maps) {
 int answer = 0;
 
 limitXPos = maps.GetLength(0); // X 축 맵 길이
 limitYPos = maps.GetLength(1); // Y 축 맵 길이

 isVisited = new bool[limitXPos, limitYPos];

 GoalPos = new int[2] { limitXPos -1, limitYPos -1};
 result = int.MaxValue;
 int[] startPos = { 0, 0 };

 DFS(ref maps, startPos[0], startPos[1], 1);
 if (result == int.MaxValue)
 result = -1;
 
 answer = result;
 return answer;
 }
 
 public static void DFS(ref int[,] maps, int x, int y, int count)
 {
 if (isVisited[x, y] == true)
 return;

 if (CheckGoalPos(x, y) == true)
 {
 if (result &gt; count)
 result = count;

 return;
 }

 isVisited[x, y] = true;

 for(int i = 0; i &lt; 4; ++i)
 {
 int NextPosX = (x + dirXAxis[i]);
 int NextPosY = (y + dirYAxis[i]);

 if(CheckMovablesDirection(ref maps, NextPosX,NextPosY) == true)
 {
 DFS(ref maps, NextPosX, NextPosY, count + 1);
 }
 
 }
 isVisited[x, y] = false;
 }

 public static bool CheckGoalPos(int x, int y)
 {
 return (GoalPos[0] == x) &amp;&amp; (GoalPos[1] == y);
 }

 public static bool CheckMovablesDirection(ref int[,] maps, int x, int y)
 {
 if ((limitXPos &lt;= x) || (0 &gt; x) || (limitYPos &lt;= y) || (0 &gt; y))
 return false; // 맵 외부에 나가는 케이스는 모두 False;

 if (maps[x, y] != 1)
 return false; // 맵이 아니어도 False

 return true;
 }
}</code></pre><h3>코드 결과 - 효율성 실패 </h3><img src="https://image.until.blog/sin0105/article/1717243022442" alt="until-392"><h3>문제 풀이 접근2 </h3>다시 효율성 테스트를 통과하기 위해 BFS를 사용할 수도 있으나, 이동거리 전부를 Map에 기록하는 방식을 이전에 공부한 적이 있다. 어느 한 지점에서 B 지점으로 이동할때 까지의 거리 값을 모두 2차원 배열에 입력해서 기억하도록 하는 방식이다.<h3>정답 작성 코드 ( C# ) </h3><pre spellcheck="false"><code>using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.ComponentModel.Design;
using System.Linq;
using System.Runtime.InteropServices;
using System.Security.AccessControl;
using System.Security.Authentication;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Web;
using System.Xml.Linq;

/*
 * URL : https://school.programmers.co.kr/learn/courses/30/lessons/1844
 */

namespace CodingTestProj
{
 internal class Program
 {
 /*
 * [1,0,1,1,1]
 * [1,0,1,0,1]
 * [1,0,1,1,1]
 * [1,1,1,0,1]
 * [0,0,0,0,1]
 */

 static public bool[,] isVisited;
 static public int[] dx = new int[4] { 0, 0, -1, 1 }; // 
 static public int[] dy = new int[4] { 1, -1, 0, 0 }; // 
 static public int[] GoalPos;
 static public int limitXPos = 0;
 static public int limitYPos = 0;
 static int[,] map;

 static void Main(string[] args)
 {
 //int[,] map = { { 1, 0, 1, 1, 1 }, { 1, 0, 1, 0, 1 }, { 1, 0, 1, 1, 1 }, { 1, 1, 1, 0, 1 }, { 0, 0, 0, 0, 1 } };
 //int[,] map = { { 1, 1, 1, 1, 1 }, { 1, 0, 1, 0, 1 }, { 1, 1, 1, 1, 1 }, { 1, 0, 1, 0, 1 }, { 1, 1, 1, 1, 1 } };

 //TC 3 
 //[[1, 1, 1, 1, 1], [1, 0, 0, 0, 1], [1, 0, 0, 0, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]] 9

 //solution(map);
 }
 static void solution(int[,] maps)
 {
 limitXPos = maps.GetLength(0); // X 축 맵 길이
 limitYPos = maps.GetLength(1); // Y 축 맵 길이

 GoalPos = new int[2] { limitXPos -1, limitYPos -1};
 map = maps;

 int answer = 0;
 BFS(0,0,out answer);
 }

 public static void BFS(int x, int y, out int result)
 {
 result = - 1;
 Queue&lt;(int, int)&gt; q = new Queue&lt;(int, int)&gt; ();
 q.Enqueue((0, 0));

 while(q.Count &gt; 0)
 {
 var curPos = q.Dequeue();

 if(curPos.Item1 == GoalPos[0] &amp;&amp; curPos.Item2 == GoalPos[1])
 {
 result = map[curPos.Item1, curPos.Item2];
 return;
 }

 for(int i = 0; i &lt; 4; ++i)
 {
 int NextPosX = (curPos.Item1 + dx[i]);
 int NextPosY = (curPos.Item2 + dy[i]);

 if ((NextPosX &gt;= map.GetLength(0)) || (NextPosX &lt; 0) || (NextPosY &gt;= map.GetLength(1) || (NextPosY &lt; 0)))
 continue;

 if (map[NextPosX, NextPosY] != 1) continue;

 q.Enqueue((NextPosX, NextPosY));
 map[NextPosX, NextPosY] = (map[curPos.Item1, curPos.Item2] +1);
 }
 }
 return;
 }
 }
}




</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1717249089001" alt="until-394">

코딩테스트 항해99 클럽 - 6일차

[코딩테스트 일지 - 99클럽] 6일차 - 게임 맵 최단거리

<h3>코딩테스트 준비 일지</h3><ul class="tight" data-tight="true"><li>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://www.hackerrank.com/dashboard">해커랭크</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://www.hackerrank.com/challenges/one-month-preparation-kit-plus-minus/problem?isFullScreen=true&amp;h_l=interview&amp;playlist_slugs%5B%5D=preparation-kits&amp;playlist_slugs%5B%5D=one-month-preparation-kit&amp;playlist_slugs%5B%5D=one-month-week-one">Plus Minus</a></li><li>난이도 : 하</li></ul><h3>문제</h3>Given an array of integers, calculate the ratios of its elements that are positive, negative, and zero. Print the decimal value of each fraction on a new line withplaces after the decimal.Note: This challenge introduces precision problems. The test cases are scaled to six decimal places, though answers with absolute error of up to 10^(-4), are acceptable.Examplearr = [1,1,0-1,-1]There are n = 5 elements, two positive, two negative and one zero. Their ratios are 2/5 = 0.400000 , 2/5 = 0.400000 , and 1/5 = 0.200000. Results are printed as:<pre spellcheck="false"><code>0.400000
0.400000
0.200000</code></pre>Function DescriptionComplete the plusMinus function in the editor below.plusMinus has the following parameter(s):<ul class="tight" data-tight="true"><li>int arr[n]: an array of integers</li></ul>Print Print the ratios of positive, negative and zero values in the array. Each value should be printed on a separate line withdigits after the decimal. The function should not return a value.Input FormatThe first line contains an integer,, the size of the array. The second line contains space-separated integers that describeConstraints<ul class="tight" data-tight="true"><li>0 &lt; n &lt;= 100</li><li>- 100 &lt;= arr[i] &lt;= 100</li></ul>Output FormatPrint the following lines, each to decimals:<ol class="tight" data-tight="true"><li>proportion of positive values</li><li>proportion of negative values</li><li>proportion of zeros</li></ol>Sample Input<pre spellcheck="false"><code>STDIN Function
----- --------
6 arr[] size n = 6
-4 3 -9 0 4 1 arr = [-4, 3, -9, 0, 4, 1]</code></pre>Sample Output<pre spellcheck="false"><code>0.500000
0.333333
0.166667</code></pre>ExplanationThere are positive numbers, negative numbers, and zero in the array. The proportions of occurrence are positive: 3/6 = 0.500000 , negative: 2/6 = 0.333333 and zeros: 1/6 = 0.166667<h3>문제 풀이 접근</h3>뭔가 문제가 영어다보니, 쉬운 문제도 어렵게 보이는 듯한 그런 느낌이 있다. 하지만, 이 문제는 아래와 같다. 1. n 개 정수 던져줄게 2. 양수 / 전체 , 음수 / 전체, 0 / 전체 이렇게 나눠서 값 출력해. 그래서 던져주는대로, 갯수를 먼저 세고, 양의 정수, 음의 정수, 0 의 값을 비율로 출력했다. 출력까지 하는줄 몰랐는데, 출력하니 All Case Pass 였다.<h3>작성 코드 ( C# )</h3><pre spellcheck="false"><code>using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;
class Result
{/*
 * Complete the 'plusMinus' function below.
 *
 * The function accepts INTEGER_ARRAY arr as parameter.
 */
public static List&amp;lt;double&amp;gt; ratio = new List&amp;lt;double&amp;gt;();public static void plusMinus(List&amp;lt;int&amp;gt; arr)
{
double count = arr.Count;
double posiCount = arr.FindAll(rhs =&amp;gt; rhs &amp;gt; 0).Count;
double NegaCount = arr.FindAll(rhs =&amp;gt; rhs &amp;lt; 0).Count;
double ZeroCount = arr.FindAll(rhs =&amp;gt; rhs == 0).Count;ratio.Add(posiCount/count);
ratio.Add(NegaCount/count);
ratio.Add(ZeroCount/count);}}class Solution
{
public static void Main(string[] args)
{
int n = Convert.ToInt32(Console.ReadLine().Trim()); List&amp;lt;int&amp;gt; arr = Console.ReadLine().TrimEnd().Split(' ').ToList().Select(arrTemp =&amp;gt; Convert.ToInt32(arrTemp)).ToList();Result.plusMinus(arr);
var ratio = Result.ratio;for(int i = 0; i &amp;amp;lt; ratio.Count; ++i)
{
Console.WriteLine(ratio[i]);
}}}
</code></pre>

해커랭크 - 1 Month Preparation Kit 1번 문제.

[코딩테스트 일지] 해커랭크, Plus Minus

<h3>코딩 테스트 준비 일지 15 일차</h3><ul class="tight" data-tight="true"><li>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://programmers.co.kr/">프로그래머스</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/courses/30/lessons/49189">가장 먼 노드</a></li><li>난이도 : 중</li><li>풀이시간 : 아직 다못품 + 2h ( 2시간 풀다가 머리식히고 리트라이 예정 )</li></ul><h6>문제 설명</h6>n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.<h5>제한사항</h5><ul class="tight" data-tight="true"><li>노드의 개수 n은 2 이상 20,000 이하입니다.</li><li>간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.</li><li>vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.</li></ul><h5>입출력 예</h5>nvertexreturn6[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]3<h5>입출력 예 설명</h5>예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.일단 기록용 문제가 엉켜서 먼저 아티클 발행

코딩테스트 항해99 클럽 - 15일차

[코딩테스트 일지 - 99클럽] 15일차 - 가장 먼 노드

CodingTest

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li>응시 사이트 :<a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/"> LeetCode</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/problems/smallest-number-in-infinite-set/">Smallest Number in Infinite Set</a></li><li>사용언어 : C#</li><li>난이도 : 중</li><li>풀이시간 : 35m</li><li>유형 : 정렬리스트, 클래스 구현, 우선순위 큐, 힙 </li></ul>You have a set which contains all positive integers&nbsp;<code spellcheck="false">[1, 2, 3, 4, 5, ...]</code>.Implement the&nbsp;<code spellcheck="false">SmallestInfiniteSet</code>&nbsp;class:<ul><li><code spellcheck="false">SmallestInfiniteSet()</code>&nbsp;Initializes the&nbsp;SmallestInfiniteSet&nbsp;object to contain&nbsp;all&nbsp;positive integers.</li><li><code spellcheck="false">int popSmallest()</code>&nbsp;Removes&nbsp;and returns the smallest integer contained in the infinite set.</li><li><code spellcheck="false">void addBack(int num)</code>&nbsp;Adds&nbsp;a positive integer&nbsp;<code spellcheck="false">num</code>&nbsp;back into the infinite set, if it is&nbsp;not&nbsp;already in the infinite set.</li></ul>&nbsp;Example 1:<pre spellcheck="false"><code>Input
["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]
[[], [2], [], [], [], [1], [], [], []]
Output
[null, null, 1, 2, 3, null, 1, 4, 5]

Explanation
SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
smallestInfiniteSet.addBack(2); // 2 is already in the set, so no change is made.
smallestInfiniteSet.popSmallest(); // return 1, since 1 is the smallest number, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 2, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 3, and remove it from the set.
smallestInfiniteSet.addBack(1); // 1 is added back to the set.
smallestInfiniteSet.popSmallest(); // return 1, since 1 was added back to the set and
 // is the smallest number, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 4, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 5, and remove it from the set.
</code></pre>&nbsp;Constraints:<ul><li><code spellcheck="false">1 &lt;= num &lt;= 1000</code></li><li>At most&nbsp;<code spellcheck="false">1000</code>&nbsp;calls will be made&nbsp;in total&nbsp;to&nbsp;<code spellcheck="false">popSmallest</code>&nbsp;and&nbsp;<code spellcheck="false">addBack</code>.</li></ul><h3>문제 풀이 접근</h3>이 문제는, LeetCode에서만 볼 수 있는 느낌의 유형이다. 아직까지 문제를 많이 풀어보진 않았지만, 이런 클래스 구현에 대한 문제는 LeetCode에서밖에 보지 못했다.문제를 보고 가장 첫 접근은, 리스트 만들고 서치하려고 했으나, 역시 이 문제에 대한 습득이 아직 덜 됐다고 느꼈다. 분명 최소요소를 찾고 pop하고 하는건 우선순위 큐, 힙, 정렬리스트 쪽으로 생각을 먼저했어야 됐는데, 리스트만 생각나는건 아직 경험이 부족한 것 같다. 어쨌건, 문제를 정렬리스트로 활용하여 풀었고, 크게 어려운 문제는 아니었다.이 문제의 해결 플로우, 1. 문제의 제약 조건, 1000까지 숫자를 넣기때문에, Addback 에서 미리 있다면 추가하지 않는것이 필요하다. 즉, 정렬리스트에 1000까지 모든 수를 끼워넣은 리스트를 세팅한다. 2. PopSmallList는 단순히 최소 요소를 리턴한다. 3. AddBack 은 있다면 딱히 할 것이 없다. ( 이것 때문에 1번에서 1000까지 세팅하는 것이다. )<h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code>public class SmallestInfiniteSet {
 
 public SortedSet&lt;int&gt; sortSet;

 public SmallestInfiniteSet() {
 sortSet = new SortedSet&lt;int&gt;();
 
 for(int i = 1; i &lt;= 1000; ++i)
 sortSet.Add(i);
 
 }
 
 public int PopSmallest() {
 
 var ret = -1;
 
 if(sortSet.Count &gt; 0)
 {
 ret = sortSet.Min;
 sortSet.Remove(sortSet.Min);
 }
 
 return ret;
 }
 
 public void AddBack(int num) {
 if(sortSet.Contains(num) == true)
 return;
 
 sortSet.Add(num);
 }
}

/**
 * Your SmallestInfiniteSet object will be instantiated and called as such:
 * SmallestInfiniteSet obj = new SmallestInfiniteSet();
 * int param_1 = obj.PopSmallest();
 * obj.AddBack(num);
 */</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1722871595406" alt="until-1181">

혼자서 다시푸는 코딩테스트 준비 일지 - 11

코딩테스트 준비 - Smallest Number in Infinite Set

<h3>코딩 테스트 준비 일지 1 일차</h3><ul class="tight" data-tight="true"><li>문제 : 가장 큰 수<ul class="tight" data-tight="true"><li><a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/courses/30/lessons/42746">https://school.programmers.co.kr/learn/courses/30/lessons/42746</a></li></ul></li><li>난이도 : 중</li></ul><h3>문제</h3>0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.<h5>제한 사항</h5><ul class="tight" data-tight="true"><li>numbers의 길이는 1 이상 100,000 이하입니다.</li><li>numbers의 원소는 0 이상 1,000 이하입니다.</li><li>정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.</li></ul><h5>입출력 예</h5>numbers return[6, 10, 2] "6210"[3, 30, 34, 5, 9] "9534330"<h3>문제 풀이 접근</h3>먼저, 단순한 문제인것으로 확인하여 "정렬" 이라고 써져있는 것만 보고 그냥 다 정렬 돌려버리고 StringBuilder클래스의 Append 를 이용해서 문자열 더하고 Int.Parse 로 정수로 돌려서 크면 무조건 가지고 있는 Int 형 저장변수를 갱신하여 답을 뽑아내려고 했다.이렇게하면 1번 TC는 패스할 수 있었으나, 2번을 패스할 수 없었다. 1시간 넘게 고민을 하다 결국 여러 풀이들을 참조하게 되었고, 3번 곱해서 아스키 코드 어쩌구.. 이런 풀이들이 정확하게 이해가 안가서 다른 방식을 찾았다. 정렬을 하면서 비교 수 A , B 를 더하여 A+B, B+A 결과를 판단하여 오름차순으로 정렬하였다. (내림차순으로 하면 바로 출력하면 되는데, 귀찮아서 최종 연산단에서 뒤부터 앞으로 더했다.) 여기까지 적용할 경우, 11번 TC에서 실패가 뜨는것을 확인할 수 있고, 11번 TC는 [0,0] =&gt; 0 의 케이스를 추가하여 코드에 맞춰 수정진행했다. 11번 케이스는 내가 오름차순으로 넣었기 때문에, 마지막에 0 으로 들어가있는지 판단을 하는것으로 이 수의 배열이 0이 제일 크다는 것을 확인할 수 있고, 이런 TC일 경우 0으로 리턴하게되면 쉽게 회피할 수 있다.<h3>작성 코드 ( C# )</h3><pre spellcheck="false"><code>using System;
using System.Text;

public class Solution
{
 public string solution(int[] numbers)
 {
 string answer = "";

 Combination(ref numbers);
 Print(ref numbers, out answer);

 return answer;
 }

 public static void Combination(ref int[] arrStr)
 {

 Array.Sort(arrStr, (int a, int b) =&gt;
 {
 StringBuilder aSB = new StringBuilder();
 StringBuilder bSB = new StringBuilder();

 aSB.Append(a);
 aSB.Append(b);

 bSB.Append(b);
 bSB.Append(a);

 int aValue = int.Parse(aSB.ToString());
 int bValue = int.Parse(bSB.ToString());

 return aValue.CompareTo(bValue);
 });
 }
 public static void Print(ref int[] arrStr, out string result)
 {
 if (arrStr[arrStr.Length - 1] == 0)
 {
 result = "0";
 return;
 }

 StringBuilder sb = new StringBuilder();
 for (int i = arrStr.Length - 1; i &gt;= 0; --i)
 sb.Append(arrStr[i].ToString());

 result = sb.ToString();
 }
}</code></pre>

코딩테스트 항해99 클럽 - 1일차 

[코딩테스트 일지 - 99클럽] 1일차 - 가장 큰 수

<h2>1. PHP Intelephense</h2><img src="https://image.until.blog/laravel/article/1716883584354" alt="until-334"><h2>2. Laravel Extension Pack</h2><img src="https://image.until.blog/laravel/article/1716883526988" alt="until-333">

1. PHP Intelephense2. Laravel Extension Pack