CodingTest

<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/16953">1389.A→B</a></li><li>사용언어 : C#</li><li>난이도 : 중</li><li>풀이시간 : 01h 08m</li><li>유형 : BFS, DFS, 그래프 이론, 그리디</li></ul><h2>문제</h2>정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.<ul><li>2를 곱한다.</li><li>1을 수의 가장 오른쪽에 추가한다.&nbsp;</li></ul>A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.<h2>입력</h2>첫째 줄에 A, B (1 ≤ A &lt; B ≤ 109)가 주어진다.<h2>출력</h2>A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.<h2>예제 입력 1 복사</h2><pre spellcheck="false"><code>2 162
</code></pre><h2>예제 출력 1 복사</h2><pre spellcheck="false"><code>5
</code></pre>2&nbsp;→ 4&nbsp;→ 8&nbsp;→ 81&nbsp;→ 162<h2>예제 입력 2 복사</h2><pre spellcheck="false"><code>4 42
</code></pre><h2>예제 출력 2 복사</h2><pre spellcheck="false"><code>-1
</code></pre><h2>예제 입력 3 복사</h2><pre spellcheck="false"><code>100 40021
</code></pre><h2>예제 출력 3 복사</h2><pre spellcheck="false"><code>5
</code></pre>100&nbsp;→ 200&nbsp;→ 2001&nbsp;→ 4002&nbsp;→ 40021<h2>문제 풀이 접근</h2>이 문제는, 일반적인 BFS 를 maps 형식으로 구성할 수 있게 주는 문제가 아니었다. 원리는 같은데 발상이 다른 느낌이어서 조금 고민해보고 어떻게 풀지 가닥을 잡았다.다른 BFS,DFS 문제는 맵을주로 상하좌우를 탐색하지만 원리는 같고, 오히려 이게 더 이쪽 원리에서 더 기초적인 방법이지 않을까? 라는게 내 생각이다. masp[,] 와 같은 2차원 배열이 아닌 행동으로 나타내기 때문이다.BFS의 원리인 Queue들 돌면서 약간의 그리디 알고리즘 키워드가 들어가 있는것을 알았는데, 내가 만든 숫자와 타겟 숫자가 같다고 판단되면 다른 경로는 모두 신경쓰지 않고, 바로 종료하도록 하며, 타겟 숫자보다 넘어갈 경우 enqueue 를 하지 않도록 하였다.그리고 이 문제의 유의점 3가지가 있다. 둘다 내가 잘못읽은 것이지만, 이것 때문에 시간을 오래썼으므로 남긴다. 첫번째는, 2번 액션에서 우측에 '1' 을 추가한다 라는 지문인데, 예를들면 20 일때 21 이 아닌 201 이 되는 것이다. 두번째는, target의 수 범위다. 10의 9승이면 10억이다. 여기서 정수의 표현범위를 알면 내가 말하고자 하는 의미를 알 수 있을 것이라고 생각한다.마지막으로, 가장 나를 괴롭혔던 문제인데, 10의 9승 즉 10억이기 때문에 1바이트라도 배열을 세워서 거기에 값 남기고 이렇게하면 메모리초과에서 절대로 헤어나올 수 없다. 이 세가지만 유의하면 금방 풀럴 것이다<h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code>using System;
using System.CodeDom;
using System.Collections.Generic;
using System.ComponentModel;
using System.ComponentModel.Design;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Security.AccessControl;
using System.Security.Authentication;
using System.Security.Cryptography;
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;

/*
 * Difficulty : Middle
 * URL : https://www.acmicpc.net/problem/16953
 */


namespace CodingTestProj
{
 internal class Program
 {


 static void Main(string[] args)
 {
 //Case 0 _ Short
 Solution solution = new Solution();
 solution.solve();
 }
 }
 public class Solution
 {
 public int start;
 public double target;

 public double ret;
 public Dictionary&lt;double, double&gt; dic;

 public void solve()
 {
 dic = new Dictionary&lt;double, double&gt;();

 string[] input = Console.ReadLine().Split(' ');

 start = Convert.ToInt32(input[0].ToString());
 target = Convert.ToInt64(input[1].ToString());

 BFS();
 Print();
 }

