Sangil's blog

https://github.com/ChoiSangIl Admin

프로그래머스 코딩 테스트 탑 JAVA(자바) DEV / ALGORITHM

2020-07-25 posted by sang12


이 문제가..왜 스택분류에 있는지 잘 모르겠다.. 스택으로 푸신분들도 존재. 이중 FOR문을 이용하면 간단히 해결 할 수 있다.

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42588

class Solution {
    public int[] solution(int[] heights) {
        int[] answer = new int[heights.length];
		
		for(int i=0; i<heights.length; i++) {
			if(i==0) {
				answer[i] = 0;
			}else {
				for(int j=i-1; j>=0; j--) {
					if(heights[i] < heights[j]) {
						answer[i] = j+1;
						break;
					}
					if(j==0) {
						answer[i]= 0;
					}
				}	
			}
		}
        
        return answer;
    }
}

REPLY

프로그래머스 코딩테스트 다리를 지나는 트럭 자바(JAVA) DEV / ALGORITHM

2020-07-25 posted by sang12


각각의 무게를 가진 트럭이 K만큼의 길이를 가지고있고 N만큼의 무게를 견딜 수 있는 다리를 건너는데 걸리는 시간을 구하는 문제입니다. 트럭은 1초마다 1만큼 이동 할 수 있습니다. (문제: https://programmers.co.kr/learn/courses/30/lessons/42583?language=java). 이미 문제 유형 자체가 스택이나 큐를 이용하는 문제여서 스포를당해버린...

링크드리스트를 이용해서 trucks과 bridge 객체를 생성했습니다. 그리고 다리의 길이만큼 이동하기위해 int배열을 이용해서 0번째에는 무게를 1번째에는 이동 할 수 있는 다리의 길이를 넣어줬습니다. 그리고 currentBridgeWeight는 다리위에 올라와있는 트럭의 무게이고, 이를 이용해서 다리에 올라 갈 수 있는 무게만 올가가게 해줬습니다. 그리고 트럭과 다리의 큐가 비어 있으면! 끝..!

import java.util.LinkedList;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
       int currentBridgeWeigh = 0;
		LinkedList<Integer> trucks = new LinkedList<Integer>(); 
		LinkedList<int[]> bridge = new LinkedList<int[]>(); 
		
		for(int truck : truck_weights) {
			trucks.add(truck);
		}
		
		int result = 1;
		
		while(!trucks.isEmpty() || !bridge.isEmpty()) {
			for(int j=0; j<bridge.size(); j++){
				int[] tructCheck = bridge.get(j);
				if(tructCheck[1] == 0) {
					bridge.poll();
					currentBridgeWeigh = currentBridgeWeigh-tructCheck[0];
				}
			}
			
			if(!trucks.isEmpty()) {
				int[] truck = {trucks.peek(), bridge_length};
				if(currentBridgeWeigh + truck[0]<= weight) {
					bridge.add(truck);
					currentBridgeWeigh = currentBridgeWeigh+truck[0];
					trucks.poll();
				}
			}
			
			for(int j=0; j<bridge.size(); j++){
				int[] tructCheck = bridge.get(j);
				tructCheck[1]--;
				bridge.set(j, tructCheck);
			}
			
			if(trucks.isEmpty() && bridge.isEmpty()) {
				break;
			}
			result++;
		}
		
		return result;
		
    }
}

하고 나서 다른사람들의 소스를 참고하니, 제가 int배열로 처리했던 부분 0번쨰에는 무게, 1에는 갈 수 있는거리를 Class Truck으로 만들어서 처리한 부분이 인상적이였습니다. 

REPLY

프로그래머스 코딩테스트연습 베스트앨범 자바(JAVA) DEV / ALGORITHM

2020-07-19 posted by sang12


프로그래머스 해시 연습문제 베스트 앨범 해답입니다. 푸는데 엄청 애 먹었네요 ㅜㅜ

문제는, 노래 장르와 노래 재생 횟수가 배열로 주어지는데, 이를 이용해서 베스트 앨범을 만드는 문제입니다.

1. 장르 재생수가 가장 많은 순서로 수록한다.

2. 장르내에서 재생이 가장 많이된 순서로 수록한다.

3. 장르내엣 재생횟수가 같으면 고유번호가 낮은 노래를 먼저 수록한다.

(https://programmers.co.kr/learn/courses/30/lessons/42579)

아래와 같이 장르별로 재생수를 카운팅한 HashMap을만들었고, 고유 id별 재생수(재생수로 정렬) LinkedHashMap과 고유 id의 장르를 가지고 있는 HashMap을 이용하여 문제를 해결했습니다. 

{pop=3100, classic=1450} <-- 장르별 재생수
{4=2500, 3=800, 1=600, 0=500, 2=150} <-- 재생수로 정렬된 고유 ID
{0=classic, 1=pop, 2=classic, 3=classic, 4=pop} <-- 고유 ID별 장르타입

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
	Map<String, Integer> group = new HashMap<String, Integer>();
	for(int i=0; i<genres.length;i++) {
		if(group.containsKey(genres[i])) {
			group.put(genres[i], group.get(genres[i])+plays[i]);
		}else {
			group.put(genres[i], plays[i]);
		}
	}
		
	Map<Integer, Integer> idAndPlaysMap = new HashMap<Integer, Integer>();
	Map<Integer, Integer> idAndPlaysLinkedMap = new LinkedHashMap<Integer, Integer>();
        Map<Integer, String> idAndGenres = new HashMap<Integer, String>();
        ArrayList<Integer> resultList = new ArrayList<Integer>();
        
        for(int i=0; i<genres.length;i++) {
    		idAndPlaysMap.put(i, plays[i]);
    		idAndGenres.put(i, genres[i]);
    	}
        
        List<String> keySetList = new ArrayList<>(group.keySet());
        Collections.sort(keySetList, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return group.get(o2).compareTo(group.get(o1));
            }
        });
        
        List<Integer> keySetList2 = new ArrayList<>(idAndPlaysMap.keySet());
        Collections.sort(keySetList2, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return idAndPlaysMap.get(o2).compareTo(idAndPlaysMap.get(o1));
            }
        });
        
        for(Integer key : keySetList2) {
        	idAndPlaysLinkedMap.put(key, idAndPlaysMap.get(key));
        }
        
        for(String key : keySetList) {
        	Iterator<Integer> keys = idAndPlaysLinkedMap.keySet().iterator();
        	int indexId = 0;
        	while ( keys.hasNext() ) {
        		Integer playKey = keys.next();
        		String genresName = idAndGenres.get(playKey);
                
        		if(key.equals(genresName)) {
                    if(indexId==2) {break;}
        			resultList.add(playKey);
        			indexId++;
        		}
        	}   
        }
        
        int[] answer = new int[resultList.size()];
        
        for(int i = 0; i < resultList.size(); i++){
            answer[i] = resultList.get(i);
        }
        
        return answer; 
    }
}

흐.. 부족함을 많이느끼네요 한 4시간은 본거같은데.. 다른분들의 좋은 소스를 참고해서 더 공부해봐야겠어요 :). 아 참고로, 스트링을 ==로 비교하면 프로그래머스 정답나오는데 약간 오류가있더라구요 그래서 equlas로 변경했답니다.. 한참 삽질을...

REPLY