<h3>코딩 테스트 준비 일지 8 일차</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/evaluate-boolean-binary-tree/description/">Evaluate Boolean Binary Tree</a></li><li>난이도 : 중하</li></ul>You are given the <code spellcheck="false">root</code> of a full binary tree with the following properties:<ul class="tight" data-tight="true"><li>Leaf nodes have either the value <code spellcheck="false">0</code> or <code spellcheck="false">1</code>, where <code spellcheck="false">0</code> represents <code spellcheck="false">False</code> and <code spellcheck="false">1</code> represents <code spellcheck="false">True</code>.</li><li>Non-leaf nodes have either the value <code spellcheck="false">2</code> or <code spellcheck="false">3</code>, where <code spellcheck="false">2</code> represents the boolean <code spellcheck="false">OR</code> and <code spellcheck="false">3</code> represents the boolean <code spellcheck="false">AND</code>.</li></ul>The evaluation of a node is as follows:<ul class="tight" data-tight="true"><li>If the node is a leaf node, the evaluation is the value of the node, i.e. <code spellcheck="false">True</code> or <code spellcheck="false">False</code>.</li><li>Otherwise, evaluate the node's two children and apply the boolean operation of its value with the children's evaluations.</li></ul>Return the boolean result of evaluating the <code spellcheck="false">root</code> node.A full binary tree is a binary tree where each node has either <code spellcheck="false">0</code> or <code spellcheck="false">2</code> children.A leaf node is a node that has zero children.Example 1:<img src="https://assets.leetcode.com/uploads/2022/05/16/example1drawio1.png" alt=""><pre spellcheck="false"><code>Input: root = [2,1,3,null,null,0,1]
Output: true
Explanation: The above diagram illustrates the evaluation process.
The AND node evaluates to False AND True = False.
The OR node evaluates to True OR False = True.
The root node evaluates to True, so we return true.</code></pre>Example 2:<pre spellcheck="false"><code>Input: root = [0]
Output: false
Explanation: The root node is a leaf node and it evaluates to false, so we return false.
</code></pre>Constraints:<ul class="tight" data-tight="true"><li>The number of nodes in the tree is in the range <code spellcheck="false">[1, 1000]</code>.</li><li><code spellcheck="false">0 &lt;= Node.val &lt;= 3</code></li><li>Every node has either <code spellcheck="false">0</code> or <code spellcheck="false">2</code> children.</li><li>Leaf nodes have a value of <code spellcheck="false">0</code> or <code spellcheck="false">1</code>.</li><li>Non-leaf nodes have a value of <code spellcheck="false">2</code> or <code spellcheck="false">3</code>.</li></ul><h3>문제 풀이 접근</h3>이 문제는 단순 경로 탐색처럼 진행하면 되는 문제처럼 보였는데, 탐색 이후 처리가 더 중요했던 문제였다.이 문제를 봤을때, 딱 해결 방법이 DFS로 하는것이 좋아보여서, DFS 말고 다른 방법은 고려하지 않았다. 딱 문제의 생김새가 부모의 Root 노드가 0,1 이 아니고 2,3 이면서 left, right 가 null 일때를 참고해서 계산한 후에 내 root 의 value 값을 갱신하면 되는것 처럼 생겼다.다행히 풀이 방법이 틀리지 않아서 문제를 용이하게 풀었으나, 중간에 조금 해맸다. 받은 데이터의 value는 어차피 중요하지 않아서 덮어씌워도 됐었는데, stack 으로 탐색한 경로를 수집하다가 나중에 다 수집하고나서 결과를 연산하는 방식으로 하니까 아무래도 연산하는 순서나 이런 부분에서 꼬이는 것이 많이 있었다. 그래서 이 방법은 시원하게 폐기하고 stack 지워버리고 재귀로 해결했다.문제를 푸는 플로우는 다음과 같다. 1. DFS를 만들고, 바로 left, right 순으로 순회시킨다. 예외 처리로는 left,right 가 모두 null 인 경우로 처리한다. 2. 이후 left, right 순으로 순회한 다음 root.value 가 2,3 인 경우 OR, AND 의 경우 값만 처리해주고 결과를 bool 값으로 리턴한다. 3. 추가로 첫 입력 데이터 root 가 0, 1 으로 하나만 들어오는 경우의 값도 처리하여 종료해준다. ( 이때는 바로 root.Value 를 Convert.ToBoolean()으로 변수를 컨버팅해서 반환하면 된다)<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 bool EvaluateTree(TreeNode root)
 {
 if (root.left == null &amp;&amp; root.right == null)
 return Convert.ToBoolean(root.val);

 bool dd = DFS(root);
 return dd;
 }

 public bool DFS(TreeNode root) 
 {
 if (root.left == null &amp;&amp; root.right == null)
 return false;

 DFS(root.left);
 DFS(root.right);

 if (root.left == null &amp;&amp; root.right == null)
 return false;

 switch(root.val)
 {
 case 2:
 root.val = (root.left.val == 0 &amp;&amp; root.right.val == 0) ? 0 : 1;
 break;
 case 3:
 root.val = (root.left.val == 1 &amp;&amp; root.right.val == 1) ? 1 : 0;
 break;
 }

 return Convert.ToBoolean(root.val);
 }
 }</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1717353024205" alt="until-399"><h3>프로젝트에서 바로 돌릴 수 있는 코드 ( C# )</h3><pre spellcheck="false"><code>using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.ComponentModel.Design;
using System.Diagnostics;
using System.IO;
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;
using static CodingTestProj.Program;

namespace CodingTestProj
{
 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;
 }
 }

 /* Condition 
 * 1 . FULL BT
 * 
 * 
 * 
 * 
 */

 internal class Program
 {
 static void Main(string[] args)
 {
 TreeNode node1 = new TreeNode(3);
 TreeNode node2 = new TreeNode(3);
 TreeNode node3 = new TreeNode(2);
 TreeNode node4 = new TreeNode(0);
 TreeNode node5 = new TreeNode(0);
 TreeNode node6 = new TreeNode(3);
 TreeNode node7 = new TreeNode(2);
 TreeNode node8 = new TreeNode(1);
 TreeNode node9 = new TreeNode(3);
 TreeNode node10 = new TreeNode(1);
 TreeNode node11 = new TreeNode(1);
 TreeNode node12 = new TreeNode(2);
 TreeNode node13 = new TreeNode(1);
 TreeNode node14 = new TreeNode(1);
 TreeNode node15 = new TreeNode(1);


 node1.left = node2;
 node1.right = node3;

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

 node3.left = node6;
 node3.right = node7;

 // 4 , 5 X
 node6.left = node8;
 node6.right = node9;

 node7.left = node10;
 node7.right = node11;

 node9.left = node12;
 node9.right = node13;

 node12.left = node14;
 node12.right = node15;

 Solution solution = new Solution();
 solution.EvaluateTree(node1);
 }
 }

 public class Solution
 {
 public bool EvaluateTree(TreeNode root)
 {
 if (root.left == null &amp;&amp; root.right == null)
 return Convert.ToBoolean(root.val);

 bool dd = DFS(root);
 return dd;
 }

 public bool DFS(TreeNode root) 
 {
 if (root.left == null &amp;&amp; root.right == null)
 return false;

 DFS(root.left);
 DFS(root.right);

 if (root.left == null &amp;&amp; root.right == null)
 return false;

 switch(root.val)
 {
 case 2:
 root.val = (root.left.val == 0 &amp;&amp; root.right.val == 0) ? 0 : 1;
 break;
 case 3:
 root.val = (root.left.val == 1 &amp;&amp; root.right.val == 1) ? 1 : 0;
 break;
 }

 return Convert.ToBoolean(root.val);
 }
 }
}</code></pre>

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

[코딩테스트 일지 - 99클럽] 8일차 - Evaluate Boolean Binary Tree

<h3>코딩 테스트 준비 일지 19 일차</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" class="no-underline hover:text-blue-s dark:hover:text-dark-blue-s truncate cursor-text whitespace-normal hover:!text-[inherit]" href="https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/description/">Minimum Add to Make Parentheses Valid</a></li><li>난이도 : 하</li><li>풀이시간 : 1h 11m</li></ul>A parentheses string is valid if and only if:<ul class="tight" data-tight="true"><li>It is the empty string,</li><li>It can be written as&nbsp;<code spellcheck="false">AB</code>&nbsp;(<code spellcheck="false">A</code>&nbsp;concatenated with&nbsp;<code spellcheck="false">B</code>), where&nbsp;<code spellcheck="false">A</code>&nbsp;and&nbsp;<code spellcheck="false">B</code>&nbsp;are valid strings, or</li><li>It can be written as&nbsp;<code spellcheck="false">(A)</code>, where&nbsp;<code spellcheck="false">A</code>&nbsp;is a valid string.</li></ul>You are given a parentheses string&nbsp;<code spellcheck="false">s</code>. In one move, you can insert a parenthesis at any position of the string.<ul class="tight" data-tight="true"><li>For example, if&nbsp;<code spellcheck="false">s = "()))"</code>, you can insert an opening parenthesis to be&nbsp;<code spellcheck="false">"(()))"</code>&nbsp;or a closing parenthesis to be&nbsp;<code spellcheck="false">"())))"</code>.</li></ul>Return&nbsp;the minimum number of moves required to make&nbsp;<code spellcheck="false">s</code>&nbsp;valid.Example 1:<pre spellcheck="false"><code>Input: s = "())"
Output: 1
</code></pre>Example 2:<pre spellcheck="false"><code>Input: s = "((("
Output: 3
</code></pre>Constraints:<ul class="tight" data-tight="true"><li><code spellcheck="false">1 &lt;= s.length &lt;= 1000</code></li><li><code spellcheck="false">s[i]</code>&nbsp;is either&nbsp;<code spellcheck="false">'('</code>&nbsp;or&nbsp;<code spellcheck="false">')'</code>.</li></ul><h3>문제 풀이 접근</h3>금일 문제 풀이 키워드는 String, Stack 이었는데, 괄호를 어떻게 최단움직임으로 완벽하게 쌍을 맞춰주냐 그게 핵심 문제였다.크게 생각할 것은 없고, 문제를 2가지 방법을 생각했는데, 1. String 의 s[i] , s[i-1] 의 '(' ,')' 일 경우를 체크해서 answer를 하나 올리고 추후 연산에 넣는다. 2. Stack을 이용하여 '(' 일 경우 Push 하고, 가지고 있는 '(' 를 그다음 s[i] 가 ')' 괄호가 온다면 하나씩 Pop 해주는 것이다. 1번의 경우 여러 TC에서 막힐 소지가 있었다. 루프 카운터가 넘어가거나 하는 경우는 체크할 수 없기 때문이다. 2번의 경우가 Stack의 LIFO 성격을 이용해 하나씩 빼고 Answer + stack.Count() 를 더하면 원하는 값이나온다. ( 이 방법을 사용한다면, 사실 꼭 Stack을 이용하지 않아도 된다. )<h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code>public class Solution
 {
 public int MinAddToMakeValid(string s)
 {
 int answer = 0;

 if (s == string.Empty)
 return answer;

 Stack&lt;char&gt; stack = new Stack&lt;char&gt;();

 for(int i = 0; i &lt; s.Length; ++i)
 {
 if (s[i] == '(')
 stack.Push(s[i]);

 if(stack.Count() &lt;= 0 &amp;&amp; s[i] == ')')
 {
 ++answer;
 }

 if(stack.Count() &gt; 0 &amp;&amp; s[i] == ')')
 {
 stack.Pop();
 }
 }

 return stack.Count()+ answer;
 }
 }</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1719302424840" alt="until-677">

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

