[99club/TIL] 3주차 - 금요일 TIL(Today I Learned)

안녕하세요. delay100 입니다.

오늘은 어제 못 풀었던 정기 세션 2문제와 금요일에 주어진 문제를 풀어볼겁니다!

총 3문제를 해결해볼거에요!

---

미들러 문제

---

목요일 문제

1번. 기능개발

https://school.programmers.co.kr/learn/courses/30/lessons/42586

프로그래머스

import java.io.*;
import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int[] how = new int[progresses.length];
        
        // n일 걸리는 값 구하기
        for(int i=0; i<progresses.length; i++) {
            int howmany = (100 - progresses[i])/speeds[i];
            int etc = (100 - progresses[i])%speeds[i];
            how[i] = etc == 0 ? howmany : (howmany + 1); 
        }
        
//         for(int i=0; i<how.length; i++) {
//             System.out.print(how[i]+ " ");
//         }
        int x = how[0];
        int cnt = 1;
        ArrayList<Integer> al = new ArrayList<Integer>();
        for(int i=1; i<progresses.length; i++) {
             if((x < how[i])) { // 뒤에있는 기능이 앞에있는 기능보다 늦게 끝나는 경우
                al.add(cnt); // 이전까지 개수를 추가
                cnt = 0;
                x = how[i]; // 비교값을 현재 값(늦게 끝나는 값)으로 변경
            }
            if((i == (progresses.length-1))) { // 마지막 index에 도달한 경우
                al.add(cnt+1);
                
            }
           
            cnt++; // 일 수 증가
        }
        
        int[] answer = new int[al.size()];
        for(int i=0; i<al.size(); i++) {
            answer[i] = al.get(i);
        }
        
        return answer;
    }
}

중간에 프린트문의 주석을 제거하고 실행하면 위와 같이 how 리스트가 출력됩니다.

how리스트는 0일을 완료하는데 며칠 걸리는지가 저장되어있는 배열입니다.

 

2번. 대충 만든 자판

https://school.programmers.co.kr/learn/courses/30/lessons/160586

프로그래머스

class Solution {
    public int[] solution(String[] keymap, String[] targets) {
        int[] answer = new int[targets.length];
        int[] alpha = new int[26]; // 대문자 알파벳 리스트
        
        for(int i=0; i<keymap.length; i++) {
            int keymapInnerLength = keymap[i].length();
            int cnt = 1;
            for(int j=0; j<keymapInnerLength; j++) {
                int a = keymap[i].charAt(j) - 'A';
                if(alpha[a]==0) {
                    alpha[a] = cnt;
                } else { // 음수인 경우는 x, 무조건 양수
                    alpha[a] = alpha[a] > cnt ? cnt : alpha[a];
                }
                cnt++;
            }
        }
        
        for(int i=0; i<targets.length; i++) {
            int num = 0;
            int targetsInnerLength = targets[i].length();
            boolean isFalse = false;    
            
            for(int j=0; j<targetsInnerLength; j++) {
                // 들어있는 값이 0인 경우 문자가 1번도 나오지 않은 경우이므로 -1 저장
                if(alpha[targets[i].charAt(j) - 'A'] == 0) {
                    isFalse = true;
                    break;
                }
                num += alpha[targets[i].charAt(j) - 'A'];
            }
            answer[i] = isFalse ? -1 : num;
        }
        
        
        return answer;
    }
}

---

금요일 문제

1번. 뒤에 있는 큰 수 찾기 

https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

1. 실패 코드 - 2중 for문 이용

문제가 1,000,000 x 1,000,000 = 10억이라 무조건 시간초과가 날 수 밖에 없는 코드입니다.

그렇지만.. 먼저 떠오른 코드였기 때문에 한번 제출해보고 싶었습니다...

