프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

Language: Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.Arrays;
 
class Solution {
    public String solution(String s) {
        String answer = "";
        char[] sToCharArr = new char[s.length()];
        for(int i=0; i<s.length(); i++){
            sToCharArr[i] = s.charAt(i);
        }
        Arrays.sort(sToCharArr);
        
        StringBuilder sb = new StringBuilder();
        for(int i=s.length()-1; i>-1; i--){
            sb.append(sToCharArr[i]);
        }
        answer = sb.toString();
        return answer;
    }
}
 
 

1. sToCharArr[i] = s.charAt(i)

    - String → char[]

2. Arrays.sort(sToCharArr)

    - 오름차순 정렬

    - Collections.reverseOrder() 사용 시, 

        - error: no suitable method found for sort(char[],Comparator<Object>) 발생

3. StringBuilder sb = new StringBuilder()

    -역순으로 문자열을 저장할 StringBuilder 선언

4. for(int i=s.length()-1; i>-1; i--)

    - 역순으로 저장

5. answer = sb.toString()

    - StringBuilder → String

 

 

😮 찾아본 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.Arrays;
 
class Solution {
    public String solution(String s) {
        String answer = "";
        char[] sToCharArr = s.toCharArray();
        Arrays.sort(sToCharArr);
        
        answer = new StringBuilder(new String(sToCharArr))
            .reverse()
            .toString();
        
        return answer;
    }
}
 
 

1. new StringBuilder(new String(sToCharArr))

    - char[] → String

2. reverse()

    - StringBuilder 내 reverse 함수 사용

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.Arrays;
import java.util.Collections;
 
class Solution {
    public String solution(String s) {
        String answer = "";
        
        String[] sArr = s.split("");
        Arrays.sort(sArr, Collections.reverseOrder());
 
        StringBuilder sb = new StringBuilder();
        for(String str : sArr){
            sb.append(str);
        }
        
        answer = sb.toString();
        
        return answer;
    }
}
 
 

1. String[] sArr = s.split("")

    - 문자 1개씩 split → String[]

2. Arrays.sort(sArr, Collections.reverseOrder())

    - 객체: Collections.reverseOrder 사용

 

 

 

🔗 소스 코드
GitHub

 

📚 참고 자료

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

🙂 확인 사항

1. 무게 중심 구하기: 경우의수 7개 

2. 2중 for문: 약 100,000* 100,000 = 약 100억

3. 1억 기준 약 1초 -> 100억 100초

 

🚨 시간 초과 실패

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        
        for(int i=0; i<weights.length; i++){
            for(int j=i+1; j<weights.length; j++){
                if(weights[i]==weights[j]){
                    answer++;
                    continue;
                }
                if((2*weights[i]==3*weights[j]) || (3*weights[i]==2*weights[j])){
                    answer++;
                    continue;
                }
                if((2*weights[i]==4*weights[j]) || (4*weights[i]==2*weights[j])){
                    answer++;
                    continue;
                }
                if((3*weights[i]==4*weights[j]) || (4*weights[i]==3*weights[j])){
                    answer++;
                    continue;
                }
            }
        }
        
        return answer;
    }
}
 
 

 

🚨 정렬을 통해 조건을 줄였지만, 시간 초과 실패

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.Arrays;
 
class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        
        Arrays.sort(weights);
        
        for(int i=0; i<weights.length; i++){
            for(int j=i+1; j<weights.length; j++){
                if(weights[i]==weights[j]){
                    answer++;
                    continue;
                }
                if((3*weights[i]==2*weights[j])){
                    answer++;
                    continue;
                }
                if((4*weights[i]==2*weights[j])){
                    answer++;
                    continue;
                }
                if((4*weights[i]==3*weights[j])){
                    answer++;
                    continue;
                }
            }
        }
        
        return answer;
    }
}
 
 

 

🚨 정렬을 통해 조건을 줄이기 + 탐색 범위 좁히기, 시간 초과 실패

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.Arrays;
 
class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        
        Arrays.sort(weights);
        
        for(int i=0; i<weights.length-1; i++){
            for(int j=i+1; j<weights.length; j++){
                if(2*weights[i]<weights[j]){
                    break;
                }
                if(weights[i]==weights[j]){
                    answer++;
                    continue;
                }
                if((3*weights[i]==2*weights[j])){
                    answer++;
                    continue;
                }
                if((4*weights[i]==2*weights[j])){
                    answer++;
                    continue;
                }
                if((4*weights[i]==3*weights[j])){
                    answer++;
                    continue;
                }
            }
        }
        
        return answer;
    }
}
 
 

 

 