[코딩테스트 일지 - 99클럽] 19일차 - Minimum Add to Make Parentheses Valid

<h3>코딩 테스트 준비 일지 18 일차</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" class="no-underline hover:text-blue-s dark:hover:text-dark-blue-s truncate cursor-text whitespace-normal hover:!text-[inherit]" href="https://leetcode.com/problems/sort-characters-by-frequency/">Sort Characters By Frequency</a></li><li>난이도 : 하</li><li>풀이시간 : 20m 15s</li></ul>Given a string&nbsp;<code spellcheck="false">s</code>, sort it in&nbsp;decreasing order&nbsp;based on the&nbsp;frequency&nbsp;of the characters. The&nbsp;frequency&nbsp;of a character is the number of times it appears in the string.Return&nbsp;the sorted string. If there are multiple answers, return&nbsp;any of them.&nbsp;Example 1:<pre spellcheck="false"><code>Input: s = "tree"
Output: "eert"
Explanation: 'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.
</code></pre>Example 2:<pre spellcheck="false"><code>Input: s = "cccaaa"
Output: "aaaccc"
Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.
Note that "cacaca" is incorrect, as the same characters must be together.
</code></pre>Example 3:<pre spellcheck="false"><code>Input: s = "Aabb"
Output: "bbAa"
Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.
</code></pre>&nbsp;Constraints:<ul class="tight" data-tight="true"><li><code spellcheck="false">1 &lt;= s.length &lt;= 5 * 105</code></li><li><code spellcheck="false">s</code>&nbsp;consists of uppercase and lowercase English letters and digits.</li></ul><h3>문제 풀이 접근</h3>금일 문제 풀이는 문제 자체가 쉬워서 2가지 정도만 생각하고 쉽게 솔루션을 냈던것 같다. 1. a ~ Z 까지 소문자, 26(소문자) + 26(대문자) =&gt; 총 52개의 배열을 먼저 갖고 있다가 만나는 문자마다 Plus 해서 조립해서 리턴하는 방식 2. PairCharCount 내부에는 Char , int 하나씩 있다라고 할때, List&lt;PairCharCount&gt; 내부에 생성해서 갖고 있다가 PairCharCount 의 갯수로 정렬하고, 갯수만큼 새롭게 문자열을 StringBuilder를 사용해서 string 으로 만들고 반환하는 방식 이 두가지 였는데, 1번을 먼저 생각했다가, 정적배열 정렬도 귀찮고 그래서 2번 방식으로 빠르게 풀었다. 문제 풀이 플로우는 아래와 같다. 1. 파라미터 문자열 s 가 들어오면 길이만큼 순회하면서 charList 안에 현재 문자가 있는지 체크한다. 2. 없다면, 그 문자에 대한 PairCharCount 를 생성하고, Count 를 하나 올려준다. 3. 문자열 끝을 순회할때까지 1~2번을 반복한다. 4. charList 를 Count 기준으로 정렬한다. 5. 정렬된 charList 를 앞에서 부터 순회하고, 그 Count 만큼 또 문자를 추가해야하기 때문에 2중 for문으로 작성한다. 6. 만들어진 string 을 반환한다.<h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code> public class PairCharCount
 {
 public char key;
 public int count;

 public PairCharCount()
 {
 this.key = 'a';
 this.count = 0;
 }// Default Creator

 public PairCharCount(char key)
 {
 this.key = key;
 this.count = 0;
 }

 public void SetChar(char key)
 {
 this.key = key;
 }

 public void PlusCount()
 {
 ++this.count;
 }
 }

 public class Solution
 {

 List&lt;PairCharCount&gt; charList = new List&lt;PairCharCount&gt;();

 public string FrequencySort(string s)
 {
 StringBuilder sb = new StringBuilder();
 string answer = string.Empty;

 for (int i = 0; i &lt; s.Length; ++i)
 {
 char element = s[i];

 if (charList.Exists(rhs =&gt; rhs.key == element) == false)
 charList.Add(new PairCharCount(element));

 var elementPair = charList.Find(rhs =&gt; rhs.key == element);
 elementPair.PlusCount();
 }

 charList.Sort((a1, a2) =&gt; a2.count.CompareTo(a1.count));

 for (int i = 0; i &lt; charList.Count; ++i)
 {
 var element = charList[i];

 for (int j = 0; j &lt; element.count; ++j)
 sb.Append(element.key);
 }

 answer = sb.ToString();
 return answer;
 }
 }</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1718777321530" alt="until-592">

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

[코딩테스트 일지 - 99클럽] 18일차 - Sort Characters By Frequency

