<h3>코딩 테스트 준비 일지 3 일차</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/42842">카펫</a></li><li>난이도 : 중</li></ul><h6>문제 설명</h6>Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.<img src="https://image.until.blog/sin0105/article/1716879329667" alt="until-326">Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.<h5>제한사항</h5><ul class="tight" data-tight="true"><li>갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.</li><li>노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.</li><li>카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.</li></ul><h5>입출력 예</h5>brown yellow return 10 2 [4, 3] 8 1 [3, 3] 24 24 [8, 6]<h3>문제 풀이 접근</h3>이 문제의 권장 풀이 시간은 1시간이었는데, 한번 풀이를 잘못 들어가서 1시간을 그냥 날리고 리셋해서 총 1시간 25분 정도 걸린것 같다. 방향을 잘못잡은 풀이는 최대한 이쁜 사각형만을 찾아서 감싸서 가로 세로 값 리턴해야지! 라는 안일한 생각으로 잘못 잡았다. 여기서 말한 최대한 이쁜 사각형이라는 것은 [18, 6] 이 주어졌을 때, [8, 3] 이 실제로 정답이나, 나는 가로 세로의 차이가 가장 적은 값인 [6, 4] 를 정답으로 판단해서 오류가 발생했던 문제였다. 직사각형이 정답이 될 수 있음을 무시하고, 정사각형에 최대한 가까운 것이 정답이라고 생각한 것에 대한 오류였다. 이렇게 문제를 풀면 풀리긴한다. 다만, 이 문제의 질문목록에 자주 올라오는 TC 4 6 7 나의 경우는 9 까지 패스할 수 없었다. 결론, 완벽한 정답이 아니다. ( 여기까지 했을때 1시간 지나버려서 리셋했다. )다시 문제를 읽고 공식을 작성해보았고, 이런식을 세웠다. 1. Brown = (Yellow 의 열 * 2 ) + { 2 ( Yellow + 2) } 충족 2. Yellow = ( Yellow 가로 값 * 세로 값 ) 충족이게 왜 이렇게 세워지냐면, 위의 [18, 6] 일 때, 6 이 Yellow 값인데, 3*2 인 Yellow 를 Brown이 감싸는 것에대해서 오류가 발생한다. Yellow 값 또한, 약수로 분해했다. [1, 6] , [2, 3], [3, 2], [6, 1] 총 4개의 집합이 나온다. 여기서 중복되는 조합은 필요없고, 가로가 세로보다 길기 때문에 [1, 6] =&gt; [6, 1] , [2, 3] =&gt; [3, 2] 로 변경해서 필터링해서 패스했다.결국 크게 보면 아래와 같이 3단계로 풀이가 정의된다. 1. Yellow 의 값을 약수 분해하라 2. Brown 공식과 Yellow 공식에 맞지 않으면 패스해라. 3. 최종적으로 나온 가로, 세로는 Yellow 의 가로 세로 값이기 때문에, 가로세로 두께인 2씩 더해서 출력하라. ( 세로의 경우 위 1 아래 1 , 가로의 경우 왼쪽 1 오른쪽 1 개씩 더있기 때문에, )<h3>방향 잘못 잡은 코드 작성 ( C# )</h3><pre spellcheck="false"><code>using System;

