<div id="readability-page-1" class="page"><div><a href="https://leetcode.com/problems/arranging-coins/">Arranging Coins</a>
<img src="https://velog.velcdn.com/images/dongha1992/post/99a0e3a2-00ea-4031-b8d7-118430174ebc/image.png">
<h2 id="풀이">풀이</h2>
<ul>
<li>n에서 차감하면서 만들 수 최대 row를 만든다.</li>
<li>이진탐색의 경우, mid 값을 뽑아 mid까지 모든 수를 더해 n과 비교한다. n보다 작을 경우, 해당 row는 모두 채울 수 있으므로 low를 올린다. 모두 더한 값이 n일 경우 mid까지 채울 수 있으니 mid를 반환, </li>
</ul>
<h2 id="코드---순회">코드 - 순회</h2>
<pre><code>class Solution {
 public int arrangeCoins(int n) {
 int c = 0;
 int row = 0;
 
 while(c &lt;= n){
 c++;
 n -= c;
 row++;
 }
 return row;
 }
}
</code></pre>
<h2 id="코드---이진탐색">코드 - 이진탐색</h2>
<pre><code>class Solution {
 public int arrangeCoins(int n) {
 long low = 1;
 long high = n; 
 
 while(low &lt;= high) {
 long mid = ((low + high) / 2);
 long sum = mid * (mid+1) / 2;
 
 if(sum == n) {
 return (int) mid;
 } else if(sum &lt; n) {
 low = mid +1; 
 } else {
 high = mid -1;
 }
 }
 
 return (int) high;
 }
}
</code></pre>
<h2 id="정리">정리</h2>
<ul>
<li><del>이진탐색 문제인데 도저히 이진탐색으로는 생각이 나지 않아 선형순회로 풀었음..</del></li>
</ul></div></div>

삶도 재입학이 되나요?

Arranging Coins
풀이
n에서 차감하면서 만들 수 최대 row를 만든다.
이진탐색의 경우, mid 값을 뽑아 mid까지 모든 수를 더해 n과 비교한다. n보다 작을 경우, 해당 row는 모두 채울 수 있으므로 low를 올린다. 모두 더한 값이 n일 경우 mid까지 채울 수 있으니 mid를 반환, 
코드 - 순회
class Solution {
 public int arrangeCoins(int n) {
 int c = 0;
 int row = 0;
 while(c <= n){
 c++;
 n -= c;
 row++;
 }
 return row;
 }
}
코드 - 이진탐색
class Solution {
 public int arrangeCoins(int n) {
 long low = 1;
 long high = n; 
 while(low <= high) {
 long mid = ((low + high) / 2);
 long sum = mid * (mid+1) / 2;
 if(sum == n) {
 return (int) mid;
 } else if(sum < n) {
 low = mid +1; 
 } else {
 high = mid -1;
 }
 }
 return (int) high;
 }
}
정리
이진탐색 문제인데 도저히 이진탐색으로는 생각이 나지 않아 선형순회로 풀었음..

99클럽 코테 스터디 29일차 - 이진탐색

댓글