<h3>코딩 테스트 준비 일지 8 일차</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/all-paths-from-source-to-target/description/">All Paths From Source to Target</a></li><li>난이도 : 중하</li></ul>Given a directed acyclic graph (DAG) of <code spellcheck="false">n</code> nodes labeled from <code spellcheck="false">0</code> to <code spellcheck="false">n - 1</code>, find all possible paths from node <code spellcheck="false">0</code> to node <code spellcheck="false">n - 1</code> and return them in any order.The graph is given as follows: <code spellcheck="false">graph[i]</code> is a list of all nodes you can visit from node <code spellcheck="false">i</code> (i.e., there is a directed edge from node <code spellcheck="false">i</code> to node <code spellcheck="false">graph[i][j]</code>).&nbsp;Example 1:<img src="https://assets.leetcode.com/uploads/2020/09/28/all_1.jpg" alt=""><pre spellcheck="false"><code>Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths: 0 -&gt; 1 -&gt; 3 and 0 -&gt; 2 -&gt; 3.</code></pre>Example 2:<img src="https://assets.leetcode.com/uploads/2020/09/28/all_2.jpg" alt=""><pre spellcheck="false"><code>Input: graph = [[4,3,1],[3,2,4],[3],[4],[]]
Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]</code></pre>&nbsp;Constraints:<ul class="tight" data-tight="true"><li><code spellcheck="false">n == graph.length</code></li><li><code spellcheck="false">2 &lt;= n &lt;= 15</code></li><li><code spellcheck="false">0 &lt;= graph[i][j] &lt; n</code></li><li><code spellcheck="false">graph[i][j] != i</code> (i.e., there will be no self-loops).</li><li>All the elements of <code spellcheck="false">graph[i]</code> are unique.</li><li>The input graph is guaranteed to be a DAG.</li></ul><h3>문제 풀이 접근</h3>이 문제는 N개의 노드 데이터를 넘겨주고, 목적지 (마지막으로 넘겨준 노드의 값) 까지의 모든 경로를 어떤 순서로든 리턴하면 되는 문제다.먼저 이 문제를 해결하기 위해 알고리즘 선택을 할 필요가 있었는데, 나는 모든 경로를 반환해야 한다는 점에서 완전탐색으로 하는 방식을 확인했고, 최단 경로를 탐색하기 좋은 BFS보다 DFS 재귀 구현방식이 더 익숙하기도해서 DFS 재귀 방식을 선택했다. DFS 스택으로 구현할 수 도 있을텐데, 익숙하지 않기도 하고, 재귀 돌려서 본인의 노드를 넘겨주는걸 더 편하게 생각해서 DFS 재귀 방식으로 진행했다.물론 이 문제의 경우 Graph 클래스를 작성해도 쉽게 풀릴 것 같다고 생각하고, 트리방식으로 생각하고 해도 될 것 같긴하다 .내가 푼 문제의 플로우는 아래와 같다. 1. 데이터 int[][] 형식의 2차원 배열로 넘어가니 map 이라는 변수를 만들어서 내가 컨트롤하기 쉬운 데이터로 바꾼다. ( 공간 복잡도 잡아먹는다고 쳐도 쓰기 쉬운게 우선이라고 생각하여 이렇게 처리 ) 2. 넘어온 데이터의 순서가 곧 노드의 번호다 "<code spellcheck="false">n</code> nodes labeled from <code spellcheck="false">0</code> to <code spellcheck="false">n - 1</code> " 3. 내가 쓰기 쉬운형태로 매핑을 한 후 DFS를 돌려준다. 4. DFS 내부 함수 내가 지나온 경로를 수집해준다. 5. 수집하면서 내가 방문했었는지 잘 체크해서 수집하고, 목적지에 도달하면 수집했던 경로를 List로 넣어주고 내 저장 리스트의 인덱스를 하나 올려준다.<h3>정답 작성 코드 ( C# )</h3><pre spellcheck="false"><code>public class Solution {
 const int s_iMaxNodeCount = 25;
 public static int s_ipathIndex = 0;
 public static int s_iGoalPos = 0;

 public static List&amp;lt;List&amp;lt;int&amp;gt;&amp;gt; maps = new List&amp;lt;List&amp;lt;int&amp;gt;&amp;gt;();

 public static Stack&amp;lt;int&amp;gt; recordPath = new Stack&amp;lt;int&amp;gt;();

 public IList&amp;lt;IList&amp;lt;int&amp;gt;&amp;gt; AllPathsSourceTarget(int[][] graph){
maps.Clear();
recordPath.Clear();
s_ipathIndex = 0;
IList&lt;IList&lt;int&gt;&gt; resultList = new List&lt;IList&lt;int&gt;&gt;();
resultList.Clear(); int NodeCount = graph.GetLength(0);
 s_iGoalPos = NodeCount - 1; // 목적지

 for (int i = 0; i &amp;lt; NodeCount; ++i)
 {
 maps.Add(new List&amp;lt;int&amp;gt;()); // 0 은 0 라벨 노드
 var mapsIndex = i;

 for (int j = 0; j &amp;lt; graph[i].Length; ++j)
 {
 var edge = graph[i][j];
 maps[mapsIndex].Add(edge);
 }
 }
 // 맵 매핑 완료

 bool[] isVisit = new bool[s_iMaxNodeCount];
 for (int i = 0; i &amp;lt; s_iMaxNodeCount; ++i)
 {
 isVisit[i] = false;
 }

 DFS(ref resultList, 0, ref isVisit);
 return resultList;} public void DFS(ref IList&amp;lt;IList&amp;lt;int&amp;gt;&amp;gt; result, int currentNode, ref bool[] isVisit){
if (isVisit[currentNode] == true)
{
if (recordPath.Count &gt; 0) recordPath.Pop();
return; // 방문했다면 종료
} isVisit[currentNode] = true;
 recordPath.Push(currentNode);

 if (result.Count &amp;lt;= s_ipathIndex)
 result.Add(new List&amp;lt;int&amp;gt;());

 if (currentNode == s_iGoalPos)
 {
 result[s_ipathIndex].Clear();

 for (int i = recordPath.Count - 1; i &amp;gt;= 0; --i)
 {
 var node = recordPath.ElementAt(i);
 result[s_ipathIndex].Add(node);
 }

 ++s_ipathIndex;
 return;
 }

 for (int i = 0; i &amp;lt; maps[currentNode].Count; ++i)
 {
 var node = maps[currentNode][i];

 DFS(ref result, node, ref isVisit);
 isVisit[node] = false;
 recordPath.Pop();
 }}}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1717337511529" alt="until-398"><h3>프로젝트에서 바로 돌릴 수 있는 코드 ( C# )</h3><pre spellcheck="false"><code> internal class Program
{
public class Graph
{ } // 그래프 풀이도 가능할 것 같다.

 // Q

 const int s_iMaxNodeCount = 20;
 public static int s_ipathIndex = 0;
 public static int s_iGoalPos = 0;

 public static List&amp;lt;List&amp;lt;int&amp;gt;&amp;gt; maps = new List&amp;lt;List&amp;lt;int&amp;gt;&amp;gt;();
 public static Stack&amp;lt;int&amp;gt; recordPath = new Stack&amp;lt;int&amp;gt;();

 static void Main(string[] args)
 {
 int[][] graph = new int[][]
 {
 new int[] { 1, 2 , },
 new int[] { 3 },
 new int[] { 3 },
 new int[] {}
 };



 Program mm = new Program();
 mm.AllPathsSourceTarget(graph);

 int[][] graph2 = new int[][]{
new int[] { 4, 3 , 1},
new int[] { 3, 2, 4 },
new int[] { 3 },
new int[] { 4} ,
new int[] {} ,
}; mm.AllPathsSourceTarget(graph2);

 }
 public IList&amp;lt;IList&amp;lt;int&amp;gt;&amp;gt; AllPathsSourceTarget(int[][] graph)
 {
 maps.Clear();
 recordPath.Clear();
 s_ipathIndex = 0;
 IList&amp;lt;IList&amp;lt;int&amp;gt;&amp;gt; resultList = new List&amp;lt;IList&amp;lt;int&amp;gt;&amp;gt;();
 resultList.Clear();

 int NodeCount = graph.GetLength(0);
 s_iGoalPos = NodeCount - 1; // 목적지

 for (int i = 0; i &amp;lt; NodeCount; ++i)
 {
 maps.Add(new List&amp;lt;int&amp;gt;()); // 0 은 0 라벨 노드
 var mapsIndex = i;

 for (int j = 0; j &amp;lt; graph[i].Length; ++j)
 {
 var edge = graph[i][j];
 maps[mapsIndex].Add(edge);
 }
 }
 // 맵 매핑 완료

 bool[] isVisit = new bool[s_iMaxNodeCount];
 for (int i = 0; i &amp;lt; s_iMaxNodeCount; ++i)
 {
 isVisit[i] = false;
 }

 DFS(ref resultList, 0, ref isVisit);
 return resultList;
 }


 public void DFS(ref IList&amp;lt;IList&amp;lt;int&amp;gt;&amp;gt; result, int currentNode, ref bool[] isVisit)
 {
 if (isVisit[currentNode] == true)
 {
 if (recordPath.Count &amp;gt; 0) recordPath.Pop();
 return; // 방문했다면 종료
 }

 isVisit[currentNode] = true;
 recordPath.Push(currentNode);

 if (result.Count &amp;lt;= s_ipathIndex)
 result.Add(new List&amp;lt;int&amp;gt;());

 if (currentNode == s_iGoalPos)
 {
 result[s_ipathIndex].Clear();

 for (int i = recordPath.Count - 1; i &amp;gt;= 0; --i)
 {
 var node = recordPath.ElementAt(i);
 result[s_ipathIndex].Add(node);
 }

 ++s_ipathIndex;
 return;
 }

 for (int i = 0; i &amp;lt; maps[currentNode].Count; ++i)
 {
 var node = maps[currentNode][i];

 DFS(ref result, node, ref isVisit);
 isVisit[node] = false;
 recordPath.Pop();
 }
 }
}&lt;/code&gt;&lt;/pre&gt;&lt;p&gt;&lt;/p&gt;&lt;h2&gt;** LeetCode 에서 문제 풀때는 절대로 전역 변수를 초기화하여 사용하던지 되도록 사용하지 말자.&lt;/h2&gt;&lt;p&gt;&lt;/p&gt;&lt;p&gt;&lt;/p&gt;&lt;p&gt;&lt;/p&gt;</code></pre>

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

[코딩테스트 일지 - 99클럽] 8일차 - All Paths From Source to Target

<h3>코딩 테스트 준비 일지 15 일차</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://school.programmers.co.kr/learn/courses/30/lessons/49191">순위</a></li><li>난이도 : 상</li><li>풀이시간 : 2h 25m</li></ul>문제설명n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.<h5>제한사항</h5><ul class="tight" data-tight="true"><li>선수의 수는 1명 이상 100명 이하입니다.</li><li>경기 결과는 1개 이상 4,500개 이하입니다.</li><li>results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.</li><li>모든 경기 결과에는 모순이 없습니다.</li></ul><h5>입출력 예</h5>nresultsreturn5[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]2<h5>입출력 예 설명</h5>2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다. 5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.<h5>제한사항</h5><ul class="tight" data-tight="true"><li>선수의 수는 1명 이상 100명 이하입니다.</li><li>경기 결과는 1개 이상 4,500개 이하입니다.</li><li>results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.</li><li>모든 경기 결과에는 모순이 없습니다.</li></ul><h5>입출력 예</h5>nresultsreturn5[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]2<h5>입출력 예 설명</h5>2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다. 5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.<h5>제한사항</h5><ul class="tight" data-tight="true"><li>선수의 수는 1명 이상 100명 이하입니다.</li><li>경기 결과는 1개 이상 4,500개 이하입니다.</li><li>results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.</li><li>모든 경기 결과에는 모순이 없습니다.</li></ul><h5>입출력 예</h5>nresultsreturn5[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]2<h5>입출력 예 설명</h5>2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다. 5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.<h3>문제 풀이 접근</h3>금일 문제는 단순히 알고리즘 없이 그래프, BFS, 탐색 이런 부분에서 해결될 줄 알았다. 문제를 Win, Lose 에 관한 것을 클래스를 만들어서 저장하고, 이후에 연산하면서 작업 진행하려 했으나, 진행하면서 부정확한 논리들 때문에 고려하다가 1시간 까먹었다. 틀린 방식의 플로우지만, 기록용으로 남긴다. 1. Graph 클래스와 Node 클래스를 만들고, Graph 클래스 안에 노드와, Edge 들에 관한 정보들을 넣는다. 2. 이들을 구성한 후에 모든 케이스에 대한 Match 를 시켜서 승&amp;패를 정한 후, 승패가 정해진 노드 ( 모든 노드와 싸운 노드 ) 의 파생 노드들을 검색해서 한명이고, 내가 n-1 등이거나 2등이거나 일때 n-1 등일때 패하면 파생노드가 꼴등, 2등일때 파생노드가 이기면 1등 이런 느낌으로 생각했는데, 생각해보면 너무 터무니 없는 로직이다.이렇게 삽질한 후에 플로이드 와샬 알고리즘을 넣어야 한다는 힌트를 찾아 다시 개념을 익히고 문제 풀이를 진행했다. 1. int[][] 로 인접행렬을 만들어 준다. 2. [A,B] , [B,C] , [ C, D] 대충 이런형식으로 데이터가 들어오는데 A는 B를 이긴다. B는 C를 이긴다. 이런 형태의 데이터가 들어온다. 3. int[A,B] = 1; , int[B,A] = -1; 와 같은 느낌으로 승패를 정해주면서 인접행렬을 만들어준다. 4. 이 문제에서 조건이 있다. "모든 경기 결과에는 모순이 없다" 라는 조건이, 간접적인 승리까지도 가능하다는 것을 이야기하는 것으로 알고 있는데, A-&gt;B , B-&gt;C , A-&gt;C 처럼 A가 B이기고 B가 C이기는데 A는 당연히 C를 이긴다. 라는 의미다. (여기서 경기에 말도안되는 조건이라고 생각을 하긴했다..) 5. 4번에 따라, 조건을 만들면, for 문은 k j i 순으로 돌린 후에 graph[i][k] == 1 &amp;&amp; graph[k][k] == 1 조건에 맞추면 graph[i][k] = 1 , graph[k][i] = -1 으로 변경해서 결과를 찾는 조건으로 넘기면된다. 6. 플로이드 와샬 사용할때 주의점은 i j k 의 순서가 매우 중요하다. 단순히 이 순서 때문에 패스하지못한 TC가 존재할 정도로 예민하다. 플로이드 와샬의 기조는 서로 모든 최단 거리를 구하는 것으로 i j k 순으로 순회를 해버리면 이미 이동해버려서 이전의 최단거리를 측정할 수 있는데, 제대로 측정하는것이 불가능해진다고 한다. 이게 싫으면 2번 돌리면 되긴한다. 실제로 이 부분 문제에서 i j k 순서로 2번 돌리면 TC 올패스 한다.<h3>실패한 코드 </h3><pre spellcheck="false"><code>using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
 internal class Program
 {
 static void Main(string[] args)
 {
 int node = 5;
 int[,] result = { { 4, 3 }, { 4, 2 }, { 3, 2 }, { 1, 2 }, { 2, 5 } };

 Solution solution = new Solution();
 solution.solution(node, result);
 }
 }

 public class Solution
 {
 public int solution(int n, int[,] results)
 {
 int answer = 0;

 Graph graph = new Graph(n, results);
 graph.MatchResult(out answer);

 return answer;
 }
 }

 public class Graph
 {
 public int nodeCount;
 public List&lt;Node&gt; nodes;
 public List&lt;Tuple&lt;int, int&gt;&gt; edges = new List&lt;Tuple&lt;int, int&gt;&gt;();
 // Key : NodeValue

 // Value
 // Param 1 : Win Player
 // Param 2 : Lose Player 

 public Graph(int n, int[,] result)
 {
 nodes = new List&lt;Node&gt;();

 for (int i = 0; i &lt; n; i++)
 nodes.Add(new Node(i)); // 하나씩 데이터를 넣는다. =&gt; 선수

 nodeCount = n;

 for (int i = 0; i &lt; result.GetLength(0); i++)
 {
 edges.Add(new Tuple&lt;int, int&gt;(result[i, 0] - 1, result[i, 1] - 1));
 }
 }

 public void MatchResult(out int result)
 {
 result = 0;

 for (int i = 0; i &lt; nodes.Count; i++)
 {
 var node = nodes[i];

 var getAllEdge = edges.FindAll(rhs =&gt; rhs.Item1 == node.NodeIndex || rhs.Item2 == node.NodeIndex);
 // 노드가 들어간 모든 케이스를 가져온다.

 var count = getAllEdge.Count();

 if (count == nodeCount - 1)
 {
 // 이 케이스의 경우 모든 애들과 싸웠다.
 if (node.rank == 0)
 {
 node.MakeRank(ref getAllEdge);
 }
 }
 }

 for (int i = 0; i &lt; nodes.Count; ++i)
 {
 var node = nodes[i];

 if (node.rank != 0)
 ++result;
 }
 }
 }

 public class Node
 {
 public int NodeIndex;
 public int rank;

 public List&lt;int&gt; WinIndex = new List&lt;int&gt;(); // 나에게서 이긴 넘버들 
 public List&lt;int&gt; LoseIndex = new List&lt;int&gt;(); // 나한테 진 넘버들

 public Node(int number)
 {
 this.NodeIndex = number;
 this.rank = 0; // 아직 안정해짐
 }

 public void MakeRank(ref List&lt;Tuple&lt;int, int&gt;&gt; matches)
 {
 for (int i = 0; i &lt; matches.Count; i++)
 {
 var match = matches[i];
 if (match.Item1 == this.NodeIndex)
 {
 // 내가 앞에있으면 이겼다.
 LoseIndex.Add(match.Item2);
 }

 if (match.Item2 == this.NodeIndex)
 {

 // 내가 뒤에있으면 졌다.
 WinIndex.Add(match.Item1);
 }


 }
 }
 }
}</code></pre><h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code>
 public class Solution
 {
 const int INF = int.MaxValue;

 public int solution(int n, int[,] results)
 {
 int answer = 0;

 int[,] graph = new int[n + 1, n + 1];

 for(int i = 0; i &lt; results.GetLength(0); ++i)
 {
 int x = results[i, 0];
 int y = results[i, 1];
 graph[x, y] = 1;
 graph[y, x] = -1;
 }

 // A -&gt; B , B -&gt; C , A -&gt; C 의 조건이 승리, A가 B를 이기고, B는 C를 이기니까 당연히 A는 C를 이긴다.

 for (int k = 1; k &lt;= n; ++k)
 {
 for (int i = 1; i &lt;= n; ++i)
 {
 for (int j = 1; j &lt;= n; ++j)
 {
 if (graph[i, k] == 1 &amp;&amp; graph[k, j] == 1)
 {
 graph[i, j] = 1;
 graph[j, i] = -1;
 }
 }
 }
 }



 int matchCount;
 for(int i = 1; i &lt;= n; ++i)
 {
 matchCount = 0;
 for(int j =1; j &lt;= n; ++j)
 {
 if (i == j) continue;
 if (graph[i, j] != 0) ++matchCount;
 }

 if (matchCount == n - 1)
 ++answer;
 }
 
 return answer;
 }
 }</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1718259929714" alt="until-478">

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