public class Solution {
 public int[] solution(int brown, int yellow) {
 int[] answer = new int[2];
 
 Tuple&lt;int, int&gt; pair = new Tuple&lt;int, int&gt;(0,0);
 int diffRecordValue = int.MaxValue;

 for(int i = 1; i &lt; 2000000; ++i)
 {
 if (i &gt; (yellow)) break;

 // yellow는 무조건 사각형이라는 가정, 정사각형, 직사각형 모두
 int balance = yellow % i;

 if (balance != 0) continue;
 // 사각형이 아니고 남으면 패스

 int div = yellow / i; // 나눠진 수

 int diffValue = Math.Abs(i - div);// 절댓값으로 차이를 구함. =&gt; 가장 가로세로 차이가 없는 이쁜 사각형을 구하기 위함.

 if (diffRecordValue &lt; diffValue) continue;
 diffRecordValue = diffValue;

 if ( i &gt; div )
 pair = new Tuple&lt;int, int&gt;(i, div);
 else
 pair = new Tuple&lt;int, int&gt;(div,i); 
 
 // 더 큰수가 가로
 }

 answer[0] = (pair.Item1) + 2;
 answer[1] = (pair.Item2) + 2;
 return answer;
 }
}</code></pre><h3>방향 잘못 잡은 결과 </h3><img src="https://image.until.blog/sin0105/article/1716880342820" alt="until-330"><h3>정답 작성 코드 ( C# )</h3><pre spellcheck="false"><code>using System;
using System.Collections.Generic;

public class Solution {
 public int[] solution(int brown, int yellow) {
 int[] answer = new int[2];
 
 // 공식
 // Brown = ( Yellow열 * 2 ) + 2 ( Yellow + 2 ) 성립

 // 분해된 수를 먼저 담아놓는다. 
 List&lt;Tuple&lt;int,int&gt;&gt; combinationList =new List&lt;Tuple&lt;int, int&gt;&gt;();

 for(int i = 1; i &lt;= yellow; ++i)
 {
 // Yellow 수 까지 분해해서 약수를 담아놓는다.
 int balance = yellow % i;
 if (balance != 0) continue; // 나누어 떨어지지 않으면 담을 필요 없다. 

 int div = yellow / i;
 if (combinationList.Exists(rhs =&gt; rhs.Item1 == div &amp;&amp; rhs.Item2 == i) == true) continue;
 if (combinationList.Exists(rhs =&gt; rhs.Item1 == i &amp;&amp; rhs.Item2 == div) == true) continue;
 // 중복된 애들 필터링 

 if (div &gt; i)
 combinationList.Add(new Tuple&lt;int, int&gt;(div, i));
 else
 combinationList.Add(new Tuple&lt;int, int&gt;(i,div));
 }

 // 이제 루프 돌면서 공식에 충족하는 애들을 추린다
 // Brown = ( Yellow + 2 ) + 2 ( Yellow + 2 ) 성립
 // Yellow = div * i 가 Yellow 성립

 for (int i = 0; i &lt; combinationList.Count; ++i)
 {
 var keyPair = combinationList[i];
 if (brown != (2* keyPair.Item1) + (2 * (keyPair.Item2 + 2))) continue;
 if (yellow != (keyPair.Item1 * keyPair.Item2)) continue;

 answer[0] = keyPair.Item1 + 2;
 answer[1] = keyPair.Item2 + 2;
 break;
 } 
 return answer;
 }
}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1716880421097" alt="until-331">

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

[코딩테스트 일지 - 99클럽] 3일차 - 카펫

<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>코딩 테스트 준비 일지 10 일차</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/42860">조이스틱</a></li><li>난이도 : 상</li><li>풀이시간 : 03 h ++</li></ul><h6>문제 설명</h6>조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA조이스틱을 각 방향으로 움직이면 아래와 같습니다.<pre spellcheck="false"><code>▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)</code></pre>예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.<pre spellcheck="false"><code>- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.</code></pre>만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.<h5>제한 사항</h5><ul class="tight" data-tight="true"><li>name은 알파벳 대문자로만 이루어져 있습니다.</li><li>name의 길이는 1 이상 20 이하입니다.</li></ul><h5>입출력 예</h5>name return "JEROEN" 56 "JAN" 23<h3>문제 풀이 접근</h3>이번 문제풀이는.. 도저히 미들러의 문제가 아니었다. 라고 생각이 들었다. 먼저 글자수대로 A를 준다는 것에도 잘 이해를 못했고, 이동하는것도 이해못했고, 그냥 모든걸 이해할 수 없던 문제였다.이 문제의 어려운 부분은 커서 이동의 최적화였다. 여러 사람들의 문제풀이가 있으나, 대부분의 문제풀이는 식과 Math.Min 을 이용하여 최소 이동을 구하는 것이었다. 커서 상하 이동은 단순히 아스키코드 개념을 알면 Math.Min(element - 'A' , 'Z' - element + 1) 과 같은 방식으로 충분히 구할 수 있는 것을 확인할 수 있다.이제 커서 이동이 가장 문제인데, 커서 이동은 준비 과정이 있다.가장 단순한 커서 이동은 오른쪽으로 이동하는 것인데, 이 이동은 정말 단순하다. 왼쪽 끝에서 오른쪽 끝으로 쭉 이동하는 것이다. 그래서 이런 식이 나온다. int move = name.Length -1; &lt;&lt; 이걸 기준으로 잡는다.그 이후에 어떻게 하느냐, 이제 왼쪽으로 가는것이 최적인지 오른쪽으로 가는것이 최적인지 정하는 것이다. 결국 나는 이 문제를 최대 55점 까지는 받고 풀이를 보았으나, 처음 보았을 때, 이게 무슨 말도 안되는 식인지 이해가 안갔다.나는 움직일 때마다, 인덱스를 저장해주고, 그 이동값에 대해서 계속 결과 반환값인 answer에 더해준다고 생각했으나, 많은 사람들의 풀이는 그 방식이 아니었다.이 문제에서 최소 커서를 조작하는 것이 핵심이므로, 1) 길이대로 오른쪽으로 이동하는 경우 2) 오른쪽으로 가다가, A 연속을만나 원점으로 돌아가서 맨 뒤에서 해결하는 방식 3) 맨뒤부터 순회해서 A 연속을 만나 원점으로 돌아가서 맨 앞에서 주르륵 해결하는 방식저 3 가지를 비교해서 최솟값을 건들면된다. PPAAAPER 라고 있을때, 3가지의 moveCount 를 만들 수 있다.1) length -1 = 7 2) PPAAAPER , PP 다음 ' A ' 를 만나 i 를 다시 원점으로 돌리고 A 연속의 뒤로 돌아가서 우측으로 이동하는 방식 =&gt; (2 * i) + (string.Length - nextIndex) 3) PPAAAPER , PPAAA 'P' 이쪽 P 부터 시작해 오른쪽 끝으로 순회하고 다시 A 연속의 왼쪽 지점으로 돌아와서 오른쪽으로 순회하는 방식 =&gt; i + 2 * (string.Length - nextIndex)<h3>정답 작성 코드 ( C# )</h3><pre spellcheck="false"><code>using System;
public class Solution {
public int solution(string name)
{
int answer = 0;
FindCountUpDown(ref name,ref answer);
MoveCount(ref name, ref answer);
return answer;
} public void FindCountUpDown(ref string name,ref int answer)
 // Up Down 하는 수들만 모아서 반환
 {
 for (int i = 0; i &amp;lt; name.Length; ++i)
 {
 char target = name[i];
 answer += Math.Min(target - 'A', 'Z' - target + 1) ;
 }
 }
 public void MoveCount(ref string name, ref int answer)
 {
 int move = name.Length - 1; // 최대값

 for (int i = 0; i &amp;lt; name.Length; ++i)
 {
 if (i == name.Length - 1) continue;

 int nextIndex = i + 1;
 while(nextIndex &amp;lt; name.Length &amp;amp;&amp;amp; name[nextIndex] == 'A')
 nextIndex++;

 move = Math.Min(move, (2 * i) + (name.Length) - nextIndex);
 move = Math.Min(move, i + 2* ((name.Length) - nextIndex));
 }
 answer += move;
 }}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1717520902703" alt="until-408">

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

[코딩테스트 일지 - 99클럽] 10일차 - 조이스틱

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/86491">최소직사각형</a></li><li>사용언어 : C#</li><li>난이도 : 하 ~ 중</li><li>풀이시간 : 45m 48s</li><li>유형 : 문제이해, 2차원 배열</li></ul><h6>문제 설명</h6>명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다.명함 번호 가로 길이 세로 길이 1 60 50 2 30 70 3 60 30 4 80 40가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다. 이때의 지갑 크기는 4000(=80 x 50)입니다.모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다. 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 하도록 solution 함수를 완성해주세요.<hr><h5>제한사항</h5><ul><li>sizes의 길이는 1 이상 10,000 이하입니다.<ul><li>sizes의 원소는 [w, h] 형식입니다.</li><li>w는 명함의 가로 길이를 나타냅니다.</li><li>h는 명함의 세로 길이를 나타냅니다.</li><li>w와 h는 1 이상 1,000 이하인 자연수입니다.</li></ul></li></ul><hr><h5>입출력 예</h5>sizes result [[60, 50], [30, 70], [60, 30], [80, 40]] 4000 [[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]] 120 [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]] 133<hr><h5>입출력 예 설명</h5>입출력 예 #1 문제 예시와 같습니다.입출력 예 #2 명함들을 적절히 회전시켜 겹쳤을 때, 3번째 명함(가로: 8, 세로: 15)이 다른 모든 명함보다 크기가 큽니다. 따라서 지갑의 크기는 3번째 명함의 크기와 같으며, 120(=8 x 15)을 return 합니다.입출력 예 #3 명함들을 적절히 회전시켜 겹쳤을 때, 모든 명함을 포함하는 가장 작은 지갑의 크기는 133(=19 x 7)입니다.<h3>문제 풀이 접근</h3>이 문제는, 가로x세로에서 모든 사각형을 포함하는 것 중 가장 작은 사각형을 만들면 되는 문제다. 문제에서 명함을 회전해서 포함한다. 라는 힌트를 줬기 때문에, 가로 &lt; 세로 의 케이스는 무조건 가로와 세로를 바꾸어주면 된다.문제를 잘못 읽어서 가로, 세로를 쌍으로보고 인덱스를 찾은 뒤 해당 인덱스 가로*세로 하면서 시간을 썻는데, 이 방법은 틀리다. 가로 세로는 따로 봐야한다.이 문제의 플로우는, 1. 받은 2차원 배열을 체크하여 가로 &lt; 세로의 케이스를 찾는다. 2. 그 다음 변경해서 list에 넣어준다. 3. 포함하는 것 중 가장 작은 최소 직사각형을 뽑는것이 주 목적이니, maxWidth, maxHeight 값은 Int32 표현범위중 제일 큰 값을 설정해놓는다. 4. list를 Loop 하면서 순회하는 원소 기준으로 list를 FindAll 함수를 이용해 찾는다. 이렇게 찾은 갯수가 현재 리스트 카운트와 동일하면 현재 원소는 가로 원소일땐 가로를 포함, 세로 원소일땐 세로를 포함한다. 리스트 내 고로 제일 큰 값이다. 5. 이 값 중 최소 직사각형을 뽑는 것이 목적이기 때문에 maxWidth &gt;= Width 를 비교하여 현재 저장된 원소보다 작다면 값을 넣어준다. 6. 이렇게 구해낸 maxWidth, maxHeight를 사각형의 크기를 구하는 공식에 따라 곱해서 반환한다.<h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code>using System;
using System.Collections.Generic;

public class Solution {
 public int solution(int[,] sizes) {
 int answer = 0;
 List&lt;Tuple&lt;int, int&gt;&gt; list = new List&lt;Tuple&lt;int, int&gt;&gt;();

 for(int i = 0; i &lt; sizes.GetLength(0); ++i)
 {
 int width = sizes[i, 0];
 int height = sizes[i, 1];

 if(width &lt; height)
 {
 int temp = height;
 height = width;
 width = temp;
 }

 list.Add(new Tuple&lt;int, int&gt;(width, height));
 }

 int maxWidth = Int32.MaxValue;
 int maxHeight = Int32.MaxValue;

 for(int i = 0; i &lt; list.Count; ++i)
 {
 var element = list[i];
 var width = element.Item1;
 var height = element.Item2;

 var countfst = list.FindAll(rhs =&gt; rhs.Item1 &lt;= width).Count;
 var countsnd = list.FindAll(rhs =&gt; rhs.Item2 &lt;= height).Count;

 if(list.Count == countfst)
 {
 if(maxWidth &gt;= width)
 maxWidth = width;
 }

 if(list.Count == countsnd)
 {
 if (maxHeight &gt;= height)
 maxHeight = height;
 }
 }

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

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

코딩테스트 준비 - 최소직사각형

<h3>코딩 테스트 준비 일지 5 일차</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/43165">타겟 넘버</a></li><li>난이도 : 중</li></ul>n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.<pre spellcheck="false"><code>-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3</code></pre>사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.<h5>제한사항</h5><ul class="tight" data-tight="true"><li>주어지는 숫자의 개수는 2개 이상 20개 이하입니다.</li><li>각 숫자는 1 이상 50 이하인 자연수입니다.</li><li>타겟 넘버는 1 이상 1000 이하인 자연수입니다.</li></ul><h5>입출력 예</h5>numbers target return[1, 1, 1, 1, 1] 3 5[4, 1, 2, 1] 4 2<h5>입출력 예 설명</h5>입출력 예 #1문제 예시와 같습니다.입출력 예 #2<pre spellcheck="false"><code>+4+1-2+1 = 4
+4-1+2-1 = 4</code></pre><ul class="tight" data-tight="true"><li>총 2가지 방법이 있으므로, 2를 return 합니다.</li></ul><h3>문제 풀이 접근</h3>결과적으로 오늘 혼자 풀었느냐 하면 아니다.문제를 보자마자, 핵심 키워드를 확인을 해보니 DFS/BFS 였다. 문제에서 나타난 핵심은 1. 순서는 그대로다. 2. 타겟 넘버에 맞다면, 여기서 카운트 하나 올리고, 총 카운트를 리턴한다. 이 문제를 풀면서 어느정도 트리를 생각하여 계속 트리를 그리고 왜 스왑이 없지? 경로들은 어떻게 담지? 하면서 문제에서도 요구하지 않은 사양에 빠져있었다.그리하여 문제 푸는시간이 약 1시간 40분 정도 걸렸고, 같은 반에 있으신 분께 도움을 받았다. 도움 받고 다시 문제 푸는 방식을 정립하고 아래와 같이 나왔다.<ol class="tight" data-tight="true"><li>경로를 담을 필요는 없다.</li><li>스왑도 생각하지마라. 왜 생각하는겨</li><li>+ - 경우를 더하면서 재귀돌리면 된다.</li></ol><h3>정답 작성 코드 ( C# )</h3><pre spellcheck="false"><code>using System;
using System.Collections.Generic;
public class Solution
{
public int solution(int[] numbers, int target)
{
int answer = 0;
calc(numbers, 0, 0, target, ref answer);
return answer;
}
public static void calc(int[] arr, int sum, int depth, int target, ref int answer)
{
if((arr.Length == depth) &amp;&amp; (sum == target))
{
++answer;
return;
} // 뎁스가 마지막에 도달했으며, 여기서 타겟넘버와 값이 같을때, ++ 한다 if (arr.Length &amp;lt;= depth)
 return; // 뎁스가 길이를 넘어갔을때, 종료한다.

 calc(arr, sum + arr[depth], depth + 1, target, ref answer); 
 // + 의 경우
 calc(arr, sum + (arr[depth] * -1), depth + 1, target, ref answer);
}}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1717077690298" alt="until-369">

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

[코딩테스트 일지 - 99클럽] 5일차 - 타겟 넘버

<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://leetcode.com/explore/">LeetCode</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/problems/valid-parentheses/">Valid Parentheses</a></li><li>사용언어 : C#</li><li>난이도 : 하</li><li>풀이시간 : 33m</li><li>유형 : 스택, 문자열 </li></ul>Given a string&nbsp;<code spellcheck="false">s</code>&nbsp;containing just the characters&nbsp;<code spellcheck="false">'('</code>,&nbsp;<code spellcheck="false">')'</code>,&nbsp;<code spellcheck="false">'{'</code>,&nbsp;<code spellcheck="false">'}'</code>,&nbsp;<code spellcheck="false">'['</code>&nbsp;and&nbsp;<code spellcheck="false">']'</code>, determine if the input string is valid.An input string is valid if:<ol><li>Open brackets must be closed by the same type of brackets.</li><li>Open brackets must be closed in the correct order.</li><li>Every close bracket has a corresponding open bracket of the same type.</li><li></li></ol>Example 1:<pre spellcheck="false"><code>Input: s = "()"
Output: true
</code></pre>Example 2:<pre spellcheck="false"><code>Input: s = "()[]{}"
Output: true
</code></pre>Example 3:<pre spellcheck="false"><code>Input: s = "(]"
Output: false
</code></pre>&nbsp;Constraints:<ul><li><code spellcheck="false">1 &lt;= s.length &lt;= 104</code></li><li><code spellcheck="false">s</code>&nbsp;consists of parentheses only&nbsp;<code spellcheck="false">'()[]{}'</code>.</li></ul><h3>문제 풀이 접근</h3>이 문제는, 여러 케이스를 생각해서 이렇게 풀었는데, 케이스 바로나왔으면 10분만에 풀었을 것 같다. 헷갈렸던 점은, 1. '(' 가 나오면 무조건 뒤에 ')' 나오도록 하는가? 2. 속괄호가 없을까? [()] 이런거.. 1,2번이 모두 참이고 맞다면 문제는 10분도 필요없다 5분컷인데, s[index] ,s[index+1] 해서 비교하면 되는거라.. 해보니까 속괄호도 있고, 처음에 닫힌 브라킷으로 주는 경우도 있고해서 여러 예외가 필요했다.문제 해결 플로우는, 1. 여는 브라킷 ' ( ' , ' [ ' , ' { ' 등이 나오면 Stack에 Push한다. 2. 이후 닫는 브라킷 ' ) ' , ' ] ' , ' } ' 이 나오면 Peek 으로 체크하고 Pop 한다. 3. 이 모든 과정을 수행해서 짝이 맞는다면 Stack 은 비어있는게 정상. 남아있다면 어딘가 닫히는게 없거나, 열리는게 없는데 닫히는 문자를 가져오거나 둘중하나. 고로 false 다.<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/1722400493650" alt="until-1157"><h3>1,2 번 가설 테스트 코드 (C#) - 실패</h3><pre spellcheck="false"><code>public class Solution {
 public bool IsValid(string s) {

 for(int i = 0; i &lt; s.Length-1; ++i)
 {
 var elem = s[i];
 var elemNext = s[i+1];
 
 if((elem == '(') &amp;&amp; (elemNext == ')') == false)
 return false;
 
 if((elem == '[') &amp;&amp; (elemNext == ']') == false)
 return false;
 
 if((elem == '{') &amp;&amp; (elemNext == '}') == false)
 return false;
 }
 
 return true;
 }
}</code></pre><img src="https://image.until.blog/sin0105/article/1722400531315" alt="until-1158">

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

코딩테스트 준비 - Valid Parentheses

[자료구조와실습]

<h2>1. 그래프 Graph</h2><blockquote>연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조</blockquote>객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)의 집합이다.<img src="https://image.until.blog/white/article/1727168137992.png" alt="until-1471"><h2>2. 그래프 용어 정리</h2>그래프에서 두 정점 V1과 V2를 연결하는 간선 (V1, V2)가 있을 때, 두 정점 V1과 V2를 인접(adjacent)되어 있다고 하고, 간선 (V1, V2)는 정점 V1과 V2에 부속(incident)되어 있다고 한다.<ul><li>이때 인접(adjacent)은 정점과 정점의 관계이다. </li></ul><img src="https://image.until.blog/white/article/1727168915549.png" alt="until-1473"><ul><li>다음과 같은 그래프에서 정점 1과 인접한 정점은 4와 3이고, 정점 1에 부속되어 있는 간선은 (1, 4)와 (1, 3)이다.</li></ul><hr>[용어 설명용 그림]<img src="https://image.until.blog/white/article/1727169964100.png" alt="until-1476"><h3>2.1. 차수 degree</h3><blockquote>정점에 부속되어 있는 간선의 수, 즉 한 정점에 인접한 정점의 개수이다.</blockquote><ul><li>무방향 그래프<ul><li>무방향 그래프에서 정점 1의 차수는 2, 정점 3의 차수는 3이다.</li></ul></li><li>방향 그래프<ul><li><code spellcheck="false">방향 그래프의 정점의 차수 = 진입차수 + 진출 차수</code><ul><li>진입차수(in-degree) : 정점을 머리로 하는 간선의 수</li><li>진출 차수(out-degree) : 정점을 꼬리로 하는 간선의 수</li></ul></li><li>방향 그래프에서 정점 4의 진입차수는 1, 진출차수는 2이다. 따라서 정점 4의 전체 차수는 (진출차수+진입차수) 이므로 3이다.</li></ul></li></ul><h3>2.2. 경로 path</h3><blockquote>그래프에서 간선을 따라 갈 수 있는 길을 순서대로 나열한 것, 즉 정점 V1에서 V2까지 간선으로 연결된 정점을 순서대로 나열한 리스트</blockquote><ul><li>무방향 그래프에서 정점 1에서 정점 2까지는 1-3-2 경로와 1-3-4-2 경로, 1-4-2 경로, 1-4-3-2 경로가 있다.</li></ul><h3>2.3. 경로 길이 path length</h3><blockquote>경로를 구성하는 간선의 수</blockquote><h3>2.4. 단순 경로 simple path</h3><blockquote>모두 다른 정점으로 구성된 경로</blockquote><ul><li>무방향 그래프에서 정점 1부터 정점 2까지의 경로 1-4-2는 단순경로이고, 경로 1-4-3-1-4-2는 단순경로가 아니다.</li></ul><h3>2.5. 사이클 cycle</h3><blockquote>단순경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로</blockquote><ul><li>무방향 그래프에서 단순경로 1-3-2-4-1과 방향 그래프에서 단순경로 1-3-1은 사이클이 된다.</li></ul><h3>2.6. DAG Directed Acyclic Graph</h3><blockquote>방향 그래프이면서 사이클이 없는 그래프</blockquote><h3>2.7. 연결 그래프 connected graph</h3><blockquote>서로 다른 모든 쌍의 정점들 사이에 경로가 있는 그래프, 즉 떨어져있는 정점이 없는 그래프</blockquote>그래프에서 두 정점 V1과 V2까지의 경로가 있으면 정점 V1과 V2가 연결(connected)되었다고 한다. 따라서 트리는 사이클이 없는 연결 그래프라고 할 수 있다.<h3>2.8. 단절 그래프 disconnected graph</h3><blockquote>연결되지 않은 정점이 있는 그래프</blockquote>[연결 그래프와 단절 그래프]<img src="https://image.until.blog/white/article/1727172439548.png" alt="until-1477"><h2>3. 그래프의 종류</h2><h3>3.1. 무방향 그래프 undirected graph</h3><blockquote>두 정점을 연결하는 간선에 방향이 없는 그래프</blockquote>정점 V1과 정점 V2를 연결하는 간선을 (V1, V2)로 표현한다. (V1, V2)와 (V2, V1)은 같은 간선을 의미한다. (순서가 없음)<img src="https://image.until.blog/white/article/1727176582469.png" alt="until-1479"><h3>3.2. 방향 그래프 directed graph, 다이그래프 digraph</h3><blockquote>간선에 방향이 있는 그래프</blockquote>정점 V1에서 정점 V2를 연결하는 간선 즉, V1 -&gt; V2를 &lt;V1, V2&gt;로 표현한다. 이때, V1를 꼬리(tail), V2를 머리(head)라고 한다. &lt;V1, V2&gt;, &lt;V2, V1&gt;은 서로 다른 간선을 의미하므로 표시에 유의해야한다.<img src="https://image.until.blog/white/article/1727176601391.png" alt="until-1480"><h3>3.3. 완전 그래프 complete graph</h3><blockquote>각 정점에서 다른 모든 정점을 연결하여 최대로 많은 간선 수를 가진 그래프</blockquote>정점이 n개인 무방향 그래프에서의 최대 간선 수는 <code spellcheck="false">n(n-1)/2</code>개이고, 정점이 n개인 방향 그래프는 두 정점에 대해서 방향이 다른 두 개의 간선을 연결할 수 있으므로 최대 간선 수는 <code spellcheck="false">n(n-1)</code>개이다.<h3>3.4. 부분 그래프 subgraph</h3><blockquote>원래의 그래프에서 정점이나 간선을 일부만 제외하여 만든 그래프</blockquote>이때, G2는 G1의 부분그래프이다.V(G') ⊆ V(G), E(G') ⊆ E(G)<img src="https://image.until.blog/white/article/1727177438157.png" alt="until-1481"><h3>3.5. 가중 그래프 weight graph, 네트워크 network</h3><blockquote>정점을 연결하는 간선에 가중치(weight)를 할당한 그래프</blockquote><img src="https://image.until.blog/white/article/1727177628840.png" alt="until-1482">

#1. 그래프

<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

다시푸는 코딩 테스트 준비 일지

문제 풀이 접근

정답 작성 코드 (C#)

코드 결과