[Algorithm] 6월 11일 알고리즘 연습 (프로그래머스 LEVEL2) - 에이젠

 

Lv. 2 주식가격 - 실패

 

실패한 풀이 : 테스트케이스만 통과... 방법 자체는 틀린 것 같지 않아서 다시 해결해보아야겠다

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Queue<Integer> tempQ = new LinkedList<Integer>();
        Stack<Integer> stack = new Stack<Integer>();
        int pre = 0;
        
        for(int i = 0; i < prices.length; i++){
            if(pre <=prices[i]){//감소하지 않았다면 스택에 그대로 추가.
                stack.push(prices[i]);
                //이전 가격 갱신
                pre = prices[i];
                continue;
            }else{
                //감소한다면 그 값보다 큰값은 큐로 빼냄
                while(stack.peek() >  prices[i]){
                    int poped = stack.pop();
                    
                    tempQ.add(0);
                }
                tempQ.add(prices[i]);
                //모두 빼낸 후 빼낸만큼 0을 쌓기
                while(tempQ.size() > 0){
                    //0과 마지막 숫자.
                    int input = tempQ.poll();
                    stack.push(input);
                    System.out.println(input);
                }
                pre = stack.peek();
            }
            
        }
        int count = 0;
        for(int i = prices.length-1 ; i >=0 ; i--){
            //System.out.println(stack.peek());
            if(stack.pop() == 0){
                answer[i] = 1;
            }else{
                answer[i] = count;
            }
            count++;
        }
        
        return answer;
    }
}

참고한 풀이

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;
    }

}

 

https://girawhale.tistory.com/7

[프로그래머스] 주식가격(Stack) - JAVA

 

Lv. 2 구명보트 - 성공

내풀이(1) : 정확도 20%

바로 앞뒤에 있는 인덱스의 몸무게 조합만 생각한 것이 실수.

40,50,150,160 limit 200 인 경우 정렬을 하였어도 40,50 | 150 | 160이므로 3이 나오며 정렬한 형태가 아닌

40, 160| 50,150 으로 탑승한다면 2가 나오는 경우가 생김. -> 투포인터로 간단히 해결

 

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        
        //정렬 먼저함
        ArrayList<Integer> stayLine = new ArrayList<Integer>();
        for(int i = 0 ; i < people.length; i++){
            stayLine.add(people[i]);
        }//오름차.
        Collections.sort(stayLine);
        int count = 0 ;
        while(stayLine.size() > 0){
            if(stayLine.size() == 1){
                count++;
                break;
            }
            int first = stayLine.get(0);
            int second = stayLine.get(1);
            
            if(first + second <= limit){
                stayLine.remove(0);
                stayLine.remove(1);
                count++;
            }else{
                stayLine.remove(0);
                count++;
            }
        }
        answer = count;
        return answer;
    }
}

내풀이(2) : 정확도 100%

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        
        int[] person = people;
        
        Arrays.sort(person);
        int count = 0 ;
        int left = 0;
        int right = person.length-1;
        while(left <= right){
            if(person[left] + person[right] <= limit ){
                left++;
                right--;
                count++;
            }else{
                right--;
                count++;
            }
        }
        answer = count;
        return answer;
    }
}

 

Lv. 2 교점에 별 만들기- 실패

 

class Solution {
     ArrayList<Integer> arr = new ArrayList<Integer>();
    int maxX = Integer.MIN_VALUE;
    int maxY = Integer.MIN_VALUE;
    int minX = Integer.MAX_VALUE;
    int minY = Integer.MAX_VALUE;
    public String[] solution(int[][] line) {
        for(int i = 0 ; i < line.length ; i++){
            for(int j = i+1 ; j < line.length; j++){
                isCrossed(line[i], line[j]);
            }
        }
        //최대 별 개수 
        int width = maxX - minX +1;
        int height = maxY - minY +1;
        String[] answer = new String[height];
        
        for(int i = 0; i < height ; i++){
            String a = "";
            for(int j = 0 ; j < width ; j++){
                a = a +".";
            }
            answer[i] = a;
        }
         for(int i = 0 ; i < arr.size()-1; i= i+2){
             
            //좌표 조정 필요 주의
            int xx = arr.get(i) - minX ;
            int yy = arr.get(i+1) - minY;
             char[] chList ;
             System.out.println(xx);
             System.out.println(yy);
             System.out.println(" ");
//              if(xx == 0){
//                  chList = answer[xx].toCharArray();
//              }else{
//                  chList = answer[xx].toCharArray();
//              }
            
            // chList[yy] = '*';
            // String temp = "";
            // for(char s : chList){
            //     temp = temp + s;
            // }
            // answer[xx] = temp;
           
        }
       
        return answer;
    }
    
    public boolean isCrossed(int[] first, int[] second){
        int A = first[0];
        int B = first[1];
        int E = first[2];
        
        int C = second[0];
        int D = second[1];
        int F = second[2];
        
        if(A*D - B*C != 0){
            int x = (B*F - E*D) / (A*D - B*C);
            int y = (E*C - A*F) / (A*D - B*C);
            minX = Math.min(minX, x);
            minY = Math.min(minY, y);
            maxX = Math.max(maxX, x);
            maxY = Math.max(maxY, y);
            arr.add(x);
            arr.add(y);
            return true;
        }else{
            return false;
        }
        
        
    }
}

참고한 풀이

public class Solution {
 