[코딩테스트 일지 - 99클럽] 15일차 - 순위

<h3>코딩 테스트 준비 일지 9 일차</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/reverse-odd-levels-of-binary-tree/description/">Reverse Odd Levels of Binary Tree</a></li><li>난이도 : 중상</li><li>풀이시간 : 01 h 51 m</li></ul>Given the <code spellcheck="false">root</code> of a perfect binary tree, reverse the node values at each odd level of the tree.<ul class="tight" data-tight="true"><li>For example, suppose the node values at level 3 are <code spellcheck="false">[2,1,3,4,7,11,29,18]</code>, then it should become <code spellcheck="false">[18,29,11,7,4,3,1,2]</code>.</li></ul>Return the root of the reversed tree.A binary tree is perfect if all parent nodes have two children and all leaves are on the same level.The level of a node is the number of edges along the path between it and the root node.&nbsp;Example 1:<img src="https://assets.leetcode.com/uploads/2022/07/28/first_case1.png" alt=""><pre spellcheck="false"><code>Input: root = [2,3,5,8,13,21,34]
Output: [2,5,3,8,13,21,34]
Explanation: 
The tree has only one odd level.
The nodes at level 1 are 3, 5 respectively, which are reversed and become 5, 3.
</code></pre>Example 2:<img src="https://assets.leetcode.com/uploads/2022/07/28/second_case3.png" alt=""><pre spellcheck="false"><code>Input: root = [7,13,11]
Output: [7,11,13]
Explanation: 
The nodes at level 1 are 13, 11, which are reversed and become 11, 13.
</code></pre>Example 3:<pre spellcheck="false"><code>Input: root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]
Output: [0,2,1,0,0,0,0,2,2,2,2,1,1,1,1]
Explanation: 
The odd levels have non-zero values.
The nodes at level 1 were 1, 2, and are 2, 1 after the reversal.
The nodes at level 3 were 1, 1, 1, 1, 2, 2, 2, 2, and are 2, 2, 2, 2, 1, 1, 1, 1 after the reversal.
</code></pre>Constraints:<ul class="tight" data-tight="true"><li>The number of nodes in the tree is in the range <code spellcheck="false">[1, 214]</code>.</li><li><code spellcheck="false">0 &lt;= Node.val &lt;= 105</code></li><li><code spellcheck="false">root</code> is a perfect binary tree.</li></ul><h3>문제 풀이 접근</h3>이 문제를 접했을 때, 바로 생각난 방식은 DFS 재귀 순회였고, depth % 2 == 0 일때, left, right 의 노드를 스위칭 하는 방식으로 생각해서 코드 구현을 작업했다. 결론으로 말하자면 이 문제는 dfs, bfs 모두 사용해도 상관없으며, 심지어 reverse 돌리는 것도 따로 저장해서 bfs 두번 돌리면서 역순 정렬해도 무방한 문제다. (유투브에 있는 대부분의 풀이 동영상이 이런 방식을 채택하고 있다. )이 문제를 풀면서 단순히 왼, 오의 값을 변경하는데 초점을 맞춰버려서 시간을 오래걸리고 제대로 된 구현을 하는것이 힘들었다. 결국 다른 사람의 풀이를 보면서 어떻게 풀어야 깔끔하고 빠르게 풀지를 체크해 보았는데, 이미 문제에서 힌트는 전부 주어지고 있었다. 완벽한 2진 트리를 준다는 것. 결국 여기서 알 수 있는 정보는 왼쪽 끝단, 오른쪽 끝단 이 둘은 서로 매칭되며, 왼쪽 끝의 오른쪽 노드와 오른쪽 끝의 왼쪽노드도 매칭된다. 결국, 모든 노드는 매칭이 된다는 것이다.플로우는 아래와 같다. 1. Left는 Left 쪽으로 계속 뻗어나간다. 2. 마찬가지로 Right는 Right 쪽으로 계속 뻗어나간다. 3. 이후 그 다음 왼쪽 끝에서 오른쪽 노드, 오른쪽 끝에서 왼쪽노드 처럼 안쪽으로 조여가며 매칭된 것을 뒤집어 준다.<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 TreeNode ReverseOddLevels(TreeNode root) {
 DFS(ref root.left,ref root.right, true);
 return root;
 }
 public void DFS(ref TreeNode rootLeft, ref TreeNode rootRight, bool isOdd)
 {
 if(rootLeft == null)
 return;
 
 if(isOdd == true)
 {
 int temp = rootLeft.val;
 rootLeft.val = rootRight.val;
 rootRight.val = temp;
 }
 
 DFS(ref rootLeft.left, ref rootRight.right,!isOdd);
 DFS(ref rootLeft.right,ref rootRight.left, !isOdd);
 }
}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1717425050186" alt="until-403">

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

[코딩테스트 일지 - 99클럽] 9일차 - Reverse Odd Levels of Binary Tree

올해로 거의 4년째 토스 만보기를 사용 중인 사용자입니다<ol><li>혼자 걷기 만보채우면 100원</li><li>미션 걷기- 친구와 같이 하는거</li><li>5천보 10원, 만보 20원, 친구 총합 3만보 30원, 친구 총합 5만보 40원이었나? 그런거..</li><li>혼자 걷기인데, 천보 5천보 만보단위..? 그리고 어디 미션하는데 도착하면 10원</li><li>아이템 도입</li><li>현재.. 애매하게 한 4개 나뉘어져있음.. 선물 주기/ 만보채우면 아마 최대 40원까지 받을듯?</li></ol>뭐 이런 토스의 만보기 여정을 기억하고 있는 사용자임돠토스 항상 친절한 라이팅과 신경 쓴 사용자 경험 덕에 편안하고 재밌게 사용 중이에요ㅎㅎ근데 요즘! 토스 만보기 좀 섭섭하다~화면이 닫히면 광고가 나와요?????아 조금 섭섭합니다...원래 그냥 받기만 하는거였는데 광고까지 보게 만드네?? 이건 쫌?싶은 그런 경험이에요눈치를 챘는지 다시 사라진거 같기도 한데.. 말이죠..원래 주던 거에 (-)를 추가해서 이렇게 느낀 것 같아요.. 차라리 돈을 줄이고 다르게 광고보고 뭘 얻게끔 추가해주시든지요ㅠ 원래 그냥 주던걸 받았을뿐인데 그 댓가로 뭘해라 시키는거 같아서 좀 섭섭....앞으로도 지켜보겠어요 토스...👀<img src="https://image.until.blog/ssunj/article/1719981889772" alt="until-703">