 public void BFS()
 {
 Queue&lt;double&gt; q = new Queue&lt;double&gt;();
 q.Enqueue(start);

 if (dic.ContainsKey(start) == false)
 dic.Add(start, 1);

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

 if (cur == target)
 break;

 if (cur &gt; target)
 continue;

 var calc1 = (double)cur * (double)2;
 var calc2 = double.Parse(cur.ToString() + "1");

 if (calc1 &lt;= target)
 {
 q.Enqueue(calc1);

 if (dic.ContainsKey(calc1) == false)
 {
 var values = dic[cur] + 1;
 dic.Add(calc1, values);
 }
 }

 if (calc1 == target)
 break;

 if (calc2 &lt;= target)
 {
 q.Enqueue(calc2);

 if (dic.ContainsKey(calc2) == false)
 {
 var values = dic[cur] + 1;
 dic.Add(calc2, values);
 }
 }

 if (calc2 == target)
 break;
 }
 }

 public void Print()
 {
 ret = dic.ContainsKey(target) == false ? (double)(-1) : dic[target];
 Console.WriteLine(ret);
 }
 }
}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1727792085824.png" data-width="100%" data-align="center"> 이 문제를 풂으로써, 등급이 S4가 되었다.

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

코딩테스트 준비 - A→B

🧑‍💻 Develop

<img src="https://image.until.blog/morethanmin/article/1718723304750" alt="until-541">개발자에게 생산성은 곧 비용이기에 생산성을 높이는 것은 매우 중요한 일인데요.멀티커서 기능을 잘 활용하면 생산성을 높일 수 있습니다. 저 또한 잘 활용하고 있지만 매번 활용하고 있는 기능들만 사용하게 되는 것 같아 이번 기회에 어떤 기능들이 있는지 정리해보려고 합니다.기본적으로 마우스를 활용한 방식과 키보드를 활용한 방식이 있어요.<h1>마우스를 활용한 멀티 커서 단축키</h1><h2>클릭하여 하나씩 추가</h2>우선 가장 기초적인 방법부터 알려드릴게요.맥에서는 <code spellcheck="false">Option</code> 키, 윈도우에서는 <code spellcheck="false">Alt</code> 키를 누른 상태로 vscode 화면에서 다른 영역을 마우스 포인터로 클릭하여 여러 커서를 추가할 수 있습니다.이 상태에서 키보드로 타이핑을 하시면 모든 커서에서 동일하게 타이핑이 됩니다.제거하기 위해서는 커서에 <code spellcheck="false">Option</code> 또는 <code spellcheck="false">Alt</code> 키를 누르신 체로 다시 클릭해주시면 됩니다.<code spellcheck="false">esc</code> 를 눌러서도 멀티커서를 제거할 수 있어요.<h2>그래그하여 추가</h2>클릭이 아닌 드래그해서 추가하는 방법도 있어요.맥에서는 <code spellcheck="false">Option+Shift</code> 키, 윈도우에서는 <code spellcheck="false">Alt+Shift</code> 키를 누른 상태로 vscode 화면에서 다른 영역을 마우스 포인터를 드래그하여 여러 커서를 추가할 수 있습니다.<h1>키보드를 활용한 멀티 커서 단축키</h1><h2>일치하는 텍스트 모두 선택</h2>선택하고자 하는 내용을 드래그한다음, 맥에서는 <code spellcheck="false">Command+Shift+L</code> 키, 윈도우에서는 <code spellcheck="false">Ctrl+Shift+L</code> 키를 누르면 동일한 텍스트들에 모두 커서가 추가됩니다.<h2>순차적으로 일치하는 텍스트 선택</h2>위 기능의 경우 모든 텍스트가 선택된다면 해당 단축키를 사용하면 순차적으로 원하는 텍스트에 하나씩 커서가 추가됩니다.선택하고자 하는 내용을 드래그한다음, 맥에서는 <code spellcheck="false">Command+D</code> 키, 윈도우에서는 <code spellcheck="false">Ctrl+D</code> 키를 누르면 드래그한 텍스트와 일치하는 다음 텍스트에 커서가 생기고 또 누르면 그 다음 텍스트에 커서가 추가되어요.만약에 다시 되돌리기 위해서는 맥에서는 <code spellcheck="false">Command+U</code> 키, 윈도우에서는 <code spellcheck="false">Ctrl+U</code> 키를 눌러서 마지막으로 선택된 곳을 취소할 수 있어요.<h2>현재 커서 위 또는 아래 줄에 추가</h2>현재 커서 위치에서 위 또는 아래 방향으로도 멀터 커서를 연속으로 추가할 수 있어요. 맥에서는 <code spellcheck="false">Command+Option+Up/Down</code>, 윈도우즈에서는 <code spellcheck="false">Ctrl+Alt+Up/Down</code>키를 누르시면 됩니다.<h2>그래그한 여러 줄의 맨 마지막에 멀터 커서 추가하기</h2>여러줄을 드래그한 상태에서 각 줄의 마지막 라인에 커서를 추가할 수 있어요.맥에서는 <code spellcheck="false">Option+Shift+I</code>, 윈도우에서는 <code spellcheck="false">Alt+Shift+I</code>를 키를 눌러 적용할 수 있어요.