😮 찾아본 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.Arrays;
import java.util.Map;
import java.util.HashMap;
 
class Solution {
    
    public long solution(int[] weights) {
        long answer = 0;
 
        Map<Double, Integer> map = new HashMap<>();
 
        Arrays.sort(weights);
        
        for(int weight : weights) {
            double sameWeight = weight*1.0;
            double twoThirdWeight = (weight*2.0)/3.0;
            double halfWeight = (weight*1.0)/2.0;
            double threeQuaters = (weight*3.0)/4.0;
            if(map.containsKey(sameWeight)) answer += map.get(sameWeight);
            if(map.containsKey(twoThirdWeight)) answer += map.get(twoThirdWeight);
            if(map.containsKey(halfWeight)) answer += map.get(halfWeight);
            if(map.containsKey(threeQuaters)) answer += map.get(threeQuaters);
            map.put((weight*1.0), map.getOrDefault((weight*1.0), 0)+1);
        }
 
        return answer;
 
    }
}
 
 

1. Arrays.sort(weights)

    - weights 오름차순 정렬

2. double sameWeight, twoThirdWeight, halfWeight, threeQuaters

    - weight가 오름차순 정렬되었으므로, 앞의 값과 비교하는 for문은 현재 weight보다 작은 특정 비율을 갖고 있는지만 확인하면 됨

3. map.put((weight*1.0), map.getOrDefault((weight*1.0), 0)+1)

    - weight값을 map에 저장하되, 중복이 제거되므로 이를 해결하기 위해 value 활용

    - 마지막에 위치시켜 자기자신과 비교한 값이 검사되지 않도록 함

        - 만일 맨 위로 위치시킬 경우, 자기 자신과 sameWeight로 비교된 부분을 제거하기 위해 weights.length를 차감해야 함

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    
    public long solution(int[] weights) {
        long answer = 0;
        
        int[] weightCount = new int[1001];
 
        for(int weight : weights){
            weightCount[weight]++;
        }
        
        for(int weight=100; weight<=1000; weight++){
            long count = weightCount[weight];
            
            if(count==0){
                continue;
            }
            
            answer += count * (count-1/ 2;
            // 동일한 값이 2개 이상일 경우
            
            if (weight * 3 % 2 == 0 && weight * 3 / 2 <= 1000) {
                answer += count * weightCount[weight * 3 / 2];
                // weight: 임의의 수 = 2 : 3
            }
            
           if (weight * 4 % 2 == 0 && weight * 4 / 2 <= 1000) {
                answer += count * weightCount[weight * 4 / 2];
               // weight: 임의의 수 = 2 : 4
            }
 
            if (weight * 4 % 3 == 0 && weight * 4 / 3 <= 1000) {
                answer += count * weightCount[weight * 4 / 3];
                // weight: 임의의 수 = 3 : 4
            }
        }
        
        return answer;
 
    }
}
 
 

1. int[] weightCount = new int[1001]

    - weight를 index로 사용하고 count를 value로 사용

2. long count = weightCount[weight]

    - count 자체를 int 범위이지만, 동일한 값의 개수를 구하기 위한 공식에서 int * int가 int의 범위를 넘어 long으로 선언

    - 또는 count간의 곱에서 casting을 할 수도 있음

        - 예: 100이 100,000개 있을 때, answer = 100,000* 99,999 > int값의 범위

3. if (weight * 3 % 2 == 0 && weight * 3 / 2 <= 1000)

    - weight * 3 % 2 == 0: weight보다 (3/2)배 더 크지만,

    - weight * 3 / 2 <= 1000: arrayIndexOutOfBoundsException 방지

 

 

 

🔗 소스 코드
GitHub

 

📚 참고 자료

 

[Java] 시소 짝꿍 - Lv2 프로그래머스

https://school.programmers.co.kr/learn/courses/30/lessons/152996 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞

mag1c.tistory.com

 

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

Language: Java

 

🚨 시간 초과 실패

- Brute Force로 시도했지만, 두 번째 반복문에서 크기를 줄였지만 시간 초과

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        for(int i=0; i<numbers.length; i++){
            answer[i] = -1;
 
            for(int j=i+1; j<numbers.length; j++){                
                if(numbers[i]<numbers[j]){
                    answer[i] = numbers[j];
                    break;
                }
            }
        }
        return answer;
    }
}
 
 

 

😮 찾아본 풀이

Stack 활용

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.Stack;
 