토스 만보기의 UX에 관하여

CodingTest

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/challenges?order=recent">Programmers</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/courses/30/lessons/42747">H - Index</a></li><li>사용언어 : C#</li><li>난이도 : 중상</li><li>풀이시간 : 1h 49m</li><li>유형 : 정렬, 문제이해, 인덱스</li></ul><h6>문제 설명</h6>H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과<a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/courses/30/lessons/42747#fn1">1</a>에 따르면, H-Index는 다음과 같이 구합니다.어떤 과학자가 발표한 논문 <code spellcheck="false">n</code>편 중, <code spellcheck="false">h</code>번 이상 인용된 논문이 <code spellcheck="false">h</code>편 이상이고 나머지 논문이 h번 이하 인용되었다면 <code spellcheck="false">h</code>의 최댓값이 이 과학자의 H-Index입니다.어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.<h5>제한사항</h5><ul><li>과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.</li><li>논문별 인용 횟수는 0회 이상 10,000회 이하입니다.</li></ul><h5>입출력 예</h5>citations return [3, 0, 6, 1, 5] 3<h5>입출력 예 설명</h5>이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다. ** H-Index 이해 필요 <a target="_blank" rel="noopener noreferrer nofollow" href="https://en.wikipedia.org/wiki/H-index">링크</a><h3>문제 풀이 접근</h3>이 문제는, 문제의 불친절함 때문에 여러번 낚였다. 구현과 생각을 4번 정도 변경해서 오래걸렸다. 여기서 말하는 H-Index의 비교수는 결코 Element의 값이 아니라 순수 Loop 되는 Index 로 생각하면 편하다. 문제를 다 풀고나서 생각이지만, 정말 이해하기 어려웠다. 위키피디아 보고나서 5분만에 고쳐서 해결했다. 이 문제의 플로우는, 1. 받은 배열을 정렬한다. (내림차순) 2. 진행한 인덱스 i 의 값을 만족하지 못하는 수가 발견되면 break 해도 좋고, i 의 값 이상 인용된 논문을 찾아서 answer에 넣어주면 쉽게 풀린다.<h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code>using System;
using System.Collections.Generic;

public class Solution {
 public int solution(int[] citations) {
 int answer = 0;
 Array.Sort(citations);
 List&lt;int&gt; list = new List&lt;int&gt;();
 
 if(citations.Length == 1)
 return citations[0];
 
 for(int i =0; i &lt; citations.Length; ++i)
 list.Add(citations[i]);
 
 list.Sort((int a, int b)=&gt;{return b.CompareTo(a);});
 
 for(int i = 0; i &lt; list.Count; ++i)
 {
 int index = i+1;
 int count = list.FindAll(rhs=&gt; rhs &gt;= index).Count;
 
 if(index &lt;= count)
 answer = index;
 }

 return answer;
 }
}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1724185496584" alt="until-1259">다시 생각해봐도 정말 시간 아까웠다. 더빨리 풀 수 있었는데.. 다시 푸는 것으로 동일한 문제에 대한 포스팅이 있다. <a target="_blank" rel="noopener noreferrer nofollow" href="https://until.blog/@sin0105/-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9D%BC%EC%A7%80---99%ED%81%B4%EB%9F%BD--2%EC%9D%BC%EC%B0%A8---h-index">링크</a>

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

코딩테스트 준비 - H - Index