개발자에게 생산성은 곧 비용이기에 생산성을 높이는 것은 매우 중요한 일인데요.멀티커서 기능을 잘 활용하면 생산성을 높일 수 있습니다. 저 또한 잘 활용하고 있지만 매번 활용하고 있는 기능들만 사용하게 되는 것 같아 이번 기회에 어떤 기능들이 있는지 정리해보려고 합니다.기본적으로 마우스를 활용한 방식과 키보드를 활용한 방식이 있어요.마우스를 활용한 멀티 커서

VSCode 멀티 커서로 생산성 높이기

Lyrics

<a target="_blank" rel="noopener noreferrer nofollow" href="https://youtu.be/-_uy5vWbeQg">https://youtu.be/-_uy5vWbeQg</a> I saw I missed your call 당신의 부재중 전화를 봤어요 Sorry for not picking up 받지 못해 미안해요 I got the job at the flower shop 난 요즘 꽃집에서 일해요 I sweep the floors but I'm talking to you 바닥을 쓸면서도 당신과 대화하고 있어요 I see your eyes in the delphinium too 델피니움에서도 당신의 눈을 봐요 I've become a servant to their blue 그들의 푸른색(델피니엄 블루)에 빠져버렸죠 (그들의 푸른색의 종이 되어버렸어요) Chin up 고개를 들고 Stay on task 일에 집중해요 Wash the windows 창문을 닦고 Count the cash 돈을 세어요 I picked up another couple of shifts 몇 번의 추가 근무를 맡았어요I hear your voice when I'm closing 가게 문을 닫을 때 당신의 목소리가 들려요 The nights fall like thorns off the roses 밤이 장미의 가시처럼 떨어져요 All around me the narcissus bloom 주변에 수선화가 피어나요 I picture the sun hitting you 태양이 당신을 비추는 모습을 상상해요 The air is filled with their perfume 공기는 그들의 향기로 가득하죠 Chin up 고개를 들고 Stay on task 일에 집중해요 Wash the windows 창문을 닦고 Count the cash 돈을 세어요 Cut the stems 줄기를 잘라 To make them last 오래 가게 해요&nbsp; Keep it cool 시원하게 유지시켜요 Bеhind the glass 유리 뒤에서 With their perfumе 그들의 향기와 함께 * Toolog 번역 시리즈는 Deepl, 파파고, Gemini, Mistral, Claude, Chatgpt, Perplexity, Pi, Hugging Chat, Hinative, Khoj 등의 번역기 및 플랫폼의 도움을 받습니다.(번역 자체가 부정확할 수 있습니다.)

https://youtu.be/-_uy5vWbeQgI saw I missed your call당신의 부재중 전화를 봤어요Sorry for not picking up받지 못해 미안해요I got the job at the flower shop난 요즘 꽃집에서 일해요I sweep the floors but I'm talking to you바닥을 쓸면서도 당신과 

Cassandra jenkins - Delphnium Blue(가사 번역)

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

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

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

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

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

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