class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        
        Stack<Integer> reverseNumbers = new Stack<>();
        
        for(int i = numbers.length-1; i>=0; i--){
            while(!reverseNumbers.isEmpty()){
                if(reverseNumbers.peek()>numbers[i]){
                    answer[i] = reverseNumbers.peek();
                    break;
                }
                if(reverseNumbers.peek()<=numbers[i]){
                    reverseNumbers.pop();
                }
            }
 
            if(reverseNumbers.isEmpty()){
                answer[i] = -1;
            }
            
            reverseNumbers.push(numbers[i]);
 
        }
        
        return answer;
    }
}
 
 

1. Stack<Integer> reverseNumbers

    - 큰 숫자를 담고 있을 Stack 선언

2. while() + if()

    - reverseNumbers가 비어있지 않을 동안,

    - reverseNumbers의 마지막 수가 numbers의 배열값보다 크다면 answer에 뒤에서 큰 값으로 입력

    - 만일, 큰 값이 없을 경우에는 reverseNumbers에서 제거

3. if(reverseNumbers.isEmpty())

    - 만일 큰 값이 없어 reverseNumbers이 비게 될 경우, -1 반환

4. reverseNumbers.push(numbers[i])

    - ⭐ 위치 중요

    -  마지막에 값을 reverseNumbers에 입력하여 reverseNumbers와 numbers가 index를 달리하여 움직이게 할 수 있음

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.Arrays;
import java.util.Stack;
 
class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
 
        Stack<Integer> indexNumber = new Stack<>();
 
        Arrays.fill(answer, -1);
 
        for (int i=0; i < numbers.length; i++) {
            while (!indexNumber.isEmpty() && (numbers[indexNumber.peek()] < numbers[i])) {
                answer[indexNumber.pop()] = numbers[i];                    
            }
            indexNumber.push(i);
        }
        return answer;
    }
}
 
 

1. Stack<Integer> indexNumber

    - index를 담아줄 Stack 선언

2. Arrays.fill(answer, -1)

    - 기본값으로 -1 대입

3. while 반복문

    - ⭐ &&을 함께 주지 않을 경우, 무한 Loop에 빠질 수 있음에 유의

    - numbers[indexNumber.peek()] < numbers[i])

         - indexNumber에 위치한 numbers 값보다 다음 값(i번째 numbers 값)이 클 경우에만 answer의indexNumber 위치에 뒤에 있는 큰 수 대입

        - 만일 해당하는 값이 없을 경우, 기본값 -1로 출력 예정(indexNumber에는 해당 값이 남아 있게 됨)

4. indexNumber.push(i)

    - ⭐ 앞 뒤 값의 비교를 위해서 push를 가장 마지막에 위치

    - (push를 while 반복문보다 앞에 위치시킬 경우, numbers[indexNumber.peek()] < numbers[i])  이 부분에서 계속 동일한 값을 비교하면서 최종 결과가 -1이 반환됨)

 

 

 

🔗 소스 코드
GitHub

 

📚 참고 자료

 

프로그래머스 Lv.2 뒤에 있는 큰 수 찾기-JAVA

문제 정수로 이루어진 배열 numbers가 있습니다. 배열의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷큰수라고 합니다. 정수 배열 numbers가 매개변

jaewoo2233.tistory.com

 

 

[프로그래머스] - 뒤에 있는 큰 수 찾기(LV2) java

https://school.programmers.co.kr/learn/courses/30/lessons/154539 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞

leeprogramer.tistory.com

 

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

Language: Java

 

🚨 곡갱이 순서 부여 로직 생성 실패

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.Arrays;
 