<h3>config\filesystem.php 내용 추가</h3><pre spellcheck="false"><code class="language-php"> 'custom' =&gt; [
 'driver' =&gt; 'local',
 'root' =&gt; 'D:/Data',
 ],</code></pre>이름은 custom으로 지정했고, 호스팅 경로는 C:\xampp\~~~~ 이지만데이터는 D:\Data 라는 경로에 저장되도록 하려면 config\filesystem.php를 수정한다.결과물은 아래와 같다.<h3>config\filesystem.php</h3><pre spellcheck="false"><code class="language-php"> 'disks' =&gt; [
 'custom' =&amp;gt; [
 'driver' =&amp;gt; 'local',
 'root' =&amp;gt; 'D:/Data',
 ],

 'local' =&amp;gt; [
 'driver' =&amp;gt; 'local',
 'root' =&amp;gt; storage_path('app'),
 'throw' =&amp;gt; false,
 ],

 'public' =&amp;gt; [
 'driver' =&amp;gt; 'local',
 'root' =&amp;gt; storage_path('app/public'),
 'url' =&amp;gt; env('APP_URL').'/storage',
 'visibility' =&amp;gt; 'public',
 'throw' =&amp;gt; false,
 ],&lt;/code&gt;&lt;/pre&gt;&lt;p&gt;&lt;/p&gt;&lt;h3&gt;UploadForm.php&lt;/h3&gt;&lt;pre spellcheck="false"&gt;&lt;code class="language-php"&gt;&amp;lt;?phpnamespace App\Livewire;use Livewire\Attributes\Rule;
use Livewire\Component;
use Livewire\WithFileUploads;class UploadForm extends Component
{
use WithFileUploads;#[Rule('required|file|max:102400')] // 1GB Max
public $attachFile;

public function uploadFile()
{
 session()-&amp;gt;flash('message', 'File uploaded successfully: ');
 $this-&amp;gt;validate();

 // 'custom'으로 맵핑된 경로에 'attachFile'이라는 폴더에 저장한다. (없으면 자동 생성)
 $path = $this-&amp;gt;attachFile-&amp;gt;store('attachFile', 'custom');
}

public function render()
{
 return view('livewire.upload-form');
}}</code></pre>아래 명령을 통해 config\livewire.php 파일 생성<pre spellcheck="false"><code>php artisan livewire:publish --config</code></pre>livewire 설정에서 disk를 아까 설정한 custom으로 지정해주고 rules를 적절히 설정해준다.<pre spellcheck="false"><code class="language-php">
 'temporary_file_upload' =&gt; [
 'disk' =&gt; 'custom', // Example: 'local', 's3' | Default: 'default'
 'rules' =&gt; 'file|max:1048576', // Example: ['file', 'mimes:png,jpg'] | Default: ['required', 'file', 'max:12288'] (12MB)
 'directory' =&gt; null, // Example: 'tmp' | Default: 'livewire-tmp'
 'middleware' =&gt; null, // Example: 'throttle:5,1' | Default: 'throttle:60,1'
 'preview_mimes' =&gt; [ // Supported file types for temporary pre-signed file URLs...
 'png', 'gif', 'bmp', 'svg', 'wav', 'mp4',
 'mov', 'avi', 'wmv', 'mp3', 'm4a',
 'jpg', 'jpeg', 'mpga', 'webp', 'wma',
 ],
 'max_upload_time' =&gt; 5, // Max duration (in minutes) before an upload is invalidated...
 'cleanup' =&gt; true, // Should cleanup temporary uploads older than 24 hrs...
 ],</code></pre>

config\filesystem.php 내용 추가        'custom' =&gt; [
            'driver' =&gt; 'local',
            'root' =&gt; 'D:/Data',
        ],이름은 custom으로 지정했고, 호스팅 경로는 C:\xampp\    'custom' =&amp;gt; [
     

File upload 저장 경로 지정하기

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li>응시 사이트 :<a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/"> </a><a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/challenges?order=recent">Programmers</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/courses/30/lessons/12909?language=csharp">올바른 괄호</a></li><li>사용언어 : C#</li><li>난이도 : 최하</li><li>풀이시간 : 이전 문제랑 똑같은 유형, <a target="_blank" rel="noopener noreferrer nofollow" href="https://until.blog/@sin0105/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%A4%80%EB%B9%84---%EA%B8%B0%EB%8A%A5-%EA%B0%9C%EB%B0%9C-i67t26g3">링크</a></li><li>유형 : 스택, 문자열</li></ul><h6>문제 설명</h6>괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어<ul><li>"()()" 또는 "(())()" 는 올바른 괄호입니다.</li><li>")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.</li></ul>'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.<h5>제한사항</h5><ul><li>문자열 s의 길이 : 100,000 이하의 자연수</li><li>문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.</li></ul><hr><h5>입출력 예</h5>sanswer"()()"true"(())()"true")()("false"(()("false<h5>입출력 예 설명</h5>입출력 예 #1,2,3,4 문제의 예시와 같습니다.<h3>문제 풀이 접근</h3>이 문제는, 보자마자 이전에 풀었던 문제랑 동일한 문제로 판단하여 이전에 풀었던 코드를 그대로 넣어서 패스했다. 코드 동일하게 넣어서 패스했고, 관련 코드와 완료 사진만 첨부. <a target="_blank" rel="noopener noreferrer nofollow" href="https://until.blog/@sin0105/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%A4%80%EB%B9%84---%EA%B8%B0%EB%8A%A5-%EA%B0%9C%EB%B0%9C-i67t26g3">링크</a><h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code>using System.Collections.Generic;

public class Solution {
 public bool IsValid(string s)
 {
 bool answer = false;
 Stack&lt;Char&gt; st = new Stack&lt;Char&gt;();

 if ((s.Length == 0) || (s[0] == ')') || (s[0] == '}') || (s[0] == ']'))
 return false;


 for (int i = 0; i &lt; s.Length; ++i)
 {
 var elem = s[i];

 if (elem == '(' || elem == '{' || elem == '[')
 {
 st.Push(elem);
 continue;
 }

 if (elem == ')' || elem == '}' || elem == ']')
 {
 char sElem;

 if(st.Count == 0)
 st.Push(elem);

 sElem = st.Peek();

 if (sElem == '(' &amp;&amp; elem == ')')
 {
 st.Pop();
 continue;
 }

 if (sElem == '[' &amp;&amp; elem == ']')
 {
 st.Pop();
 continue;
 }

 if (sElem == '{' &amp;&amp; elem == '}')
 {
 st.Pop();
 continue;
 }

 break;
 }
 }

 answer = st.Count == 0 ? true : false;

 return answer;
 }
}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1722482945818" alt="until-1170">

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

코딩테스트 준비 - 올바른 괄호

<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>코딩 테스트 준비 일지 17 일차</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" class="no-underline hover:text-blue-s dark:hover:text-dark-blue-s truncate cursor-text whitespace-normal hover:!text-[inherit]" href="https://leetcode.com/problems/minimum-suffix-flips/">Minimum Suffix Flips</a></li><li>난이도 : 중하</li><li>풀이시간 : 1h 03m</li></ul>You are given a&nbsp;0-indexed&nbsp;binary string&nbsp;<code spellcheck="false">target</code>&nbsp;of length&nbsp;<code spellcheck="false">n</code>. You have another binary string&nbsp;<code spellcheck="false">s</code>&nbsp;of length&nbsp;<code spellcheck="false">n</code>&nbsp;that is initially set to all zeros. You want to make&nbsp;<code spellcheck="false">s</code>&nbsp;equal to&nbsp;<code spellcheck="false">target</code>.In one operation, you can pick an index&nbsp;<code spellcheck="false">i</code>&nbsp;where&nbsp;<code spellcheck="false">0 &lt;= i &lt; n</code>&nbsp;and flip all bits in the&nbsp;inclusive&nbsp;range&nbsp;<code spellcheck="false">[i, n - 1]</code>. Flip means changing&nbsp;<code spellcheck="false">'0'</code>&nbsp;to&nbsp;<code spellcheck="false">'1'</code>&nbsp;and&nbsp;<code spellcheck="false">'1'</code>&nbsp;to&nbsp;<code spellcheck="false">'0'</code>.Return&nbsp;the minimum number of operations needed to make&nbsp;<code spellcheck="false">s</code>&nbsp;equal to&nbsp;<code spellcheck="false">target</code>.&nbsp;Example 1:<pre spellcheck="false"><code>Input: target = "10111"
Output: 3
Explanation: Initially, s = "00000".
Choose index i = 2: "00000" -&gt; "00111"
Choose index i = 0: "00111" -&gt; "11000"
Choose index i = 1: "11000" -&gt; "10111"
We need at least 3 flip operations to form target.
</code></pre>Example 2:<pre spellcheck="false"><code>Input: target = "101"
Output: 3
Explanation: Initially, s = "000".
Choose index i = 0: "000" -&gt; "111"
Choose index i = 1: "111" -&gt; "100"
Choose index i = 2: "100" -&gt; "101"
We need at least 3 flip operations to form target.
</code></pre>Example 3:<pre spellcheck="false"><code>Input: target = "00000"
Output: 0
Explanation: We do not need any operations since the initial s already equals target.
</code></pre>Constraints:<ul class="tight" data-tight="true"><li><code spellcheck="false">n == target.length</code></li><li><code spellcheck="false">1 &lt;= n &lt;= 100000(10^5)</code></li><li><code spellcheck="false">target[i]</code>&nbsp;is either&nbsp;<code spellcheck="false">'0'</code>&nbsp;or&nbsp;<code spellcheck="false">'1'</code>.</li></ul><h3>문제 풀이 접근</h3>금일 문제 풀이는 하면서 여러가지를 생각해봤다. 1. 1이 연속된 구간 섹션을 나누고 나눠진 갯수 출력하는 방식. 2. 주어진 문자열을 뒤부터 순환해서 마지막의 문자를 기억했다가 달라지는 인덱스를 삭제하는 방법 3. 앞에서부터 순환해서 다를때마다 카운트 올리고 출력하는 방식. 결국 위 3가지는 뭐 구간을 어떻게 나누고, 달라진것을 캐치하고 하는 방식에서 일단 명맥상 다 비슷하다. 틀린 코드도 결국 조금만 수정하면 다 풀릴 코드 였겠지만, 타임리밋은 조금 고민을 해봐야하긴한다. 인덱스 이하 좌측은 고려안해도 Remove 나, 새롭게 string 을 만드는 부분에서 뭔가 문제가 있는듯하다.문제 풀이 플로우는 아래와 같다. 1. target에 1이 하나도 없다 == 즉 0으로 범벅이다. =&gt; 바꿀게 없다 0번 플립하면된다. 2. 내가 현재 기준이 될 문자열 하나를 선언한다. ( 문제에서 target.Length에 맞게 0으로 채운다했으니 초기에는 0으로 잡는다.) 3. 앞에서부터 인덱스를 넘겨가면서 내가 저장한 문자열과 다르면 내 기준 문자열을 변경하고 answer를 하나 올린다. 4. 끝까지 돌면 answer 반환하고 종료한다.이 문제는 결국, 내가 쓰여진 것과 다르면 내 문자를 바꾸고 카운터 올리는 것이다. 플립 실제로 구현할 필요도 없다.문제 풀면서 든 생각이지만 2차선 타다가 앞에 차를 만나서 1차선 갔다가 1차선에서 차를 또만나면 2차선 갔다가 이런 느낌으로 연산하면 이해가 편할것 같기도하다. 내가 2차선 -&gt; 1차선 ( 플립 + 1) , 1차선 -&gt; 2차선 ( 플립 +1 ) 하는 느낌을 받았기 때문이다.<h3>실패한 코드 (Wrong Answer - 1번 방식) </h3><pre spellcheck="false"><code>public class Solution {
 public int MinFlips(string target) {
 // 10111
 
 // 00111
 // 11000
 // 10111
 string origin = string.Empty;

 for(int i=0; i &lt; target.Length;++i)
 origin += 0;

 int answer = 0;

 if(origin == target)
 return answer;

 string[] seperate = target.Split('0');
 answer = seperate.Length+1;

 return answer;
 }
}</code></pre><h3>실패한 코드 (Time Limit Exceeded - 2번 방식) </h3><pre spellcheck="false"><code>public class Solution {
 public int MinFlips(string target) {
 // 10111
 
 // 00111
 // 11000
 // 10111
 string origin = string.Empty;

 for(int i=0; i &lt; target.Length;++i)
 origin += 0;

 int answer = 0;

 if(origin == target)
 return answer;

 while(true)
 {
 if(origin == target)
 return answer;

 for(int i = 0; i &lt; target.Length; ++i)
 {
 if(origin[i] == target[i]) continue;

 filp(ref origin, i);
 break;
 }

 ++answer;
 }

 return answer;
 }

 public void filp(ref string target, int index)
 {
 for(int i = index; i &lt; target.Length; ++i)
 {
 char character = target[i];

 if(character == '0')
 {
 char[] charArr = target.ToCharArray(0,target.Length);
 charArr[i] = '1';
 target = new string(charArr);
 }
 else
 {
 char[] charArr = target.ToCharArray(0,target.Length);
 charArr[i] = '0';
 target = new string(charArr);
 }
 }
 
 }
}</code></pre><h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code>public class Solution
 {
 public int MinFlips(string target)
 {
 int answer = 0;

 if (target.Contains("1") == false)
 return answer;

 char nowChar = '0';

 for(int i = 0; i &lt; target.Length;++i)
 {
 if (target[i]!=nowChar)
 {
 nowChar = target[i];
 ++answer;
 }
 }

 return answer;
 }
 }</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1718721723647" alt="until-540">

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

[코딩테스트 일지 - 99클럽] 17일차 - Minimum Suffix Flips

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/">Programmers</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/courses/30/lessons/1844">게임맵 최단거리</a></li><li>사용언어 : C#</li><li>난이도 : 중</li><li>풀이시간 : 1h 36m</li><li>유형 : BFS, DFS</li></ul><h2>문제</h2><h6>문제 설명</h6>ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다. 아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.<ul><li>첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.</li><li>두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.</li></ul>위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.<h5>제한사항</h5><ul><li>maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.<ul><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<h5>입출력 예 설명</h5>입출력 예 #1 주어진 데이터는 다음과 같습니다.캐릭터가 적 팀의 진영까지 이동하는 가장 빠른 길은 다음 그림과 같습니다.따라서 총 11칸을 캐릭터가 지나갔으므로 11을 return 하면 됩니다.입출력 예 #2 문제의 예시와 같으며, 상대 팀 진영에 도달할 방법이 없습니다. 따라서 -1을 return 합니다.<h3>문제 풀이 접근</h3>이 문제는 최단거리를 구한다는 점에서 BFS를 이용하여 풀어야 한다. 그러나 DFS로 처음부터 구현해서 예상보다 많은 시간이 걸렸다. map을 받아서 BFS로 상하좌우를 서치해서 +1 씩 연산한다음 도달좌표가 고정되었기 때문에, 처음 입력받은 maps 의 GetLength를 이용해 n, m 의 값을 인덱스 참조해서 출력하면 된다.<h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code>using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Diagnostics;
using System.Linq;
using System.Text;
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
 {
 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, 0, 1, 1, 1 }, { 1, 0, 1, 0, 1 }, { 1, 0, 1, 1, 1 }, { 1, 1, 1, 0, 0 }, { 0, 0, 0, 0, 1 } };
 // //TC 3 
 //int[,] map = { { 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 s = new Solution();
 s.solution(map);
 }
 }


 class Solution
 {
 // /*
 // * [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]
 // */

 // 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]
 // */

 public int n;
 public int m;
 // 1 &lt;= n,m &lt;= 100

 public int[] dx = new int[4] { 0, 0, -1, 1 };
 public int[] dy = new int[4] { 1, -1, 0, 0 };
 // 상하좌우 순서

 public int[,] originMaps;
 // 원래 맵, 이것은 Visit, 갈 수 있는 길 모두를 판단가능

 public bool[,] isVisited;

 public int startX;
 public int startY;

 public int solution(int[,] maps)
 {
 n = maps.GetLength(0);
 m = maps.GetLength(1);

 if (n == 1 &amp;&amp; m == 1)
 return 1;

 originMaps = maps;
 isVisited = new bool[n, m];

 startX = 0;
 startY = 0;

 BFS(startX, startY);

 return originMaps[n - 1, m - 1] == 1 ? -1 : originMaps[n - 1, m - 1];
 }

 public void BFS(int x, int y)
 {
 Queue&lt;(int, int)&gt; q = new Queue&lt;(int, int)&gt;();
 q.Enqueue((x, y));

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

 int posX = top.Item1;
 int posY = top.Item2;

 if ((n - 1) == posX &amp;&amp; (m - 1) == posY)
 return;

 for (int i = 0; i &lt; 4; ++i)
 {
 int newPosX = posX + dx[i];
 int newPosY = posY + dy[i];

 if (isSafetyArea(newPosX, newPosY) == false)
 continue;

 if (originMaps[newPosX, newPosY] != 1)
 continue;

 q.Enqueue((newPosX, newPosY));
 originMaps[newPosX, newPosY] = originMaps[posX, posY] + 1;
 }
 }
 }

 public bool isSafetyArea(int newX, int newY)
 {
 if (newX &lt; 0 || newX &gt;= n || newY &lt; 0 || newY &gt;= m)
 return false;

 return true;
 }
 }
}</code></pre>이전 문제를 다시 푼 포스팅이기 때문에, 포스팅이 있다. <a target="_blank" rel="noopener noreferrer nofollow" href="https://until.blog/@sin0105/-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9D%BC%EC%A7%80---99%ED%81%B4%EB%9F%BD--6%EC%9D%BC%EC%B0%A8---%ED%83%80%EA%B2%9F-%EB%84%98%EB%B2%84">링크</a>

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

