1. Lv.2
- 33문제 풀기 :
- 정답률 높은 순서
- 약 3만명 이상 푼 문제부터 풀고 Kakao 문제는 거의 다 풀기
- 문제 당, 최대 2시간 고민
1) 최댓값과 최솟값
- compareTo는 문자열 정렬 시, 사용! **
import java.util.*;
class Solution {
public String solution(String s) {
String[] sp = s.split(" ");
String answer = "";
int[] num = new int[sp.length];
for(int i = 0; i < sp.length; i++){
num[i] = Integer.parseInt(sp[i]);
}
Arrays.sort(num);
for(int i = 0; i < num.length; i++){
answer = num[0] + " " + num[sp.length-1];
}
// ** compareTo는 문자열 정렬시, 사용! **
// Arrays.sort(sp, (o1,o2) -> (o1).compareTo(o2));
// for(int i = 0; i < sp.length; i++){
// answer = sp[0] + " " + sp[sp.length-1];
// }
return answer;
}
}
2) JadenCase 문자열 만들기
- 테케 8번만 실패, 연속된 공백 어떻게 없앨까?
- 다시 풀기!
import java.util.*;
class Solution {
public String solution(String s) {
String[] sp = s.split(" ");
String answer = "";
List<String> ls = new ArrayList<>();
for(int i = 0; i < sp.length; i++){
ls.add(sp[i]);
}
for(int i = 0; i < sp.length; i++){
if(ls.get(i).equals(" "))
ls.remove(i--);
String[] s1 = ls.get(i).split("");
s1[0] = s1[0].toUpperCase();
for(int j = 0; j < s1.length; j++){
if(j != 0)
s1[j] = s1[j].toLowerCase();
answer += s1[j];
}
if(i != sp.length - 1)
answer += " ";
}
return answer;
}
}
3) 올바른 괄호
- 첫 번째 코드 :
- 테스트 전부 통과하지만, 시간 초과
- 수정하기
class Solution {
boolean solution(String s) {
String[] sp = s.split("");
boolean count1 = true;
boolean answer = true;
for(int i = 0; i < sp.length; i++){
if(sp[i].equals("("))
count1 = true;
else if(sp[i].equals(")"))
count1 = false;
}
if(count1 == false)
answer = true;
else
answer = false;
return answer;
}
}
- 두 번째 코드 :
- 반환 타입이 boolean이라서 false로 반환하기!
- return 0보다는 return false를 더 많이 사용할 것!
import java.util.*;
class Solution {
boolean solution(String s) {
// String[] sp = s.split("");
boolean check = true;
boolean answer = true;
int cnt = 0;
for(int i = 0; i < s.length(); i++){
if(s.charAt(i) == '('){
check = true;
cnt++;
}
else if(s.charAt(i) == ')'){
check = false;
cnt--;
}
// 반환 타입이 boolean이라서 false로 반환하기!
if(cnt < 0)
return false;
}
if(cnt != 0)
answer = false;
else
answer = true;
return answer;
}
}
4) 최솟값 만들기
- 첫번째 풀이 : 수정하기. 절반만 맞았다.
import java.util.*;
class Solution
{
public int solution(int[] A, int[] B)
{
int answer = 0;
List<Integer> list1 = new ArrayList<Integer>();
List<Integer> list2 = new ArrayList<Integer>();
for(int i = 0; i < A.length; i++){
list1.add(A[i]);
}
Collections.sort(list1);
for(int i = 0; i < B.length; i++){
list2.add(B[i]);
}
Collections.sort(list2);
for(int i = 0; i < list1.size(); i++){
for(int j = list2.size()-1; j >= 0; j--){
int temp = list1.get(i) * list2.get(j);
answer += temp;
}
}
return answer;
}
}
- 두번째 풀이 : 탐색할 때, 어떻게 동작할지 동작 과정 생각하기!
- 중요!
import java.util.*;
class Solution
{
public int solution(int[] A, int[] B)
{
int answer = 0;
List<Integer> list1 = new ArrayList<Integer>();
List<Integer> list2 = new ArrayList<Integer>();
for(int i = 0; i < A.length; i++){
list1.add(A[i]);
}
Collections.sort(list1);
for(int i = 0; i < B.length; i++){
list2.add(B[i]);
}
Collections.sort(list2);
int j = list2.size()-1;
for(int i = 0; i < list1.size(); i++){
for(; j >= 0; j--){
int temp = list1.get(i) * list2.get(j);
answer += temp;
break;
}
j--;
}
return answer;
}
}
5) 피보나치 수**
- 첫번째 풀이 : 테케 절반만 통과함. 수정하기!
class Solution {
public int solution(int n) {
int answer = 0;
int[] temp = new int[n+1];
temp[0] = 0;
temp[1] = 1;
for(int i = 0; i < temp.length-2; i++){
temp[i+2] = temp[i] + temp[i+1];
answer = temp[i+2];
}
answer = answer % 1234567;
return answer;
}
}
- 두 번째 풀이 :
- DP 개념 이용! 중요!**
class Solution {
public int solution(int n) {
int answer = 0;
int[] temp = new int[n+1];
temp[0] = 0;
temp[1] = 1;
// 더 쉬운 풀이! : DP 개념 이용!
for(int i = 2; i < temp.length; i++){
temp[i] = (temp[i-1] + temp[i-2]) % 1234567;
}
return temp[n];
}
}
6) 카펫**
- 다시 풀기 : 생각하는 것이 까다롭다.
- 첫 번째 풀이 : 다시 풀기! 76점 수준
- 중간에 계산이 안맞는 경우가 있다. 이전 조합을 사용해야 할듯(‘-1’ 하기)
- 예) 가로/ 세로 : 6/4 -> 8/3
- 따라서, (가로길이 - 2) * (세로길이 - 2) == yellow 조건 고려하기!
- yellow 계산이 안 맞을 수도
import java.util.*;
class Solution {
public int[] solution(int brown, int yellow) {
int sum = brown + yellow;
List<Integer> list = new ArrayList<>();
int[] answer = new int[2];
for(int i = 0; i < sum; i++){
if(sum % (i+1) == 0){
list.add(i+1);
}
}
for(int i = 0; i < 2; i++){
if(list.size() % 2 != 0)
answer[i] += list.get(list.size()/2);
else{
answer[i] += list.get(list.size()/2-i);
}
}
return answer;
}
}
- 두 번째 풀이 :
- 등호 조건 주의, 그림을 직접 그려보면서 패턴을 정의해야 한다.
import java.util.*;
class Solution {
public int[] solution(int brown, int yellow) {
int sum = brown + yellow;
int[] answer = new int[2];
for(int i = 3; i < sum; i++){
int j = sum / i;
if((sum % i == 0) && j >= 3){
int col = Math.max(i, j);
int row = Math.min(i, j);
if(yellow == ((col -2) * (row -2))){
answer[0] = col;
answer[1] = row;
}
}
}
return answer;
}
}
7) 구명보트**
- 첫 번째 풀이 : 다시 풀기! 테케 2개 중 1개만 통과
import java.util.*;
class Solution {
public int solution(int[] people, int limit) {
int answer = 0;
int temp = limit;
int sub = 0;
Arrays.sort(people);
for(int i = people.length-1; i >= 0; i--){
sub = temp / people[i]; // 50 / 50 = 1
for(int j = 0; j < people.length-1-i; j++){
if(((sub-1) * people[j]) == people[j]){
answer++;
break;
}
sub = ((sub-1) * people[j]) % people[j];
if(sub == 0){
answer++;
break;
}
}
}
return answer;
}
}
- 두 번째 풀이** :
- 투 포인트로 찍어서 문제 풀이해보기!(그리디이긴 하지만 투포인터 이용)
- sum하고 limit 차이점이 중요!
import java.util.*;
class Solution {
public int solution(int[] people, int limit) {
int answer = 0;
int sum = 0;
int min = 0;
Arrays.sort(people);
for(int max = people.length-1; max >= min; max--){
sum = people[max] + people[min];
if(sum <= limit){
min++;
}
answer++;
}
return answer;
}
}
8) H-Index*
- 첫 번째 풀이 : 테케는 통과지만 실행 시, 모든 테스트에서 에러 발생
import java.util.*;
class Solution {
public int solution(int[] citations) {
int answer = 0;
int[] temp = new int[citations.length];
int[] count = new int[citations.length];
Arrays.sort(citations);
for(int i = 0; i < citations.length; i++) {
temp[i] = citations[citations.length - i - 1];
}
// 순회하면서 특정 값 비교하여 카운트하고 카운트가 전체 개수의 절반 이상일 때, 정답!
for(int i = 0; i < citations.length; i++) {
for(int j = 0; j < citations.length; j++) {
if(citations[j] >= temp[i]) {
count[i]++;
}
}
}
for(int i = 0; i < count.length; i++) {
if(count[i] > (count.length/2)){
answer = temp[i];
break;
}
}
return answer;
}
}
- 두 번째 풀이 : 문제 설명이 부족하지만, 예를 들어, [7,7,7,7,3]인 경우에
- H-Index는 4가 출력되어야하므로 citations에 포함되지 않는 경우도 고려해야 한다.
- 기존 코드에서 조건문만 수정하기. 항상 정답이 citations나 temp에 있는 것이 아니다!
import java.util.*;
class Solution {
public int solution(int[] citations) {
int answer = 0;
int[] temp = new int[citations.length];
int[] count = new int[citations.length];
Arrays.sort(citations);
for(int i = 0; i < citations.length; i++) {
temp[i] = citations[citations.length - i - 1];
}
// 순회하면서 특정 값 비교하여 카운트하고 카운트가 전체 개수의 절반 이상일 때, 정답!
for(int i = 0; i < citations.length; i++) {
for(int j = 0; j < citations.length; j++) {
if(citations[j] >= temp[i]) {
count[i]++;
}
}
}
// 항상 정답이 citations나 temp에 있는 것이 아니다!
for(int i = 0; i < count.length; i++) {
if(temp[i] >= count[i]){
answer = count[i];
}
}
return answer;
}
}
9) 1차 - 캐시
- 첫 번째 풀이 : 어렵다.. LRU 알고리즘 구현하는 방법?
import java.util.*;
class Solution {
public int solution(int cacheSize, String[] cities) {
int answer = 0;
// LinkedList 사용하거나 Queue 사용할 듯
List<String> city = new ArrayList<>();
int temp = 0;
for(int i = 0; i < cities.length; i++){
if(i % 3 == cacheSize-1){
if(city.contains(cities[i])){
temp = i;
answer = answer + 5;
city.remove(0);
}
}
city.add(cities[i]);
answer++;
}
return answer;
}
}
- 두 번째 풀이 :
10) 의상**
- 첫 번째 풀이 : 완전탐색 불가능
import java.util.*;
class Solution {
public int solution(String[][] clothes) {
int answer = 0;
int count = 0;
Map<String, String> hashMap = new HashMap<String, String>();
for(int i = 0; i < clothes.length; i++){
hashMap.put(clothes[i][0], clothes[i][1]);
}
for(int i = 0; i < hashMap.size(); i++){
for(int j = 0; j < hashMap.size(); j++){
if(hashMap.get(clothes[i][0]) != "face"){
if(hashMap.get(clothes[i][0]) != clothes[j][1]){
count++;
break;
}
}
else{
break;
}
}
break;
}
System.out.println(count);
for(int i = 0; i < hashMap.size(); i++){
for(int j = 0; j < hashMap.size(); j++){
if(count == 0){
if(hashMap.get(clothes[i][0]) == clothes[i][1]){
answer++;
}
}
else{
if(hashMap.get(clothes[i][0]) != "face"){
if(hashMap.get(clothes[i][0]) == clothes[j][1]){
answer += Math.pow(hashMap.size()- count , (hashMap.size() - count));
}
else{
answer++;
}
}
}
}
}
return answer;
}
}
- 두 번째 풀이** : stream API 공부하기!!
- stream API : test.stream().reduce(1, (a,b) -> a*b)
- stream의 reduce는 초기값을 ‘1’로 설정할 수 있고 스트림의 모든 요소를 반복적으로 처리할 수 있다.
- 옷 종류에 관한 경우의 수를 정리해서 Map 형식으로 다시 매핑해서 카운팅한다.
- 이 경우에는 옷을 안입는 경우의 수를 모두 하나씩 더하고 나서 마지막에 모두 안 입는 경우를 1개 뺀다.(적어도 한가지 정도는 입어야하니까)
- 이펙티브 자바 공부하기!!**
- stream API : test.stream().reduce(1, (a,b) -> a*b)
import java.util.*;
class Solution {
public int solution(String[][] clothes) {
int answer = 0;
Map<String, Integer> hashMap = new HashMap<String, Integer>();
for(int i = 0; i<clothes.length; i++){
hashMap.put(clothes[i][1], hashMap.getOrDefault(clothes[i][1],1) + 1);
}
Collection<Integer> test = hashMap.values();
answer = test.stream().reduce(1, (a,b) -> a*b) - 1;
// (a, b)를 "(a+1) * (b+1) - 1" 로 풀기
// 이것은 옷을 안입는 경우의 수를 모두 하나씩 더하고 나서 마지막에 모두 안입는 경우를 1개 뺀다.
// 적어도 한가지 정도는 입어야하니까
return answer;
}
}
11) 기능개발**
- 첫 번째 풀이 : 테케 모두 통과하지만, 런타임 에러 발생!
- Iterator의 iterator.hasNext() 사용에서 런타임 에러 발생한듯!
import java.util.*;
class Solution {
public int[] solution(int[] progresses, int[] speeds) {
int[] temp = new int[speeds.length];
Queue<Integer> queue1 = new LinkedList<Integer>();
Queue<Integer> queue2 = new LinkedList<Integer>();
for(int prog : progresses){
queue1.add(100 - prog);
}
for(int i = 0; i < speeds.length; i++){
int temp2 = queue1.poll();
int temp3 = temp2 / speeds[i];
if(temp2 % speeds[i] != 0){
queue2.add(temp3+1);
}
else{
queue2.add(temp3);
}
}
int count = 1;
// 주의** : Queue는 poll하면 remove되기 때문에 for문에서 index가 사라진다.
// 그래서 Iterator 이용하기!!
Iterator iter = queue2.iterator();
Iterator iter2 = queue2.iterator();
int temp4 = (int) iter.next();
int i = 0;
int count2 = 1;
int temp6 = (int) iter2.next();
while(iter2.hasNext()){
int temp7 = (int) iter2.next();
if(temp7 > temp6){
count2++;
}
}
int[] answer = new int[count2];
while(iter.hasNext()){
int temp5 = (int) iter.next();
if(temp4 > temp5){
count++;
}
else{
temp4 = temp5;
System.out.println(temp4);
answer[i] = count;
i++;
count = 1;
if(!iter.hasNext()){
answer[i] = 1;
}
}
if(!iter.hasNext()){
answer[i] = count;
}
}
return answer;
}
}
- 두 번째 풀이 ; Iterator 빼고 Queue, ArrayList로만 다시 풀기
- 위와 로직이 같지만, queue의 peek(), poll() 이용하기!
import java.util.*;
class Solution {
public int[] solution(int[] progresses, int[] speeds) {
ArrayList<Integer> list = new ArrayList<>();
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < progresses.length; i++) {
if ((100 - progresses[i]) % speeds[i] == 0) {
q.add((100 - progresses[i]) / speeds[i]);
} else {
q.add((100 - progresses[i]) / speeds[i] + 1);
}
}
int x = q.poll();
int count = 1;
while (!q.isEmpty()) {
if (x >= q.peek()) {
count++;
q.poll();
} else {
list.add(count);
count = 1;
x = q.poll();
}
}
list.add(count);
int[] answer = new int[list.size()];
for (int i = 0; i < answer.length; i++) {
answer[i] = list.get(i);
}
return answer;
}
}
12) 프로세스**
- 첫 번째 풀이 : queue 순서 조작하기!, 테케 1개 통과함. 다시 풀기
- 큐, 우선순위 큐
import java.util.*;
class Solution {
public int solution(int[] priorities, int location) {
// 값을 비교해서 가장 높은 값이면 비교해서 같으면, 빼서 뒤로 보내기!
// peek로 비교해서 poll하고 add하기
// priorities와 queue를 비교하기!
int answer = 0;
int temp = 0;
int temp2 = 0;
int count = 0;
Queue<Integer> queue = new LinkedList<Integer>();
PriorityQueue<Integer> queue2 = new PriorityQueue<Integer>();
for(int pri : priorities){
queue.add(pri);
}
for(int pri2 : priorities){
queue2.add(pri2);
}
for(int i = 0; i < priorities.length; i++){
temp = queue2.poll();
}
int temp6 = 0;
for(int i = 0; i < priorities.length; i++){
temp2 = queue.peek();
// 가장 큰 숫자인지 비교해서 index 담기!!
if(temp2 == temp){
count = count + i;
break;
}
else if(temp2 != temp){
int temp3 = queue.poll();
count = 1;
if(temp6 == temp3)
count++;
temp6 = temp3;
queue.add(temp2);
}
}
for(int i = 0; i < priorities.length; i++){
int temp4 = priorities[location];
// priorities : 2, 1, 3, 2
// queue : 3, 2, 2, 1
int temp5 = queue.poll();
if(temp4 != temp5){
answer++;
}
else if(temp4 == temp5){
while(count != answer){
answer++;
}
answer++;
return answer;
}
}
return answer;
}
}
- 두 번째 풀이 : 우선순위 큐로 다시 풀기
- 거의 로직은 비슷한거 같은데 index 컨트롤 하는 것 다시 생각하기
- 암기하기, 우선순위큐를 이용하는 방법!
if(queue2.peek() == priorities[i]){}: 이 부분 중요- 최대값부터 다시 시작하겠다는 뜻
- 중요!! :
- 우선순위큐는 중복값을 허용하고 우선순위가 같은 경우에 값이 같다면 그들은 큐에서 그들의 순서에 의해 처리된다.
- 우선순위가 같고 값이 같은 상황에서는 일단, 순서대로 처리가 이루어진다.
- 우선순위큐는 중복값을 허용하고 우선순위가 같은 경우에 값이 같다면 그들은 큐에서 그들의 순서에 의해 처리된다.
import java.util.*;
class Solution {
public int solution(int[] priorities, int location) {
// peek로 비교해서 poll하고 add하기
// priorities와 queue를 비교하기!
int answer = 0;
Queue<Integer> queue = new LinkedList<Integer>();
PriorityQueue<Integer> queue2 = new PriorityQueue<Integer>(Collections.reverseOrder());
for(int pri2 : priorities){
queue2.add(pri2);
}
while (!queue2.isEmpty()) {
for(int i = 0; i < priorities.length; i++){
if(queue2.peek() == priorities[i]){
if(i == location){
answer++;
return answer;
}
queue2.poll();
answer++;
}
}
}
return -1;
}
}
13) 타겟 넘버**
- 첫 번째 풀이 : boolean 값을 이용했는데 실패해서 DFS 개념 이용하기!
class Solution {
public int solution(int[] numbers, int target) {
int answer = 0;
int temp = 0;
boolean[] chk = new boolean[numbers.length];
for(int i = 0; i < numbers.length; i++){
if(chk[i] && target < temp)
temp += numbers[i];
else{
temp -= numbers[i];
}
chk[i] = !chk[i];
}
return answer;
}
}
- 두 번째 풀이 : DFS 개념 이용하기
- DFS, BFS를 이용한 완전 탐색 문제를 풀 때는 항상 무엇을 탐색의 대상으로 삼아야 하는지에 대한 기준을 내리지 못해 삽질을 많이 하는 것 같다. 완전탐색을 이용해 모든 경우의 수를 고려하면 된다.
- 생각보다 간단한 문제였다. 경우의 수를 생각하기 때문에 plus, minus의 경우를 모두 따진다.
- 중요** : DFS, 재귀함수, 완전탐색이라서 for 반복문 사용 안 해도 되고 ‘수행조건’이랑 ‘탈출조건’만 설계하면 된다.
class Solution {
int answer = 0;
public int solution(int[] numbers, int target) {
dfs(numbers, 0, target, 0);
return answer;
}
public void dfs(int[] numbers, int depth, int target, int sum) {
if(depth == numbers.length){
if(target == sum)
answer++;
}
else{
dfs(numbers, depth+1, target, sum + numbers[depth]);
dfs(numbers, depth+1, target, sum - numbers[depth]);
}
}
}
14) 전화번호 목록
- 첫 번째 풀이 : 75점 풀이, 수정하기!
import java.util.*;
class Solution {
public boolean solution(String[] phone_book) {
boolean answer = true;
for(String phone : phone_book){
list.add(phone);
}
for(int i = 0; i < phone_book.length; i++){
for(int j = 0; j < phone_book.length; j++){
if(i != j){
if(phone_book[i].contains(phone_book[j])){
System.out.println(phone_book[j]);
answer = false;
return answer;
}
else{
answer = true;
}
}
}
}
return answer;
}
}
- 두 번째 풀이** :
- 효율성 테스트** : Arrays.sort로 정렬 후 바로 뒤의 index만 비교하면, 훨씬 효율적이다.
- startsWith() : 대상 문자열이 특정 문자 또는 문자열로 시작하는지 체크하는 함수이다.
- contains() : 대상 문자열에 특정 문자열이 포함되어 있는지 확인하는 함수이다.
- String 은 정렬하면 사전순으로 정렬되기 때문에, 따라서 무조건 앞의 변수만 비교하면 되기 때문에 for 문 한번으로 끝낼 수 있습니다.
- 문자열이 그대로 일치하는 것을 찾는 문제가 아니기 때문에 contains() 보다는 startsWith()를 사용한다.
import java.util.*;
class Solution {
public boolean solution(String[] phone_book) {
boolean answer = true;
Arrays.sort(phone_book);
for(int i = 0; i < phone_book.length-1; i++){
if(phone_book[i+1].startsWith(phone_book[i])){
System.out.println(phone_book[i+1]);
answer = false;
break;
}
}
return answer;
}
}
15) 더 맵게
- 첫 번째 풀이 : 테케 통과했지만 50점 풀이, 효율성 테스트 다시
import java.util.*;
class Solution {
public int solution(int[] scoville, int K) {
int answer = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int scov : scoville){
pq.add(scov);
}
for(int i = 0; i < pq.size(); i++){
if(!pq.isEmpty()){
if(pq.peek() < K){
if(pq.size() >= 2){
pq.add(pq.poll() + (pq.poll() * 2));
}
answer++;
}
}
}
if(pq.peek() < K){
return -1;
}
return answer;
}
}
- 두 번째 풀이 : 위의 풀이보다 훨씬 더 간단하다.
- pq.peek()는 초기에 for문보다는 while문으로만 비교하고 pq.size()로 최종 비교
import java.util.*;
class Solution {
public int solution(int[] scoville, int K) {
int answer = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int scov : scoville){
pq.add(scov);
}
while(pq.peek() < K){
if(!pq.isEmpty()){
if(pq.size() < 2){
return -1;
}
pq.add(pq.poll() + (pq.poll() * 2));
answer++;
}
}
return answer;
}
}
16) 주식가격
-
앞으로 문제 푸는 방법 -> 유형별로 lv.2 : 10개, lv.3 : 12개 풀고 다시 lv.2 Kakao 풀기
-
이 문제는 이해하는 것이 어렵다.
- 주식 가격이 전체 가격 중에서 이후 시간에 해당 가격으로부터 떨어지지 않는 시간을 return하는 문제이다.
- 첫 번째 풀이 : index 이용해서 푸는 방법
import java.util.*;
class Solution {
public int[] solution(int[] prices) {
int[] answer = new int[prices.length];
for(int i = 0; i < prices.length; i++){
for(int j = i+1; j < prices.length; j++){
if(prices[i] <= prices[j]){
answer[i]++;
}
else{
answer[i]++;
break;
}
}
}
return answer;
}
}
- 두 번째 풀이 : stack 이용해보기 출처
- 주식가격이 떨어지지 않는 구간에는 일단 스택에 index(시간 카운트)를 넣어주고 주식가격이 떨어지는 구간에는 ‘현재시간-초기시간’ 계산식 진행
class Solution {
public int[] solution(int[] prices) {
int[] ans = new int[prices.length];
Stack<Integer> stack = new Stack();
for (int i = 0; i < prices.length; i++) {
while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
ans[stack.peek()] = i - stack.peek();
stack.pop(); // 답을 구했기 때문에 stack에서 제거한다
}
stack.push(i);
}
while (!stack.isEmpty()) { // 값을 구하지 못한 index == 끝까지 가격이 떨어지지 않은 주식
ans[stack.peek()] = prices.length - stack.peek() - 1;
stack.pop();
}
return ans;
}
}
17) 다리를 지나는 트럭
- 첫 번째 풀이 : 수정하기
import java.util.*;
class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
int answer = 0;
int temp = 0;
int poll = 0;
Queue<Integer> queue = new LinkedList<>();
for(int truck : truck_weights){
queue.add(truck);
}
for(int i = 0; i < queue.size(); i++){
if(queue.peek() < weight){
if((weight >= temp + queue.peek())){
}
else{
temp = 0;
answer += bridge_length;
}
poll = queue.poll();
temp = poll + temp;
}
// if(i == queue.size()-1){
// answer += poll;
// }
}
return answer;
}
}
- 두 번째 풀이_1 : 어렵다
- 대기하는 트럭을 queue에 따로 저장하지 않고 truck_weight 배열을 활용해서 index를 만들고 1씩 더하는 방법을 사용하면 조금 더 효율적일 것
import java.util.*;
class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
int answer = 0;
Queue<Integer> bridgeQue = new LinkedList<>();
Queue<Integer> readyTruckQue = new LinkedList<>();
// 초기 다리 상태 세팅
for(int i = 0 ; i<bridge_length ; i++)
{
bridgeQue.offer(0);
}
// 대기 트럭 세팅
for(int i : truck_weights)
{
readyTruckQue.offer(i);
}
int time = 0;
int totalWeight = 0;
while(!bridgeQue.isEmpty())
{
// while 한번 도는게 1초라고 생각
// 시작하자마자 다리 맨 마지막부분에서 트럭을 빼버림
totalWeight -= bridgeQue.peek();
bridgeQue.poll();
// 대기 트럭열에 있던 마지막 트럭이 다리에 올라가면, 다리 길이 만큼의 시간 후에
// 마지막 트럭이 다리를 건너기때문에 다리 길이(*1초) 만큼 시간이 소요되면 모든 트럭이 건너게 됨.
if(readyTruckQue.isEmpty())
{
time += bridge_length;
break;
}
else
{
// 다리의 하중량을 버틸 수 있으면 트럭 투입
if((totalWeight+readyTruckQue.peek()) <= weight)
{
bridgeQue.offer(readyTruckQue.peek());
totalWeight+=readyTruckQue.peek();
readyTruckQue.poll();
}
// 다리의 하중량때문에 트럭 못들어가면 0으로 넣어줌
else {
bridgeQue.offer(0);
}
}
time++;
}
answer = time;
return answer;
}
}
- 두 번째 풀이_2 : 어렵다
import java.util.*;
class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
int answer = 0;
Queue<Integer> bridge = new LinkedList<>();
// 비어있는 다리의 공간을 0으로 가득 채웠다.
for(int i=0;i<bridge_length;i++){
bridge.offer(0);
}
int index = 0;
// 다리에 있는 현재 트럭의 무게이다.
int currentWeight = 0;
// 트럭이 더이상 남아있지 않을 때 탈출해주기 위해 조건을 만들었다.
while(index < truck_weights.length){
// 현재 다리에 있는 트럭무게에서 곧 나갈 트럭의 무게를 빼준다.
currentWeight -= bridge.poll();
// 새 트럭이 들어올 것이므로 1초를 추가한다.
answer++;
// 현재 다리에 있는 트럭 무게와 곧 들어올 트럭 무게의 합과 다리의 하중을 비교
if(currentWeight + truck_weights[index] <= weight){
// 무게를 버틴다면 다리에 트럭을 추가한다.
bridge.offer(truck_weights[index]);
// 현재 다리에 있는 트럭 무게에도 새 트럭 무게를 더해준다.
// 그리고 다음 트럭을 지정하기 위해 후위 연산자를 써주어 index를 증가시켰다.
currentWeight += truck_weights[index++];
} else{
// 버티지 못한다면 0을 추가한다.
bridge.offer(0);
}
}
//처음 설정한 0으로 채워진 다리가 전부 치환되면 결국 처음 다리 길이와 같으므로
//트럭이 지나간 시간 + 다리 길이
return answer + bridge_length;
}
}
- 두 번째 풀이_2 : 최종 정리
import java.util.*;
class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
int answer = 0;
int temp = 0;
Queue<Integer> queue = new LinkedList<>();
for(int i = 0; i < bridge_length; i++){
queue.add(0);
}
int i = 0;
while(i < truck_weights.length){
temp -= queue.poll();
answer++;
if(temp + truck_weights[i] <= weight){
queue.add(truck_weights[i]);
temp += truck_weights[i++];
}
else{
queue.add(0);
}
}
return answer + bridge_length;
}
}
18) 큰 수 만들기
- 첫 번째 풀이 : 다시 풀기
import java.util.*;
class Solution {
public String solution(String number, int k) {
String answer = "";
String[] nums = number.split("");
int count = 0;
List<Integer> list = new ArrayList<Integer>();
for(String num : nums){
list.add(Integer.parseInt(num));
}
for(int i = 1; i < list.size(); i++){
if(list.get(i-1) > list.get(i)){
answer += list.get(i-1);
}
if(list.get(i-1) < list.get(i)){
count++;
continue;
}
if(count == k){
return answer;
}
}
return answer;
}
}
- 두 번째 풀이 :
- index에는 가장 큰 수 다음 index를 넣어준다. 이유는 그 다음 문자열부터 가장 큰 수를 찾아야 하기 때문이다.
- index 주의!! 여러 번 풀기!! 그리디는 내가 생각하는 방법과 반대 방향으로 문제를 풀어야 한다.
- 제거하지 않고 index를 조회하는 방식으로 풀이!
- 참고
import java.util.*;
class Solution {
public String solution(String number, int k) {
StringBuilder sb = new StringBuilder();
int index = 0;
int max = 0;
for(int i=0; i < number.length() - k; i++) {
max = 0;
for(int j = index; j <= k+i; j++) {
if(max < number.charAt(j)-'0') {
max = number.charAt(j)-'0';
index = j+1;
}
}
sb.append(max);
}
return sb.toString();
}
}
19) 가장 큰 수
- 첫 번째 풀이 : 수정하기
- 메모리 에러
import java.util.*;
import java.lang.Math;
class Solution {
public String solution(int[] numbers) {
String answer = "";
String temp = "";
int tempNum = -1;
List<Integer> temp1 = new ArrayList<>();
String[] temps = new String[(int)Math.pow(2, numbers.length)];
List<String> temp2 = new ArrayList<>();
for(int i = 0; i < (int)Math.pow(2, numbers.length); i++){
for(int j = 0; j < numbers.length; j++){
if(tempNum != j){
temp1.add(numbers[j]);
}
else
continue;
if(temp1.size() != numbers.length){
j = 0;
}
else
break;
}
tempNum = i;
for(Integer num : temp1){
if(!num.equals(null))
temp += String.valueOf(num);
}
temps[i] = temp;
}
for(String num1 : temps){
if(!num1.equals(null))
temp2.add(num1);
}
Collections.sort(temp2);
answer = temp2.get(temp2.size()-1);
return answer;
}
}
- 두 번째 풀이 : Comparator, StringBuilder 이용!
- 숫자들의 앞자리 숫자가 큰 수가 먼저 와야 가장 큰 수를 만들 수 있기 때문에 이를 기준으로 내림차순으로 숫자를 정렬!
- 내림차순하는 방법 : Collections.sort() 보다는 다른 방식 이용하기!**
- Arrays.sort() 내부에서 Comparator의 compareTo()를 이용하는 방식!
- 내림차순 : (o2+o1).compareTo(o1+o2);
- 오름차순 : (o1+o2).compareTo(o1+o2);
- 정렬된 숫자를 이어붙이는 경우, String 값을 더하는 것보다 StringBuilder 이용해 append()하는 것을 추천!
- 이유는 String은 Immutable(불변 객체)이기 때문이다. String을 합치는 연산이 많을수록 StringBuilder가 유리하다.
import java.util.*;
public class Solution {
public String solution(int[] numbers) {
String[] arr = new String[numbers.length];
for (int i = 0; i < arr.length; i++) {
arr[i] = String.valueOf(numbers[i]);
}
Arrays.sort(arr, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));
if (arr[0].equals("0")) {
return "0";
}
StringBuilder answer = new StringBuilder();
for (int i = 0; i < arr.length; i++) {
answer.append(arr[i]);
}
return answer.toString();
}
}
20) 소수 찾기
- 첫 번째 풀이 : dfs 이용하기
- 중요 개념 정리 :
- split가 아니라 substring 이용하기
- ‘1, 7, 17, 71’ 구조를 만드는 방법 중요!!
- set으로 이전 값 중복 제거
import java.util.*;
class Solution {
public int solution(String numbers) {
Set<Integer> set = new HashSet<>();
dfs(numbers, "", set);
int answer = 0;
for(Integer num : set){
int i;
for(i = 2; i < num ; i++){
if(num % i == 0){
break;
}
}
if(i == num){
answer++;
}
}
return answer;
}
public void dfs(String numbers, String temp, Set<Integer> set) {
int length = numbers.length();
// '1, 7, 17, 71' 구조를 만드는 방법(set으로 중복 제거)
if(!"".equals(temp)){
set.add(Integer.valueOf(temp));
}
for(int i = 0; i < length; i++){
dfs(numbers.substring(0, i) + numbers.substring(i+1, length),
temp + numbers.charAt(i),
set);
}
}
}
- 두 번째 풀이 : 백트래킹 이용하여 다시 풀어보기!!
- 방문했는지 판단하기(boolean[])
import java.io.*;
import java.util.*;
class Solution {
static ArrayList<Integer> arr = new ArrayList<>();
static boolean[] check = new boolean[7];
public int solution(String numbers) {
int answer = 0;
for(int i=0; i<numbers.length(); i++){
dfs(numbers,"",i+1);
}
for(int i=0; i<arr.size(); i++){
if(prime(arr.get(i))) answer++;
}
return answer;
}
//백트래킹
static void dfs(String str, String temp, int m) {
if(temp.length() == m){
int num = Integer.parseInt(temp);
if(!arr.contains(num)){
arr.add(num);
}
}
for(int i=0; i<str.length(); i++){
if(!check[i]){
check[i] = true;
temp += str.charAt(i);
dfs(str, temp, m);
check[i] = false;
temp = temp.substring(0, temp.length()-1);
}
}
}
//소수 판단
static boolean prime(int n) {
if(n<2) return false;
for(int i=2; i*i<=n; i++) {
if(n % i == 0) return false;
}
return true;
}
}
2. Lv.3
1) 네트워크**
- 첫 번째 풀이 : BFS 이용하기
- 반복해서 암기하기! BFS 기본 문제
- 기존에 queue에서 poll이 되고나서 start 위치 빼고나서도 완전 탐색을 위해서 또 다시 나머지 위치도 방문!!
import java.util.*;
class Solution {
static boolean[] visited;
public int solution(int n, int[][] computers) {
int answer = 0;
visited = new boolean[n];
for(int i = 0; i < n; i++){
if(visited[i] == false){
bfs(i, computers, n);
answer++;
}
}
return answer;
}
public void bfs(int i, int[][] computers, int n){
Queue<Integer> queue = new LinkedList<>();
queue.add(i);
visited[i] = true;
while(!queue.isEmpty()){
int value = queue.poll();
// 위에서 poll되어서 start 위치 빼고 완전 탐색을 위해서 나머지도 위치 방문!!
for(int j = 0; j < n; j++){
if(visited[j] == false && computers[value][j] == 1){
visited[j] = true;
queue.add(j);
}
}
}
}
}
- 두 번째 풀이 : DFS 이용하기
- 메인에서 로직이 돌아 한 번 탐색하여 answer에 1을 더한다. 그리고나서 완전 탐색을 위해 한번 더 탐색한다.
- answer에 1을 더하고 난 후 DFS 깊이 탐색에서는 answer에 1을 더하지 않는다. 네트워크가 연결되어 있는 모든 것은 1개로 생각하기 때문이다.
import java.util.*;
class Solution {
static boolean[] visited;
public int solution(int n, int[][] computers) {
int answer = 0;
visited = new boolean[n];
// 2. dfs
for(int i = 0; i < n; i++){
if(visited[i] == false){
dfs(i, computers, n);
answer++;
visited[i] = true;
}
}
return answer;
}
public void dfs(int i, int[][] computers, int n){
// 메인에서 로직이 돌아서 한 번 탐색하여 answer에 1을 더하고나서
// 완전 탐색을 위해 한번 더 탐색한다.
visited[i] = true;
for(int j = 0; j < n; j++){
if(visited[j] == false && computers[i][j] == 1){
dfs(j, computers, n);
}
}
}
}
2) 베스트앨범
- 첫 번째 풀이 : 다시 수정, 최적화하기
import java.util.*;
class Solution {
public int[] solution(String[] genres, int[] plays) {
// List
List<String> list1 = new ArrayList<>();
List<Integer> list2 = new ArrayList<>();
// Map<genres, plays>
Map<String, Integer> hsMap = new HashMap<>();
// Set
Set<String> hsSet = new HashSet<>();
/* 초기화 */
for(int i = 0; i < genres.length; i++){
list1.add(genres[i]);
list2.add(Integer.valueOf(plays[i]));
hsSet.add(genres[i]);
}
/* 장르별 크기 합 구하기 */
for(String genre : hsSet){
Integer temp = 0;
for(int i = 0; i < genres.length; i++){
if((genre.equals(list1.get(i)))){
temp += list2.get(i);
}
}
hsMap.put(genre, temp);
}
System.out.println(hsMap.get("pop"));
/* 장르별 크기 순 정렬 */
List<String> listSort = new ArrayList<>();
String genre1 = "";
for(String genre : hsSet){
if(genre1 == ""){
genre1 = genre;
continue;
}
if(hsMap.get(genre1) > hsMap.get(genre)){
listSort.add(genre1);
listSort.add(genre);
}
else{
listSort.add(genre);
listSort.add(genre1);
}
}
int[] answer = new int[listSort.size() * 2];
// Collections.sort(list1, (o1, o2) -> (o2+o1).compareTo(o1+o2));
// Collections.sort(list2, (o1, o2) -> (o2+o1).compareTo(o1+o2));
// Collections.reverse(list2);
Map<String, Integer> hsMap1 = new HashMap<>();
int[] temp1 = new int[listSort.size() * 2];
int[] temp2 = new int[2];
/* 장르 내 많이 재생된 노래순 정렬 */
/* 추가 : 같은 값일 경우 처리하기 */
for(int i = 0; i < listSort.size(); i++){
int count = 0;
for(int j = 0; j < answer.length; j++){
if(listSort.get(i).equals(list1.get(j))){
if(count == 2){
break;
}
temp1[j] += list2.get(j);
count++;
}
System.out.println(temp1[j]);
}
}
for(int i = 0; i < plays.length; i++){
for(int j = 0; j < answer.length; j++){
if(plays[i] == temp1[j]){
answer[i] += j;
}
}
}
return answer;
}
}
3) 단어 변환
a. 수정하기
- 방문 배열 추가, 한 문자만 다른 것 체크하는 로직 추가
import java.util.*;
class Solution {
public int solution(String begin, String target, String[] words) {
int answer = 0;
int depth = 0;
dfs(begin, target, words, depth);
answer = depth;
return answer;
}
// 수정하기 : 방문 배열 추가, 한 문자만 다른 것 체크하는 로직 추가
public void dfs(String begin, String target, String[] words, int depth){
for(int i = 0; i < words.length; i++){
if(!begin.equals(target)){
begin = words[i++];
dfs(begin, target, words, depth);
}
}
}
}
b. 수정하기2
- static 변수 선언 주의!
- java라서 여러 번 타고 들어간다.
import java.util.*;
class Solution {
static int answer = 0;
static int depth = 0;
static boolean[] visited;
public int solution(String begin, String target, String[] words) {
visited = new boolean[words.length];
dfs(begin, target, words, 0);
return answer;
}
public static boolean oneDiffCheck(String word1, String word2){
int count = 0;
for(int i = 0; i < word1.length(); i++){
if(word1.charAt(i) != word2.charAt(i)){
count++;
}
}
if(count == 1){
return true;
}
else
return false;
}
// 방문 배열 추가, 한 문자만 다른 것 체크하는 로직 추가
public static void dfs(String begin, String target, String[] words, int depth){
if(answer <= depth){
return ;
}
if(begin.equals(target)){
answer = depth;
return ;
}
for(int i = 0; i < words.length; i++){
if(oneDiffCheck(begin, words[i]) && !visited[i]){
visited[i] = true;
dfs(words[i], target, words, depth+1);
visited[i] = false;
}
}
}
}
c. 최종 코드!!
- 완전탐색으로 하면서, depth 카운팅!
- 일치하지 않을 경우도 추가로 생각해줘야한다! 50인 경우는 문제 조건에서 words에는 3개이상 50개 이하의 단어가 존재해서 ‘50’으로 설정함.
import java.util.*;
class Solution {
static int answer = 50;
static boolean[] visited;
public int solution(String begin, String target, String[] words) {
visited = new boolean[words.length];
dfs(begin, target, words, 0);
if(answer == 50){
return 0;
}
return answer;
}
public static boolean oneDiffCheck(String word1, String word2){
int count = 0;
for(int i = 0; i < word1.length(); i++){
if(word1.charAt(i) != word2.charAt(i)){
count++;
}
}
if(count == 1){
return true;
}
else
return false;
}
// 방문 배열 추가, 한 문자만 다른 것 체크하는 로직 추가
public static void dfs(String begin, String target, String[] words, int depth){
if(answer <= depth){
return ;
}
if(begin.equals(target)){
answer = depth;
return ;
}
for(int i = 0; i < words.length; i++){
if(oneDiffCheck(begin, words[i]) && !visited[i]){
visited[i] = true;
dfs(words[i], target, words, depth+1);
visited[i] = false;
}
}
}
}
4) 등굣길
a. 수정하기
import java.util.*;
class Solution {
static int[][] D;
static boolean[][] visited;
public int solution(int m, int n, int[][] puddles) {
int answer = 0;
visited = new boolean[m][n];
D = new int[m][n];
for(int i = 1; i < n+1; i++){
for(int j = 1; j < m+1; j++){
if((D[j][i] != puddles[j][i]) && !visited[j][i]){
D[j][i] = D[j-1][i-1] + 1;
visited[j][i] = true;
answer++;
}
}
}
return answer;
}
}
b. 최종 코드
- index 정의하는 것, 정답 맞추는 형식에 관한 조건 주의!!,
- 문제 잘 읽기!
- 경로 찾기 : 알고리즘 생각!
- 최단 거리, 경우의 수
- Dp라서 점화식으로 해석하기!!
- puddles를 재정의 하는 것이 까다로움.
- 문제 조건에서 행/열이 순서 바뀐 것 주의!
import java.util.*;
class Solution {
static int[][] D;
public int solution(int m, int n, int[][] puddles) {
int answer = 0;
D = new int[n+1][m+1];
for(int i = 0; i < puddles.length; i++){
int x = puddles[i][0];
int y = puddles[i][1];
D[y][x] = -1;
}
D[1][1] = 1;
for(int i = 1; i < n+1; i++){
for(int j = 1; j < m+1; j++){
if(D[i][j] == -1){
continue;
}
if(D[i][j-1] != -1){ // y축 이동!!
D[i][j] += D[i][j-1];
}
if(D[i-1][j] != -1){ // x축 이동!!
D[i][j] += D[i-1][j];
}
D[i][j] %= 1000000007;
}
}
answer = D[n][m] % 1000000007;
return answer;
}
}
5) 여행경로
a. 수정하기
- 좀 더 간단한 방법이 있을 것 같다.
- 현재는 너무 복잡하다.
import java.util.*;
class Solution {
static String[] A;
static String[] B;
static String[] answer;
static int depth;
static Stack<String> stack;
public String[] solution(String[][] tickets) {
A = new String[tickets.length + 1];
B = new String[tickets.length + 1];
stack = new Stack<String>();
depth = 0;
int count = 0;
for(int i = 0; i<tickets.length; i++){
A[i+1] = tickets[i][1];
B[i+1] = tickets[i][0];
if(A[i+1].equals("ICN")){
count++;
}
}
Integer[] num = new Integer[count];
if(count > 1){
for(int i = 0; i<tickets.length; i++){
if(A[i+1].equals("ICN")){
num[i] = i+1;
}
}
}
for(int i = 1; i<tickets.length+1; i++){
if(A[i].equals("ICN")){
if(count > 1){
B[i] = B[num[i]].charAt(0) > B[num[i-1]].charAt(0) ? B[num[i]] : B[num[i-1]];
}
dfs(B[i], tickets, depth);
}
}
answer = new String[depth];
for(int i = 0; i<depth; i++){
answer[i] = stack.pop();
}
return answer;
}
public static void dfs(String begin, String[][] tickets, int depth){
for(int i = 1; i < tickets.length+1; i++){
if(A[i].equals(begin) && A[i].equals(B[i-1])){
stack.add(begin);
stack.add(B[i-1]);
dfs(B[i-1], tickets, depth++);
}
}
}
}
b. 최종 코드
-
DFS에는 항상 방문배열 추가하기!!
-
복잡한 로직에서 이것을 List를 이용하여 정렬 이용해서 한 번에 해결하기!
import java.util.*;
class Solution {
static boolean[] visited;
static List<String> list;
public String[] solution(String[][] tickets) {
visited = new boolean[tickets.length];
list = new ArrayList<>();
dfs("ICN", "ICN", tickets, 0);
Collections.sort(list);
return list.get(0).split(" ");
}
public static void dfs(String now, String next, String[][] tickets, int depth) {
if(depth == tickets.length){
list.add(next);
return;
}
for(int i = 0; i < tickets.length; i++){
if( !visited[i] && now.equals(tickets[i][0]) ){
visited[i] = true;
dfs(tickets[i][1], next + " " + tickets[i][1], tickets, depth+1);
visited[i] = false;
}
}
}
}
6) 단속카메라
a. 수절하기
- 테케는 통과하지만, 정확성과 효율성에서 실패! 다시 수정하기!
import java.util.*;
class Solution {
public int solution(int[][] routes) {
int answer = 0;
for(int i = 0; i < routes.length; i++){
for(int j = i; j < routes.length-1; j++){
if(routes[j][1] > routes[j+1][0] && routes[j][0] > routes[j+1][0]){
answer++;
}
}
}
return answer;
}
}
b. 간략히 수정
- 역시나 테케는 통과하지만, 정확성과 효율성에서 실패! 다시 수정하기!
- 차량이 1대 이상 10,000대 이하라서 효율성 실패
import java.util.*;
class Solution {
public int solution(int[][] routes) {
int answer = 0;
List<Integer> list = new ArrayList<>();
for(int i = 0; i < routes.length-1; i++){
for(int j = i+1; j < routes.length-i; j++){
if(routes[i][1] < routes[i+j][0]){
answer++;
}
}
}
return answer;
}
}
c. 최종 수정
- 이전에 효율성 문제가 발생했기 때문에 for문 2번이 아니라 Collection 등의 자료구조를 이용해야 한다.
- 정렬을 위해 오름차순을 이용하는 것이 핵심이다.
- 따라서, 이차원 배열의 정렬을 위해 Comparator 인터페이스를 사용!!
- 오름차순은 Comparator + 람다식으로 간편하게 사용했다.
import java.util.*;
class Solution {
public int solution(int[][] routes) {
int answer = 0;
Arrays.sort(routes, (route1, route2) -> (route1[1] - route2[1]));
int minNum = Integer.MIN_VALUE;
for(int[] route : routes){
if(minNum < route[0]){
minNum = route[1];
answer++;
}
}
return answer;
}
}
d. 원래 Comparator 인터페이스 사용
- 길어서 위처럼 람다식을 이용하여 Comparator를 사용하자!
Arrays.sort(routes, new Comparator<int[]>() {
@Override
public int compare(int[] route1, int[] route2) {
return route1[1] - route2[1];
}
});
7) 섬 연결하기
a. 수절하기