class Solution {
    public int[] solution(int[] numbers) {
        int numbersLength = numbers.length;
        int[] answer = new int[numbersLength];
        
        for(int i=0; i<numbersLength-1; i++) {
            boolean isTrue = false;
            for(int j=i+1; j<numbersLength; j++) {
                if(numbers[i] < numbers[j]) {
                    answer[i] = numbers[j];
                    isTrue = true;
                    break;
                }
            }
            if(!isTrue) {
                answer[i] = -1;
            }
        }
        
        answer[numbersLength-1] = -1;
        
        return answer;
    }
}

2중 for문을 이용하면 82.6점이 나옵니다.

 

2. 성공 코드 - stack 이용

핵심은 Stack을 이용하여 해결하였습니다.

먼저, 가장 마지막 원소는 더 큰 수가 뒤에 올 수 없으므로 무조건 -1입니다.

answer[numbersLength-1] = -1;

그리고 스택을 선언해줍니다.

Stack<Integer> stk = new Stack<Integer>();

stk.push(numbers[numbersLength-1]);

스택에는 numbers 리스트의 가장 마지막 원소를 넣어주었습니다.

그리고 배열을 뒤에서부터 순환하면서, 스택에 저장되어있는 값과 비교하며 현재 값보다 더 큰 수를 찾아주었습니다.

자세한 설명은 코드에 적어두었습니다.

코드에 있는 출력문(System.out.println)의 주석을 제거하면 위와 같이 변화하는 스택의 값을 볼 수 있습니다.

import java.io.*;
import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int numbersLength = numbers.length;
        int[] answer = new int[numbersLength];
        Stack<Integer> stk = new Stack<Integer>();
        
        answer[numbersLength-1] = -1;
        stk.push(numbers[numbersLength-1]);
        
        for(int i=numbersLength-2; i>=0; i--) { // 배열을 뒤에서 부터 순환
            if(stk.peek() <= numbers[i]) { // 스택에 들어있는 값 <= 현재 값 ---> 뒤에있는 큰 수 발견 못 한 상태
                stk.pop(); // 스택에 들어있는 값을 제거
                while(!stk.isEmpty()) { // 스택이 비어있지 않는 동안 반복
                    if(stk.peek() > numbers[i]) { // 스택에 들어있는 값 > 현재값이 된 경우 -> 뒤에있는 큰 수 발견한 것임
                        answer[i] = stk.peek(); // 스택에 들어있는 값을 정답으로 저장
                        stk.push(numbers[i]); // 스택에 현재 값 추가
                        break;
                    }
                    stk.pop(); // while문의 if문이 만족할 때까지 stk의 값을 제거해줌
                }
                if(stk.isEmpty()) { // 현재 도달한 값이 가장 뒤에있는 큰 값임
                    stk.push(numbers[i]); // 스택에 현재 값 추가
                    answer[i] = -1; // 현재 값보다 큰 값이 없으므로 -1 저장
                }
            } else { // 스택에 들어있는 값 > 현재 값 ---> 뒤에 있는 큰 수 발견
                answer[i] = stk.peek(); // 스택에 들어있는 값을 결과값으로 저장
                stk.push(numbers[i]); // 스택에 현재 값을 저장
            }
            
            // System.out.println("i= "+i+"/ stk.size()= "+stk.size());
            // for(int j=0; j<stk.size(); j++) {
            //     System.out.print(stk.get(j) + " ");
            // }
            // System.out.println();
        }
        
        return answer;
    }
}

 

 

---

+ 비기너 문제

 

목요일 문제

1번

https://school.programmers.co.kr/learn/courses/30/lessons/12903

프로그래머스

2번

https://school.programmers.co.kr/learn/courses/30/lessons/132267

프로그래머스

금요일 문제

2016년 (https://school.programmers.co.kr/learn/courses/30/lessons/12901)

프로그래머스

---

+ 챌린저 문제

목요일 문제

1번

https://school.programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스

2번

https://school.programmers.co.kr/learn/courses/30/lessons/152995

프로그래머스

금요일 문제

공 이동 시뮬레이션 (https://school.programmers.co.kr/learn/courses/30/lessons/87391)

프로그래머스

---

이해가 되지 않는 부분이 있으시면 댓글을 달아주세요!

최대한 빨리 답변 드리겠습니다.