코딩테스트 준비 - 게임맵 최단거리

[자료구조와실습]

<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>다시푸는 코딩 테스트 준비 일지</h3><ul><li>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://www.acmicpc.net/">BOJ</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://www.acmicpc.net/problem/1312">1312.소수</a></li><li>사용언어 : C#</li><li>난이도 : 하</li><li>풀이시간 : 약 25m</li><li>유형 : 수학</li></ul><h2>문제</h2>피제수(분자) A와 제수(분모) B가 있다. 두 수를 나누었을 때, 소숫점 아래 N번째 자리수를 구하려고 한다. 예를 들어, A=3, B=4, N=1이라면, A÷B=0.75 이므로 출력 값은 7이 된다.<h2>입력</h2>첫 번째 줄에 A와 B(1 ≤ A, B ≤ 100,000), N(1 ≤ N ≤ 1,000,000)이 공백을 경계로 주어진다.<h2>출력</h2>A÷B를 했을 때, 소숫점 아래 N번째 수를 출력한다.<h2>예제 입력 1</h2><pre spellcheck="false"><code>25 7 5
</code></pre><h2>예제 출력 1</h2><pre spellcheck="false"><code>2</code></pre><h3>문제 풀이 접근</h3>이 문제는, 단순하게 a / b 한 후, mathf.pow(10,n) 해서 끌어올려서 % 10 으로 찾으면 쉽게 찾을 것처럼 생긴 문제여서, 나 또한 이렇게 접근했다. 다만, n이 상당히 높은수인 1,000,000 까지 할 수 있기 때문에, 끌어올려서 하는 방식은 애매했다.원리를 정확하게 알 수 없어 잡고 있는 것 보다 빠르게 풀고 이해하는 것이 전략적이라고 판단하여 힌트를 보고 풀었다. 힌트 : 초등과정 수학 나눗셈먼저 그림을 보면 간단한 수학 나눗셈이다. <img src="https://image.until.blog/sin0105/article/1726084591823.png" alt="until-1336">이걸 보고 만들어 낸 이 문제의 플로우는 아래와 같다. 1. 나머지 값을 10을 곱해 a 에 갱신해준다. (a = a % b * 10) 2. a / b 의 몫 값은 그 회차의 해당 자리 수 이다 . ex) n == 1 , a = 40 , mok = 5 -- 1번째 소수 자릿 수 ex) n == 2 , a = 50 , mok = 7 -- 2번째 소수 자릿 수 ex) n == 3 , a = 10 , mok = 1 -- 3번째 소수 자릿 수 등등 3. n 번째 까지 for 문을 통해 loop 하면서 가장 최근까지 입력된 mok 의 값을 그대로 출력<h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code>using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.ComponentModel.Design;
using System.Diagnostics;
using System.IO;
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;
using static CodingTestProj.Program;

/*
 * URL : https://www.acmicpc.net/problem/1312
 */

namespace CodingTestProj
{
 internal class Program
 {
 static void Main(string[] args)
 {
 string[] inputs = Console.ReadLine().Split(' ');

 int a = Int32.Parse(inputs[0]);
 int b = Int32.Parse(inputs[1]);
 int n = Int32.Parse(inputs[2]);

 int ret = Solution.Prog(a,b,n);
 Console.WriteLine(ret);
 }
 }

 public static class Solution
 {
 public static int Prog(int a, int b, int n)
 {
 int ret = 0;
 int mok = 0;

 for (int i = 0; i &lt; n; ++i)
 {
 a = (a % b) * 10;
 mok = (a / b);
 }

 ret = mok;
 return ret;
 }
 }
}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1726084964706.png" alt="until-1337">

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

코딩테스트 준비 - 소수

<h3>코딩 테스트 준비 일지 14 일차</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" class="no-underline hover:text-blue-s dark:hover:text-dark-blue-s truncate cursor-text whitespace-normal hover:!text-[inherit]" href="https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/">Capacity To Ship Packages Within D Days</a></li><li>난이도 : 중상</li><li>풀이시간 : 1h 39m</li></ul>A conveyor belt has packages that must be shipped from one port to another within <code spellcheck="false">days</code> days.The <code spellcheck="false">ith</code> package on the conveyor belt has a weight of <code spellcheck="false">weights[i]</code>. Each day, we load the ship with packages on the conveyor belt (in the order given by <code spellcheck="false">weights</code>). We may not load more weight than the maximum weight capacity of the ship.Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within <code spellcheck="false">days</code> days.Example 1:<pre spellcheck="false"><code>Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10
Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.</code></pre>Example 2:<pre spellcheck="false"><code>Input: weights = [3,2,2,4,1,4], days = 3
Output: 6
Explanation: A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4</code></pre>Example 3:<pre spellcheck="false"><code>Input: weights = [1,2,3,1,1], days = 4
Output: 3
Explanation:
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1</code></pre>Constraints:<ul class="tight" data-tight="true"><li><code spellcheck="false">1 &lt;= days &lt;= weights.length &lt;= 5 * 104</code></li><li><code spellcheck="false">1 &lt;= weights[i] &lt;= 500</code></li></ul><h3>문제 풀이 접근</h3>이 문제 풀이는 단번에 접근할 수 없었다. 이분탐색 개념도 희미해져서 잘 몰랐을 뿐더러, 풀면서 이분탐색이 뭐였지? 하면서 개념을 다시 살펴보고 문제를 다시확인했다. 처음 설정한 방향성은 List 를 하나 더만들어서 [1,2,3,4,5,6,7,8,9,10]이 있다면, 이분 탐색으로 중간지점 인덱스 5, value 6 이하의 값을 1,2,3,4,5 해서 선적에 넣고 리스트 앞에서 다 날리고 이후에 [6,7,8,9,10] 에서 또 중간지점 인덱스 2 , value 8 이하의 점을 날리고 [8,9,10] 에서 8 날리고 9 날리고 10 날리고 하면 딱 될것 같아서 생각을 해봤으나, 3번의 예시가 보기좋게 응 아니야라는 메시지를 날렸다.결국 혼자 풀지못하고 풀이 영상을 확인하니 그제서야 접근 방식을 알았다. 방식은 인덱스로 이분탐색하면 안되는 것이 핵심이었다. 1. 무게 중 가장 큰 값이 Left 로 들어가고, 모든 무게의 합이 Right 로 들어간다 . 2. 여기서 조건에 따라 양 사이드를 땡기는 투포인터 느낌으로다가 L = mid + 1, R = mid -1 로 범위를 당겨온다. 3. 조건은 CalcDays &gt;= days 일 경우, Low = mid + 1 을 한다. ( 이 경우, 선적의 중량이 부족하다는 소리, 그래서 결국 몇일 더걸린다는 얘기니까 Low 를 땡겨서 선적의 중량을 올린다.) 반대 조건인 else 구문은 High = mid - 1 을 한다. ( 중량이 차고 넘치니까, 예산일정보다 빨리 끝난다는 얘기다. 그러니, 선적의 중량을 낮춘다.)<h3>예시 풀이</h3>2번이 테스트 하면서 잘 안됐었어서 2번으로 예시 풀이 하겠다.<pre spellcheck="false"><code>Input: weights = [3,2,2,4,1,4], days = 3
Output: 6
Explanation: A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4</code></pre>이 중 가장 큰 값인 4, 를 Left, 모든 합 16 을 Right , mid 값은 이 중간 값 ( m 은 여기서 선적 용량 ) L = 4 , R = 16 , M = 10 M = 10 일때, CalcDays [3,2,2] , [4,1,4] =&gt; 2로 끝난다. 선적의 중량이 많다. 낮춘다. R = M - 1 로 변경 L = 4, R = 9 , M = 6 M = 6 일때, CalcDays [3,2] [2,4] [1,4] =&gt; 3그룹 이지만 실제 CalcDays 는 2 이다. 당긴다. R = 6 - 1 = 5 L = 4 , R = 5 , M = 5 M = 5 일때, CalcDays [3,2] [2] [4] [3,1] =&gt; 4, CalcDays &gt; Days L = 5 + 1 로 놓는다. While ( Left &lt;= Right ) 의 조건으로 빠져나와 Left를 반환하면 최적의 값을 출력할 수 있다.<h3>작성 코드</h3><pre spellcheck="false"><code>using System.Collections.Generic;
public class Solution {
public int ShipWithinDays(int[] weights, int days) { int low = 0;
 int high = 0;
 int mid = 0;

 for(int i = 0; i &amp;lt; weights.Length; ++i)
 {
 high += weights[i];
 low = Math.Max(low, weights[i]);
 }

 // 용량을 기준으로 BS 한다.
 // 예시 1번으로는, [10, 55] 로 BS 진행한다.
 

 while(low &amp;lt;= high)
 {
 int calcDays = 0; // 산정된 일 수 
 int nowSum = 0;

 mid = (low + high) / 2; // 용량

 for(int i = 0; i &amp;lt; weights.Length; ++i)
 {
 if(nowSum + weights[i] &amp;gt; mid)
 {
 // 현재 용량 선적보다 많다. 일 수를 추가해야함.
 nowSum =0;
 ++calcDays;
 }

 nowSum += weights[i];
 }

 // 여기서 용량 선적이 남으면, 다시 최적을 찾는다. 
 if(calcDays &amp;gt;= days)
 low = mid + 1;
 else 
 high = mid - 1;
 }

 return low;
}}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1718156679033" alt="until-457">

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