    public String[] solution(int[][] line) {
        String[] answer = {};
        List<long[]> list = new ArrayList<>();
        long minX = Long.MAX_VALUE;
        long maxX = Long.MIN_VALUE;
        long minY = Long.MAX_VALUE;
        long maxY = Long.MIN_VALUE;

        for(int i = 0; i < line.length; i++){
            long a = line[i][0];
            long b = line[i][1];
            long e = line[i][2];

            for(int j = i+1; j < line.length; j++){
                long c = line[j][0];
                long d = line[j][1];
                long f = line[j][2];

                long xUp = b*f - e*d;
                long xDown = a*d - b*c;

                long yUp = e*c - a*f;
                long yDown = a*d - b*c;

                if(xDown != 0){
                    double x = xUp / (double)xDown;
                    double y = yUp / (double)yDown;

                    if(x == Math.ceil(x) && y == Math.ceil(y)){
                        list.add(new long[]{(long)x, (long)y});
                        minX = Math.min(minX, (long) x);
                        maxX = Math.max(maxX, (long) x);
                        minY = Math.min(minY, (long) y);
                        maxY = Math.max(maxY, (long) y);
                    }
                }


            }
        }

        boolean[][] answerTemp = new boolean[(int) (maxY- minY +1)][(int) (maxX - minX + 1)];

        for (long[] ints : list) {
            int x = (int) (ints[0] - minX);
            int y = (int) (ints[1] - maxY);

            answerTemp[Math.abs(y)][Math.abs(x)] = true;
        }

        answer = new String[answerTemp.length];

        int i = 0;
        for (boolean[] bs : answerTemp) {
            StringBuilder sb = new StringBuilder();
            for (boolean b : bs) {
                if(b){
                    sb.append("*");
                }else{
                    sb.append(".");
                }
            }
            answer[i] = sb.toString();
            i++;
        }

        return answer;
    }
}

https://tmdrl5779.tistory.com/247

[프로그래머스] 교점에 별 만들기(Java 자바)

x, y 값이 바뀌기 때문에 Y = maxY - y, X = x - minX와 같이 계산

 

Lv. 2 전력망을 둘로 나누기 - 실패

참고한 풀이

import java.util.LinkedList;
import java.util.Queue;
class Solution {
    static int[][] arr;
    public int solution(int n, int[][] wires) {
        int answer = n;
        arr= new int[n+1][n+1];
        
        //1. 인접행렬에 input
        for(int i=0; i<wires.length; i++){
            arr[wires[i][0]][wires[i][1]]=1;
            arr[wires[i][1]][wires[i][0]]=1;
        }
        
        //2. 선을 하나씩 끊어보며 순회
        int a, b;
        for(int i=0; i<wires.length; i++){
            a= wires[i][0];
            b= wires[i][1];
            
            //선을 하나 끊고
            arr[a][b]=0;
            arr[b][a]=0;
            
            //bfs
            answer= Math.min(answer, bfs(n, a));
            
            //선 다시 복구
            arr[a][b]=1;
            arr[b][a]=1;
        }
        
        return answer;
    }
    
    public int bfs(int n, int start){
        int[] visit= new int[n+1];
        int cnt=1;
        
        Queue<Integer> queue= new LinkedList<>();
        queue.offer(start);
        
        while(!queue.isEmpty()){
            int point= queue.poll();
            visit[point]= 1;
            
            for(int i=1; i<=n; i++){ //point와 연결된 애들 중에 방문한적 없는 노드 전부 큐에 넣기
                if(visit[i]==1) continue;
                if(arr[point][i]==1) {
                    queue.offer(i);
                    cnt++;
                }
            }
        }
        return (int)Math.abs(n-2*cnt); //cnt-(n-cnt);
    }//bfs
}

https://arinnh.tistory.com/84

[프로그래머스]level 2: 전력망 둘로 나누기_Java(위클리 9주차)

 

Lv. 2 모음사전 - 실패

 

class Solution {
	public int solution(String word) {
		String str = "AEIOU";
		int[] x = {781,156,31,6,1};
		int index,result=word.length();
		for(int i=0;i<word.length();i++){
			index = str.indexOf(word.charAt(i));
			result+=x[i]*index;
		}
		return result;
	}
}

https://bangu4.tistory.com/241

[위클리챌린지] 5주 - 모음사전 - Java코드

 

Lv. 2 이진 변환 반복하기 - 성공

문자열의 길이를 변환하는 것인데 문자열을 그대로 변환했다가 실패함. Long의 범위마저 넘어가서 발생한 에러

내풀이

// s를 바로 char[]에 넣고 일일이 빼는 건 비효율적
// s.length 와 s.replace("0", "") 사용후 s.length와 비교해서 0의 개수 출력
//0 제거 후 s.length 길이를 2진법으로 변환
// 반복
class Solution {
    public int[] solution(String s) {
        int[] answer = new int[2];
        
        String str = s;
        long count = 0;
        long zeroKill = 0;
        while(!str.equals("1")){
            count++;
            long before  = str.length(); //처음 길이
            str = str.replace("0","");//0 제거
            long after = str.length();
            long zeroNumber = before- after;//제거한 0개수
            zeroKill = zeroKill + zeroNumber;
            str = toBinary(after);
        }
        answer[0]  = (int)count;
        answer[1] = (int)zeroKill;
        
        return answer;
    }
    
    public String toBinary(long st){
        StringBuilder sb = new StringBuilder();
        long num = st; //Long.parseLong(st);
        while(num >0){
            long remain = num%2;
            num = num/2;
            sb.append(remain);
        }
        String result = sb.reverse().toString();
        
        return result;
    
    }
    
}