<a target="_blank" rel="noopener noreferrer nofollow" href="https://youtu.be/tCp0vukTNMo">https://youtu.be/tCp0vukTNMo</a> Sweet baby 사랑스러운 아가야 Like you, I emerged 나도 너처럼 어떤 불확실한 From a certain uncertain chaos 혼돈으로부터 태어났지 They say those who are quickest, survive 사람들은 말해, 가장 빠른 자가 살아남고 And those who are strongest, thrive 가장 강한 자가 번성한다고 But I never want to get all the things that I want 하지만 난 원하는 모든 걸 얻고 싶진 않아 How awful would that be for me? 그건 내게 얼마나 끔찍할까? I’m happier here, slow 나는 여기서 행복해, 느리게 And indulgent in the sun 태양아래 느긋하게 I’m happier here, weak 나는 여기서 행복해, 약하게 Let the night come when it comes 밤이 오면 그냥 오게 둬 Sweet baby 사랑스러운 아가야 Never thought I’d be the one 내 스스로 내 패배를 To accept my own defеat 받아들일 줄 몰랐어 I know if I’d been quicker, I’d have survived 알아, 내가 더 빨랐다면 살아남았고 And if I’d been strongеr, I’d have thrived 더 강했다면 번성했겠지 But I never want to get all the things that I want 하지만 난 원하는 모든 걸 얻고 싶진 않아 How awful would that be for me? 그건 내게 얼마나 끔찍할까? I’m happier here, slow 나는 여기서 행복해, 느리게 And indulgent in the sun 태양아래 느긋하게 I’m happier here, weak 나는 여기서 행복해, 약하게 Let the night come when it comes 밤이 오면 그냥 오게 둬<hr> * Toolog 번역 시리즈는 Deepl, 파파고, Gemini, Mistral, Claude, Chatgpt, Perplexity, Pi, Hugging Chat, Hinative, Khoj 등의 번역기 및 플랫폼의 도움을 받습니다.(번역 자체가 부정확할 수 있습니다.)

https://youtu.be/tCp0vukTNMoSweet baby사랑스러운 아가야Like you, I emerged나도 너처럼 어떤 불확실한From a certain uncertain chaos혼돈으로부터 태어났지They say those who are quickest, survive사람들은 말해, 가장 빠른 자가 살아남고And those who are

Lightning Bug - On Paradise(가사 번역)

코딩테스트

<h3>문제 설명</h3>당신은 순서대로 <code spellcheck="false">n</code>개의 퍼즐을 제한 시간 내에 풀어야 하는 퍼즐 게임을 하고 있습니다. 각 퍼즐은 난이도와 소요 시간이 정해져 있습니다. 당신의 숙련도에 따라 퍼즐을 풀 때 틀리는 횟수가 바뀌게 됩니다. 현재 퍼즐의 난이도를 <code spellcheck="false">diff</code>, 현재 퍼즐의 소요 시간을 <code spellcheck="false">time_cur</code>, 이전 퍼즐의 소요 시간을 <code spellcheck="false">time_prev</code>, 당신의 숙련도를 <code spellcheck="false">level</code>이라 하면, 게임은 다음과 같이 진행됩니다.<ul><li><code spellcheck="false">diff</code> ≤ <code spellcheck="false">level</code>이면 퍼즐을 틀리지 않고 <code spellcheck="false">time_cur</code>만큼의 시간을 사용하여 해결합니다.</li><li><code spellcheck="false">diff</code> &gt; <code spellcheck="false">level</code>이면, 퍼즐을 총 <code spellcheck="false">diff</code> - <code spellcheck="false">level</code>번 틀립니다. 퍼즐을 틀릴 때마다, <code spellcheck="false">time_cur</code>만큼의 시간을 사용하며, 추가로 <code spellcheck="false">time_prev</code>만큼의 시간을 사용해 이전 퍼즐을 다시 풀고 와야 합니다. 이전 퍼즐을 다시 풀 때는 이전 퍼즐의 난이도에 상관없이 틀리지 않습니다. <code spellcheck="false">diff</code> - <code spellcheck="false">level</code>번 틀린 이후에 다시 퍼즐을 풀면 <code spellcheck="false">time_cur</code>만큼의 시간을 사용하여 퍼즐을 해결합니다.</li></ul>예를 들어 <code spellcheck="false">diff</code> = 3, <code spellcheck="false">time_cur</code> = 2, <code spellcheck="false">time_prev</code> = 4인 경우, <code spellcheck="false">level</code>에 따라 퍼즐을 푸는데 걸리는 시간은 다음과 같습니다.<ul><li><code spellcheck="false">level</code> = 1이면, 퍼즐을 3 - 1 = 2번 틀립니다. 한 번 틀릴 때마다 2 + 4 = 6의 시간을 사용하고, 다시 퍼즐을 푸는 데 2의 시간을 사용하므로 총 6 × 2 + 2 = 14의 시간을 사용하게 됩니다.</li><li><code spellcheck="false">level</code> = 2이면, 퍼즐을 3 - 2 = 1번 틀리므로, 6 + 2 = 8의 시간을 사용하게 됩니다.</li><li><code spellcheck="false">level</code> ≥ 3이면 퍼즐을 틀리지 않으며, 2의 시간을 사용하게 됩니다.</li></ul>퍼즐 게임에는 전체 제한 시간 <code spellcheck="false">limit</code>가 정해져 있습니다. 제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 구하려고 합니다. 난이도, 소요 시간은 모두 양의 정수며, 숙련도도 양의 정수여야 합니다.퍼즐의 난이도를 순서대로 담은 1차원 정수 배열 <code spellcheck="false">diffs</code>, 퍼즐의 소요 시간을 순서대로 담은 1차원 정수 배열 <code spellcheck="false">times</code>, 전체 제한 시간 <code spellcheck="false">limit</code>이 매개변수로 주어집니다. 제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 정수로 return 하도록 solution 함수를 완성해 주세요.<h3>제한사항</h3><ul><li>1 ≤ <code spellcheck="false">diffs</code>의 길이 = <code spellcheck="false">times</code>의 길이 = <code spellcheck="false">n</code> ≤ 300,000<ul><li><code spellcheck="false">diffs[i]</code>는 <code spellcheck="false">i</code>번째 퍼즐의 난이도, <code spellcheck="false">times[i]</code>는 <code spellcheck="false">i</code>번째 퍼즐의 소요 시간입니다.</li><li><code spellcheck="false">diffs[0]</code> = 1</li><li>1 ≤ <code spellcheck="false">diffs[i]</code> ≤ 100,000</li><li>1 ≤ <code spellcheck="false">times[i]</code> ≤ 10,000</li></ul></li><li>1 ≤ <code spellcheck="false">limit</code> ≤ 1015<ul><li>제한 시간 내에 퍼즐을 모두 해결할 수 있는 경우만 입력으로 주어집니다.</li></ul></li></ul><h3>입출력 예시</h3><img src="https://image.until.blog/jisoo/article/1727223139135.png" alt="until-1507"><h3>접근</h3><ol><li>puzzle에 대한 조건식을 구성</li><li>숙련도를 찾아야하는데, 전부 계산하기에는 시간초과 =&gt; 이진 탐색 필요!</li></ol><h3>구현 Code</h3><pre spellcheck="false"><code class="language-python">def puzzle(diff, cur, prev, level):
 if diff &lt;= level:
 return cur
 else:
 return (diff - level) * (cur + prev) + cur