[코딩테스트 일지 - 99클럽] 14일차 - Capacity To Ship Packages Within D Days

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/challenges?order=recent"> </a><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/count-pairs-whose-sum-is-less-than-target/">Count Pairs Whose Sum is Less than Target</a></li><li>사용언어 : C#</li><li>난이도 : 최하</li><li>풀이시간 : 1m 49s</li><li>유형 : 반복문, 사칙연산</li></ul>Given a 0-indexed integer array <code spellcheck="false">nums</code> of length <code spellcheck="false">n</code> and an integer <code spellcheck="false">target</code>, return the number of pairs <code spellcheck="false">(i, j)</code> where <code spellcheck="false">0 &lt;= i &lt; j &lt; n</code> and <code spellcheck="false">nums[i] + nums[j] &lt; target</code>. &nbsp;Example 1:<pre spellcheck="false"><code>Input: nums = [-1,1,2,3,1], target = 2
Output: 3
Explanation: There are 3 pairs of indices that satisfy the conditions in the statement:
- (0, 1) since 0 &lt; 1 and nums[0] + nums[1] = 0 &lt; target
- (0, 2) since 0 &lt; 2 and nums[0] + nums[2] = 1 &lt; target 
- (0, 4) since 0 &lt; 4 and nums[0] + nums[4] = 0 &lt; target
Note that (0, 3) is not counted since nums[0] + nums[3] is not strictly less than the target.
</code></pre> Example 2:<pre spellcheck="false"><code>Input: nums = [-6,2,5,-2,-7,-1,3], target = -2
Output: 10
Explanation: There are 10 pairs of indices that satisfy the conditions in the statement:
- (0, 1) since 0 &lt; 1 and nums[0] + nums[1] = -4 &lt; target
- (0, 3) since 0 &lt; 3 and nums[0] + nums[3] = -8 &lt; target
- (0, 4) since 0 &lt; 4 and nums[0] + nums[4] = -13 &lt; target
- (0, 5) since 0 &lt; 5 and nums[0] + nums[5] = -7 &lt; target
- (0, 6) since 0 &lt; 6 and nums[0] + nums[6] = -3 &lt; target
- (1, 4) since 1 &lt; 4 and nums[1] + nums[4] = -5 &lt; target
- (3, 4) since 3 &lt; 4 and nums[3] + nums[4] = -9 &lt; target
- (3, 5) since 3 &lt; 5 and nums[3] + nums[5] = -3 &lt; target
- (4, 5) since 4 &lt; 5 and nums[4] + nums[5] = -8 &lt; target
- (4, 6) since 4 &lt; 6 and nums[4] + nums[6] = -4 &lt; target
</code></pre>Constraints:<ul><li><code spellcheck="false">1 &lt;= nums.length == n &lt;= 50</code></li><li><code spellcheck="false">-50 &lt;= nums[i], target &lt;= 50</code></li></ul><h3>문제 풀이 접근</h3>문제의 내용이 어렵지 않다. 제약조건 또한 어렵지 않다. 반복문 두개로 타겟 넘버와 비교하여 풀이할 수 있는 내용이다. <h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code>public class Solution {
 public int CountPairs(IList&lt;int&gt; nums, int target) {
 
 int answer = 0;
 
 for(int i = 0; i &lt; nums.Count; ++i)
 {
 for(int j = i + 1; j &lt; nums.Count; ++j)
 {
 int fst = nums[i];
 int snd = nums[j];
 
 if(fst + snd &lt; target)
 ++answer;
 }
 }
 return answer;
 }
}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1724176666815" alt="until-1258">

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

코딩테스트 준비 - Count Pairs Whose Sum is Less than Target

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/challenges?order=recent">Programmers</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/courses/30/lessons/42746">가장 큰 수</a></li><li>사용언어 : C#</li><li>난이도 : 중하</li><li>풀이시간 : 1h13m</li><li>유형 : 정렬, 수 비교, 배열</li></ul><h6>문제 설명</h6>0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.<h5>제한 사항</h5><ul><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>이 문제에선 삽질을 많이해서 여러번 정답을 들이밀면서 해결해보았다. 1. 모든 조합을 구한 뒤, 큰 수 부터 정렬하여 구하는 방법 2. 문제에서 원소 크기는 1000 으로 고정되었기 때문에, 자릿 수를 10000만의 자리까지 끌고 올라와서 정렬하여 비교하는 방법 먼저, 1번은 효율성에서 좋지 않아 보인다. 일단 모든 조합수를 구하는 데 있어서, O(N^2) 이 들 수 밖에 없다. 모든 원소의 값을 다 구한 뒤 정렬도 수행해야하기 때문이다. 결국 O(N^2) + O(N Log N) 의 시간복잡도로 가정된다. ( 편의상 전부 적어보았음 ) 그렇다면 2번의 방법은 어떤게 다른가? 2번은 원소의 수를 잠시 5자리 이상의 수로 연산을한 뒤 정렬을 하면, 1번에서 O(N^2)는 안들고 정렬에 대한 시간 복잡도인 +O(N Log N) 정도만 들겠다. 그러면 수를 정렬하는 방법은 단순히 [6,10,2] 등과 같이 수가 다 다르다면 상관은 없을 수 있는데, [3,3000] 과 같이 앞자리가 같은수는 결국 3 * 10000 , 3000 * 10 을 하면 결국 30000으로 같다. 그렇기 때문에 자릿수를 맞추는 것은 수를 문자열로 바꾼 후 문자열의 길이만큼 Loop하여 추가한다. 그러면 33333 , 30003 이기 때문에, 3이 더 큰수로 나올 것이다. 이런 아이디어로 비교를 하여 정렬을 하게된다면 정답을 찾을 수 있다. 문제의 플로우는 아래와 같다. 1. Tuple을 이용하여, Key : 6자리 변경 수 , Value : 원래 수 2. Key 기준으로 정렬 3. List의 처음부터 끝까지 원래 수를 StringBuilder 에 Append 하면서 추가. 4. 그리고 Int32.Parse로 캐스팅하여 반환<h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code>using System;
using System.Text;
using System.Collections.Generic;

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

 if(numbers.Length == 1)
 {
 return numbers[0].ToString();
 }
 
 for(int i = 0; i &lt; numbers.Length; ++i)
 {
 if(numbers[i] == 0)
 ++isZero;
 }
 
 if(isZero == numbers.Length)
 {
 answer = "0";
 return answer;
 }
 
 
 // 모두 100000의 숫자로 변경해서 체크.
 List&lt;Tuple&lt;int,int&gt;&gt; list = new List&lt;Tuple&lt;int,int&gt;&gt;();
 
 for(int i = 0; i &lt; numbers.Length; ++i)
 { 
 int valueInt = numbers[i];
 int makeInt = MakeValue(valueInt);
 
 list.Add(new Tuple&lt;int,int&gt;(makeInt,valueInt));
 }
 
 var toArr = list.ToArray();
 
 Array.Sort(toArr, (a,b) =&gt; {return b.Item1.CompareTo(a.Item1);});
 
 StringBuilder sb = new StringBuilder();
 for(int i = 0; i &lt; toArr.Length; ++i)
 {
 var element = toArr[i];
 sb.Append(element.Item2);
 }
 
 answer = sb.ToString();
 return answer;
 }
 
 public int MakeValue(int valueInt)
 {
 int ret = 0;
 String valueString = valueInt.ToString();
 StringBuilder sb = new StringBuilder();
 int intIndex = 0;
 
 while(sb.Length != 6) // 비교는 10만으로 비교, 즉 6자리 수로 비교하겠다.
 {
 if(valueString.Length == intIndex)
 intIndex = 0;
 
 
 char element = valueString[intIndex];
 sb.Append(element);
 ++intIndex;
 }
 
 ret = Int32.Parse(sb.ToString());
 return ret;
 }
}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1724065391054" alt="until-1246">

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

코딩테스트 준비 - 가장 큰 수

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/challenges?order=recent">Programmers</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/problems/smallest-number-in-infinite-set/"> </a><a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/courses/30/lessons/42748">K번째수</a></li><li>사용언어 : C#</li><li>난이도 : 하</li><li>풀이시간 : 15m</li><li>유형 : 정렬, 배열, 리스트</li></ul><h6>문제 설명</h6>배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면<ol><li>array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.</li><li>1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.</li><li>2에서 나온 배열의 3번째 숫자는 5입니다.</li></ol>배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.<h5>제한사항</h5><ul><li>array의 길이는 1 이상 100 이하입니다.</li><li>array의 각 원소는 1 이상 100 이하입니다.</li><li>commands의 길이는 1 이상 50 이하입니다.</li><li>commands의 각 원소는 길이가 3입니다.</li></ul><h5>입출력 예</h5>array commands return [1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3]<h5>입출력 예 설명</h5>[1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다. [1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다. [1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.<h3>문제 풀이 접근</h3>이 문제는, 바로 읽히는대로 풀면 될 정도로 직관적인 문제다. 이 문제의 해결 플로우, 1. array를 주고, Command 를 준다. 2. 2차원 배열로 Command를 주기때문에 각 배열 하나하나가 커맨드이다. 3. {i,j,k} 로 주어질 때, i -&gt; j 까지 자르고 정렬하여 k 번째를 answer에 하나씩 넣어 반환<h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code>using System;
using System.Collections.Generic;

 public class Solution
 {
 public int[] solution(int[] array, int[,] commands)
 {
 int count = commands.GetLength(0);
 int[] answer;

 List&lt;int&gt; list = new List&lt;int&gt;();

 int loop = 0;

 for(int i = 0; i &lt; commands.GetLength(0); ++i)
 {
 var fst = commands[i,0] -1 ;
 var snd = commands[i, 1] - 1;
 var findIndex = commands[i, 2];

 var makeArrCount = snd - fst + 1;

 int[] processArr = new int[makeArrCount];

 int index = 0;
 for(int j = fst; j &lt;= snd; ++j)
 {
 processArr[index] = array[j];
 ++index;
 }

 Array.Sort(processArr);
 list.Add(processArr[findIndex - 1]);

 ++loop;
 }
 answer = list.ToArray();
 return answer;
 }
 }</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1723145153151" alt="until-1216">

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

코딩테스트 준비 - K번째수

안녕하세요. 투얼리입니다. 앞으로 그 때 그때 들은 앨범을 리스닝로그로 정리해 올릴 생각입니다. 잘 부탁드립니다!아래는 예시 이미지입니다.<img src="https://image.until.blog/tooearly/article/1716023988210" alt="until-65">

듣고 있는 앨범을 정리해 업로드합니다.