땅다람쥐의 나날

문제 레모네이드의 가격은 $5입니다. 손님들은 $5, $10, $20을 낼 수가 있는데, $5보다 큰 금액을 내면은 정확한 거스름돈을 줘야합니다. 여기서 명심해야 할 것은 처음에 가지고 있는 거스름돈은 없습니다. Integer array로 bills을 받게 되는데 bills[i]는 ith 번째 손님이 지불하는 bill을 말합니다. 만약에 고객들한테 정확하게 거스름돈을 줄 수 있으면 true를 반환하고 아니면 false를 반환해야합니다. 조건을 보자면 아래와 같이 정리할 수 있는데요. 초기에 가지고 있는 거스름돈 없음 고객이 낼 수 있는 돈의 종류는 3가지 정확하게 거스름돈을 줄 수 있는지 아닌지 풀이 푸는 방법은 여러가지 일 수 가 있겠는데요. 처음에 생각나는건 HashMap 이였습니다. key 값에 5..

문제 n개의 주유소가 순환 루트에 있다. 주어진 Gas와 Cost를 사용해서 한 바퀴를 돌 수 있는 인덱스를 찾기 만약에 없다면 -1 리턴하기. 해결방법 계속 여행을 할 수 있는 조건은 gas[i] - cost[i+1]가 0보다 클 때 그래서 모든 gas[i] - cost[i+1]를 더한 값이 0 보다 작으면 -1 그렇지 않을 경우에는 한 바퀴를 돌 수 있다. 그리고 gas[i] - cost[i+1]의 값과 잔여 연료의 값을 더 했을 때 0 보다 큰 값이 나오면 거기서부터 한 바퀴를 돌 수 있다. int fuel = 0; int size = gas.length; for (int i = 0; i < size; i++){ fuel += gas[i] - cost[i]; } if (fuel < 0) { retu..

문제 회전된 배열에서 target 넘버 찾기 넘버가 없으면 -1의 값을 리턴 런타임이 O (log n)이 되야함 해결방법 Modified Binary Search class Solution { public int search(int[] nums, int target) { int left = 0; int right = nums.length - 1; while (left

문제 화단에서 꽃 몇 송이를 심을 수 있는가? 화단에 심은 꽃이 n보다 같거나 작은가? 해결방법 세가지 인덱스의 값을 비교하면서 n을 줄여나가기 n이 만약 0 보다 크다면 false 작으면 true. public class Solution { public boolean canPlaceFlowers(int[] flowerbed, int n) { for(int i = 0; i = flowerbed.length ? 0 : flowerbed[i+1]; int curr = flowerbed[i]; if(pre == 0 && post == 0 && curr == 0) ..

Two Sum과 Binary Search의 개념을 이용해서 풀 수 있는 간단한 문제 문제 - 정렬된 배열에서 target이 되는 값을 찾아 index + 1 되는 배열을 return하기 해결방법 - 배열이 이미 정렬되어 있어서 Binary Search를 사용 class Solution { public int[] twoSum(int[] numbers, int target) { int start = 0; int end = numbers.length - 1; int[] output = new int[2]; while (end > start) { int sum = numbers[start] + numbers[end]; if (sum == target){ output[0] = start + 1; output[1]..

문제 - 두 가지 곡 시간의 합이 60으로 나뉘어지는 Pair의 수를 찾아라 해결방법 1. Brute Force를 이용해서 곡 pair의 합이 60으로 나뉘어지는 곡들 찾기 2. 각 곡들의 시간을 60으로 나누었을 때 나머지 값이 같은 곡이 있다면 +1 해주기. class Solution { public int numPairsDivisibleBy60(int[] time) { int output = 0; int size = time.length; for (int i = 0; i < size; i++){ for(int j = i+1; j < size; j++){ int totalTime = time[i] + time[j]; if (totalTime % 60 == 0){ output++; } } } retur..

학기 끝나고 오랜만에 풀어보는 알고리즘 문제다. C++을 사용하다가 Java로 넘어오면서 적응하느라 고생을 좀 했다. 문제 - 숫자와 도메인으로 이루어진 String pair - 앞에 숫자는 도메인을 얼마나 방문했는지 나타내는 것 - 도메인을 "."으로 나누었을 때 각각 총 방문 숫자를 각각 나태는 List를 return 할 것 해결 방법 - Hash Table과 Brute Force를 이용하기 public List subdomainVisits(String[] cpdomains) { int size = cpdomains.length; HashMap map = new HashMap(); List output = new ArrayList(); for (int i = 0; i < size; i++){ //Sp..