def solution(diffs, times, limit):
 max_level, min_level = max(diffs), 1

 while max_level &gt; min_level:
 mid_level = (min_level + max_level) // 2
 total = puzzle(diffs[0], times[0], 0, mid_level)

 for t in range(1, len(diffs)):
 prev = times[t - 1]
 cur = times[t]
 total += puzzle(diffs[t], cur, prev, mid_level)
 if total &lt;= limit:
 max_level = mid_level
 else:
 min_level = mid_level + 1

 return min_level</code></pre><h3>함수 설명</h3>puzzle<ul><li>현재 퍼즐 난이도가 숙련도보다 쉽다면 =&gt; 현재값</li><li>현재 퍼즐 난이도가 숙련도보다 어렵다면<ul><li>(이전 문제 푸는 시간 + 현재 문제 푸는 시간)을 (난이도 - 숙련도) 즉, 틀릴 때마다 반복해주고 현재 문제 푸는 시간만큼 더해줘야한다.</li></ul></li></ul>숙련도 찾는 방법전부 탐색하기에는 불가능하기 때문에, 중간부터 찾아준다.level에 따라 계산한 값을 total에 더해줄건데, 만약에 limit보다 크다면 level을 낮춰준다.반대로 작다면 최소값을 찾아야하기 때문에 숙련도를 높여준다.

문제 설명당신은 순서대로 n개의 퍼즐을 제한 시간 내에 풀어야 하는 퍼즐 게임을 하고 있습니다. 각 퍼즐은 난이도와 소요 시간이 정해져 있습니다. 당신의 숙련도에 따라 퍼즐을 풀 때 틀리는 횟수가 바뀌게 됩니다. 현재 퍼즐의 난이도를 diff, 현재 퍼즐의 소요 시간을 time_cur, 이전 퍼즐의 소요 시간을 time_prev, 당신의 숙련도를 level

[프로그래머스 - lv2] [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 (Python)

Notice

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

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