class Solution {
    static int[] mineralsToInt;
    static int[] sumWeight;
    public int solution(int[] picks, String[] minerals) {
        // minerals: 5
        // diamond count sort
        // picks 0 1 2
        int answer = 0;
        
        calcWeightMinerals(minerals);
        calcSumWeight(mineralsToInt);
        createOrderPickUse(picks);
        Arrays.sort(sumWeight);
                
        return answer;
    }
    public static int[] calcWeightMinerals(String[] minerals){
        mineralsToInt = new int[minerals.length];
        for(int i=0; i<minerals.length; i++){
            switch(minerals[i]){
                case "diamond": mineralsToInt[i]=3break;
                case "iron": mineralsToInt[i]=2break;
                case "stone": mineralsToInt[i]=1break
            }
        }
        return mineralsToInt;
    }
    public static int[] calcSumWeight(int[] mineralsToInt){
        sumWeight = new int[(mineralsToInt.length/5)+1];
        int sumSubWeight = 0;
        int idx=0;
        for(int i=0; i<mineralsToInt.length; i++){
            sumSubWeight += mineralsToInt[i];
            if(i%5==4 || i==(mineralsToInt.length-1)){
                sumWeight[idx++= sumSubWeight;
                sumSubWeight = 0;
            }
        }
        return sumWeight;
    }
}
 
 

 

😮 찾아본 풀이

⭐이중 배열과 포인터 활용

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.*;
 
class Solution {
    public int solution(int[] picks, String[] minerals) {
        int answer = 0;
        int countPicks = picks[0+ picks[1+ picks[2];
        int[][] mineralFatigueTable = new int[minerals.length / 5 + 1][3];
        
        for(int i = 0; i < minerals.length && countPicks > 0; i++) {
            switch(minerals[i])
            {
                case "diamond":
                    mineralFatigueTable[i / 5][0+= 1;
                    mineralFatigueTable[i / 5][1+= 5;
                    mineralFatigueTable[i / 5][2+= 25;
                    break;
                case "iron":
                    mineralFatigueTable[i / 5][0+= 1;
                    mineralFatigueTable[i / 5][1+= 1;
                    mineralFatigueTable[i / 5][2+= 5;
                    break;
                case "stone":
                    mineralFatigueTable[i / 5][0+= 1;
                    mineralFatigueTable[i / 5][1+= 1;
                    mineralFatigueTable[i / 5][2+= 1;
            }
            
            if(i % 5 == 4) countPicks--;            
            
        }
        
        Arrays.sort(mineralFatigueTable, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[2< o2[2]) 
                    return 1;
                else 
                    return -1;
            }
        });
        
        for(int i = 0, pickIndx = 0; i < mineralFatigueTable.length; i++) {
            while(pickIndx < 3 && picks[pickIndx] == 0) pickIndx++;
            if(pickIndx == 3break;
            picks[pickIndx]--;
            answer += mineralFatigueTable[i][pickIndx];
        }
        
        return answer;
    }
}
 
 

 

1. mineralFatigueTable

    - [광물을 5개씩 묶었을 때 몇 번째 묶음인지,곡괭이 별 피로도]

2. Arrays.sort(mineralFatigueTable)

    - compare

        - 피로도 계산이 가장 큰 돌을 사용했을 때 기준으로 5개 광물 캐기 피로도 묶음을 내림차순 정렬

    - pickIdx로 mineralFatigueTable에서 피로도 선택

 

 

 

🔗 소스 코드
GitHub

 

📚 참고 자료

 

프로그래머스 광물 캐기 java

문제링크문제 조건을 읽어보면, 어차피 곡괭이 하나 들었으면 마인크래프트마냥 앞에꺼 다섯개 무조건 캐야한다.1-1 마인크래프트랑은 다르게 앞에 놓여진 블록들을 알때, 어떻게 캐야 제일 효

velog.io

 

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

Language: Java

 

🚨 시간초과

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = {01000000};
        
        int i, j;
        for(i=0; i<sequence.length; i++){
            int sum=0;
            for(j=i; j<sequence.length; j++){
                if(sum==k){
                    if((j-i)<(answer[1]-answer[0])){
                        answer[0= i;
                        answer[1= j;
                        break;                        
                    }
                }
                if(sum<k){
                    sum += sequence[j];                    
                }
            }
        }
        return answer;
    }
}
 
 

이중 for문으로 인한 시간복잡도 향상(O(n))

 

😮 찾아본 풀이

⭐ 투 포인터

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    int[] answer = {0, 1_000_000};
    
    public int[] solution(int[] sequence, int k) {
        
        int left = 0;
        int right = 0;
        
        int sum=0;
        while(right < sequence.length) {
            sum += sequence[right++];
            while(sum>k){
                sum -= sequence[left++];
            }
            
            if(sum==k){
                changeArr(left, right-1);
            }
        }
        return answer;
    }
    
    private void changeArr(int left, int right){
        if(right-left<answer[1]-answer[0]){
            answer[0= left;
            answer[1= right;
        }
    }
}
 
 

1. while(right < sequence.length)

    - sequence 길이 전까지 반복

2. sum += sequence[right++]

    - right pointer를 키워가며 sum에 덧셈

3. while(sum>k)

    - 단, sum이 k보다 커질 경우, left pointer를 키워가며 sum 뺄셈

4. if(sum==k)

    - changeArr(left, right-1)

        - 길이가 더 짧은 경우에만 answer에 입력하는 함수 작성

        - 단, right pointer의 경우 후위연산자로 1커졌으므로 조정 필요

        - 먼저 발견된 pointer를 출력하기 위해 if 조건문에 동등 연산자 제외

 

 

 

🔗 소스 코드
GitHub

 

📚 참고 자료

 

[Java] 연속된 부분 수열의 합 - Lv2 프로그래머스

https://school.programmers.co.kr/learn/courses/30/lessons/178870 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞

mag1c.tistory.com