공부공간

[JAVA] Programmers 위클리 챌린지 1~8주 풀이 본문

알고리즘/구현,시뮬

[JAVA] Programmers 위클리 챌린지 1~8주 풀이

개발자가될수있을까? 2021. 9. 30. 20:59

https://programmers.co.kr/learn/challenges

 

코딩테스트 연습

기초부터 차근차근, 직접 코드를 작성해 보세요.

programmers.co.kr


쉬는날을 맞아서 프로그래머스에서 진행하는 위클리챌린지를 풀어보았다.

이번 포스팅에서는 JAVA로 1-4주차 푼문제를 정리하려한다.

( + 2021.08.30 5주차 문제풀이 추가 )

(+ 2021.09.14 6,7주차 문제풀이 추가)

(+ 2021.09.30 8주차 문제풀이 추가)


1 주차.

https://programmers.co.kr/learn/courses/30/lessons/82612

 

코딩테스트 연습 - 1주차

새로 생긴 놀이기구는 인기가 매우 많아 줄이 끊이질 않습니다. 이 놀이기구의 원래 이용료는 price원 인데, 놀이기구를 N 번 째 이용한다면 원래 이용료의 N배를 받기로 하였습니다. 즉, 처음 이

programmers.co.kr


가볍게 1주차 문제부터 시작한다. 

놀이기구는 price의 가격을 가지고있는데 1,2, ... N 번 이용하면 누적이용횟수를 곱해야지 그 당시이용하는 금액이다.

간단하게 count번 이용한 값을 구해서 내가가진 money와 비교해주자.

 

class Solution {
    public long solution(int price, int money, int count) {
        long answer = 0;
        for(int i=1;i<=count;i++){
        	answer += (price*i);
        }
        return answer <= money ? 0 : answer-money ;
    }
}

 

2 주차.

https://programmers.co.kr/learn/courses/30/lessons/83201

 

코딩테스트 연습 - 2주차

[[100,90,98,88,65],[50,45,99,85,77],[47,88,95,80,67],[61,57,100,80,65],[24,90,94,75,65]] "FBABD" [[70,49,90],[68,50,38],[73,31,100]] "CFD"

programmers.co.kr


2주차문제는 배열문제이다. 즉 2차원 배열을 한 Col씩탐색하면서 

i==j인 값이 유일한 최고/최저 점인지 확인하고 해당된다면 평균을 구할때 값을 빼주면된다.

이러한 계산을 배열 사이즈만큼 반복하면 해결!

import java.util.ArrayList;

class Solution {
  	public static String solution(int[][] scores) {
        String answer = "";
        int size = scores.length;
        for(int i=0;i<size;i++) {
        	int me = scores[i][i];
        	boolean highest = true;
        	ArrayList<Integer> index = new ArrayList<>();
        	for(int j=0;j<size;j++) {
        		if(me < scores[j][i]) {highest = false;}
        		if(me==scores[j][i]) {index.add(j);}
        	}
        	if(highest && index.size()==1) {
        		//유일한 최고점 조건
        		int score =0;
        		for(int j=0;j<size;j++) {
        			if(j!=i) {score +=scores[j][i];}
        		}
        		answer += returnString(score/(size-1));
        		continue;
        	}
        	boolean lowest = true;
        	index.clear();
        	for(int j=0;j<size;j++) {
        		if(me > scores[j][i]) {lowest = false;}
        		if(me==scores[j][i]) {index.add(j);}
        	}
        	if(lowest && index.size()==1) {
        		//유일한 최저점 조건
        		int score =0;
        		for(int j=0;j<size;j++) {
        			if(j!=i) {score +=scores[j][i] ;}
        		}
        		answer += returnString(score/(size-1));
        		continue;
        	}
        	int score =0;
    		for(int j=0;j<size;j++) {score +=scores[j][i];}
    		answer += returnString(score/size);
        }
        return answer;
    }
	public static String returnString(int score) {
		System.out.println(score);
		if(score>=90) return "A";
		if(score>=80) return "B";
		if(score>=70) return "C";
		if(score>=50) return "D";
		return "F";
	}
}

 

3 주차.

https://programmers.co.kr/learn/courses/30/lessons/84021

 

코딩테스트 연습 - 3주차

[[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0

programmers.co.kr


3주차의 문제는 배열탐색 + 그리디 문제이다. 문제는 블럭을 빈칸에 끼우는 것인데

각 블럭은 90,180,270 도 회전이가능하다.

 

즉, 블록의 정의를 내리는것이 중요한데, 나는 첫BFS시작점에서 좌표의 변화를 리스트로 담아 블록을 표시했다.

해당 블록은 4개의 리스트로 구성되어있는데, 각각 회전하였을때에 좌표변화를 담는값이다.

 

즉 Game_Board를 탐색하면서 특정 좌표에서 리스트의 모든 좌표변화에 대해서 예외가 발생하지 않는다면, 놓을수 있고

항상 그리디하게 최대값을 보장한다.

 

각 좌표에 대한 회전은 

아래방식으로 돌려버렸다.. 딱히 좋은방법이 생각안나서..

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;

class Solution {
 public static int answer = 0; 
	public static int dir[][] = {{1,0},{-1,0},{0,1},{0,-1}};
	public static ArrayDeque<int []> dq = new ArrayDeque<>();
	public static class Block{
		boolean isUsed = false;
		ArrayList<int[]> info[];
		public Block(int size) {
			info = new ArrayList[size];
			for(int i=0;i<size;i++) {
				info[i] = new ArrayList<>();
			}
		}
	}
	public static HashMap<Integer, ArrayList<Block>> Hm = new HashMap<>();
	public static int solution(int[][] game_board, int[][] table) {
        createBlocks(table);
        fillGameBoard(game_board);
        return answer ;
	}
	private static void fillGameBoard(int[][] game_board) {
		/*BFS */
		int size = game_board.length;
		for(int i=0;i<size;i++) {for(int j=0;j<size;j++) {if(game_board[i][j]==1) {game_board[i][j]=-1;}}}
		for(int i=0;i<size;i++) {
			for(int j=0;j<size;j++) {
				if(game_board[i][j] ==0) {
					ArrayList<int []> xy = new ArrayList<>();
					dq.add(new int[] {i,j});
					int space =1;
					game_board[i][j] = -1;
					xy.add(new int[] {i,j});
					while(!dq.isEmpty()) {
						int now[] = dq.poll();
						for(int k=0;k<4;k++) {
							int nexty= now[0] + dir[k][0];
							int nextx= now[1] + dir[k][1];
							if(isRange(game_board.length, nexty, nextx)&&0==game_board[nexty][nextx]) {
								xy.add(new int[] {nexty, nextx});
								space++;
								game_board[nexty][nextx] = -1;
								dq.add(new int[] {nexty,nextx});
							}
						}
					}
					/*좌표에 해당 area의 크기를 적어놓는다.*/
					for(int k=0;k<xy.size();k++) {
						game_board[xy.get(k)[0]][xy.get(k)[1]] = space;
					}
				} 
			}
		}
		CoverGameBoard(game_board);
		return ;
	}
	private static void CoverGameBoard(int[][] game_board) {
		int size = game_board.length;
		/*놓을수 있으면 항상 mvp다*/
		for(int index =0; index < size*size ; index++) {
			int i = index/size;
			int j = index%size;
			if(game_board[i][j]!=-1) {
				if(Hm.containsKey(game_board[i][j])) {
					/*해당 맵에 쓰여진 크기에 해당하는 블록만 탐색*/
					ArrayList<Block> path = Hm.get(game_board[i][j]);
					for(int k=0;k<path.size();k++) {
						if(path.get(k).isUsed) {continue;}
						int result = isGo(path.get(k), game_board,i,j);
						if(result != -1){
							path.get(k).isUsed=true;
							answer +=  game_board[i][j];
							fill(path.get(k).info[result],game_board,i,j);
							/*해당블록은 더이상 볼 필요가 없다.*/
							break;
						}
					}
				}
			}
		}
	}
	

	private static void fill(ArrayList<int[]> arrayList, int[][] game_board, int i, int j) {
		for(int k=0;k<arrayList.size();k++) {
			game_board[i+arrayList.get(k)[0]][j+arrayList.get(k)[1]] = -1;
		}
	}
	private static int isGo(Block block, int[][] game_board, int i, int j) {
		/*채움 가능하면 해당 블록의 회전 index를 리턴 */
		if(game_board[i][j]==1 ) {
			return 0;
		} else {
			for(int k=0;k<4;k++) {
				ArrayList<int []> add = block.info[k];
				boolean isCango = true;
				for(int kk=0;kk<add.size();kk++) {
					if(!isCango) break;
					int nexty = add.get(kk)[0]+i;
					int nextx = add.get(kk)[1]+j;
					if(isRange(game_board.length, nexty, nextx) && game_board[nexty][nextx] != -1) {
						continue;
					} else {
						isCango = false;
					}
				}
				if(isCango){
					return k;
				}
			}
		}
		return -1;
	}
	private static void createBlocks(int[][] table) {
	    int size = table.length;
		for(int i=0;i<size;i++) {
			for(int j=0;j<size;j++) {
				if(table[i][j]==1){
					ArrayList<int[]> xyDiff = new ArrayList<>();
					int starty = i;
					int startx = j;
					table[starty][startx] = 0;
					dq.add(new int[] {starty,startx});
					xyDiff.add(new int[] {0,0});
					while(!dq.isEmpty()) {
						int now[] = dq.poll();
						for(int k=0;k<4;k++) {
							int nexty= now[0] + dir[k][0];
							int nextx= now[1] + dir[k][1];
							if(isRange(size,nexty,nextx) && table[nexty][nextx]==1) {
								xyDiff.add(new int[] {nexty-starty , nextx-startx});
								table[nexty][nextx] = 0;
								dq.add(new int[] {nexty,nextx});
							}
						}
					}
					int Listsize = xyDiff.size();
					Block block ;
					if(Listsize ==1) {
						block = new Block(1);
						block.info[0] = xyDiff;
						if(Hm.containsKey(1)) {
							Hm.get(1).add(block);
						} else {
							ArrayList<Block> BlockList = new ArrayList<>();
							BlockList.add(block);
							Hm.put(1, BlockList);
						}
					} else {
						block = new Block(4);
						block.info[0] = xyDiff;
						// 3방향에대한 회전 좌표차이를 넣어야함.. 
						for(int k=1;k<4;k++) {
							ArrayList<int[]> twistedXy = new ArrayList<>();
							for(int kk=0;kk<xyDiff.size();kk++) {
								twistedXy.add(new int[] {
										((int)Math.sin(k*90*Math.PI/180)*xyDiff.get(kk)[1] + (int)Math.cos(k*90*Math.PI/180)*xyDiff.get(kk)[0]), 
										((int) Math.cos(k*90*Math.PI/180)*xyDiff.get(kk)[1] - (int)Math.sin(k*90*Math.PI/180)*xyDiff.get(kk)[0])});
								}
							block.info[k] = twistedXy;
						}
						
						if(Hm.containsKey(Listsize)) {
							Hm.get(Listsize).add(block);
						} else {
							ArrayList<Block> BlockList = new ArrayList<>();
							BlockList.add(block);
							Hm.put(Listsize, BlockList);
						}
					}
				}
			}
		}
	}
	private static boolean isRange(int size, int nexty, int nextx) {
		return nexty<size&&nextx<size&&nexty>=0&&nextx>=0;
	}
}

 

 

4 주차.

 

https://programmers.co.kr/learn/courses/30/lessons/84325

 

코딩테스트 연습 - 4주차

개발자가 사용하는 언어와 언어 선호도를 입력하면 그에 맞는 직업군을 추천해주는 알고리즘을 개발하려고 합니다. 아래 표는 5개 직업군 별로 많이 사용하는 5개 언어에 직업군 언어 점수를 부

programmers.co.kr


4주차의 문제는 조건에 맞게 계산후 우선순위를 부여하면된다 (점수가같으면 사전순으로)

우선순위큐를 써주어 가장 앞에오는 값을 리턴하면된다.

import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {
    public String solution(String[] table, String[] languages, int[] preference) {
        int max = -1;
        int score[] = new int[6];
        PriorityQueue<String> pq = new PriorityQueue<>(new Comparator<String>() {
        	@Override
        	public int compare(String o1, String o2) {
        		return o1.compareTo(o2);
        	}
		});
        for(int i=0;i<table.length;i++) {
        	String str[] = table[i].split(" ");
        	for(int j =1;j < str.length;j++ ) {
        		for(int k=0;k<languages.length;k++) {
        			if(str[j].equals(languages[k])) {
        				score[i] += ((6-j)*preference[k]);
        			}
        		}
        	}
        	max = max > score[i] ? max : score[i];
       }
       for(int i=0;i<table.length;i++) {
    	   if(max==score[i]) {
    		   pq.add(table[i].split(" ")[0]);
    	   }
       }
       
        
        return pq.peek();
    }
}

 

 

 

5 주차.

https://programmers.co.kr/learn/courses/30/lessons/84512

 

코딩테스트 연습 - 5주차

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니

programmers.co.kr


모음으로 구성된 단어에서 A ~ UUUUU 까지 몇번째에 등장하는지 묻는 문제이다.

진법처럼 풀어도되고, 경우의수가 작으므로 모든경우에대해서 번호를 매겨주면 된다.

import java.util.HashMap;
class Solution {
    public static HashMap<String, Integer> hm = new HashMap<>();
	public static char m[] = {'A','E','I','O','U'};
	public static int result=1;
	public static int solution(String word) {
	        DFS("");
	        return hm.get(word);
	}
	private static void DFS(String str) {
		if(str.length()>=1) hm.put(str, result++);
		if(str.length()==5) return;
		for(int i=0;i<5;i++) DFS(str+m[i]);
	}
}

 

6 주차.

https://programmers.co.kr/learn/courses/30/lessons/85002

 

코딩테스트 연습 - 6주차_복서 정렬하기

복서 선수들의 몸무게 weights와, 복서 선수들의 전적을 나타내는 head2head가 매개변수로 주어집니다. 복서 선수들의 번호를 다음과 같은 순서로 정렬한 후 return 하도록 solution 함수를 완성해주세요

programmers.co.kr


import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class 위클리6주차 {
	 static class boxer {
		 double rate = 0;
		 int overCnt = 0;
		 int weight =0 ;
		 int number =0;
		 public boxer(double rate, int overCnt, int weight, int number) {
			this.rate = rate;
			this.overCnt = overCnt;
			this.weight = weight;
			this.number = number;
		 }
	}
	 
	 public static PriorityQueue<boxer> pq = new PriorityQueue<>(new Comparator<boxer>() {
		@Override
		public int compare(boxer o1, boxer o2) {
			if(o1.rate > o2.rate) {
				return 1;
			} else if(o1.rate < o2.rate) {
				return -1;
			} else {
				if(o1.overCnt > o2.overCnt) {
					return 1;
				} else if(o1.overCnt < o2.overCnt) {
					return -1;
				} else {
					if(o1.weight > o2.weight) {
						return 1;
					} else if(o1.weight < o2.weight) {
						return -1;
					} else {
						if(o1.number > o2.number) {
							return 1;
						} else if(o1.number < o2.number) {
							return -1;
						} else {
							return 0;
						}
					}
				}
			}
		}
	 });
			 
	 public static int[] solution(int[] weights, String[] head2head) {
		    int size = weights.length;
	        int[] answer = new int[size];
	        for(int i=0;i<size;i++) {
	        	int cnt = 0;
	        	int weight = weights[i];
	        	int now = i+1;
	        	int Overcnt = 0;
	        	int wins= 0;
	        	String str= head2head[i];
	        	for(int j=0;j<str.length();j++) {
	        		char result = str.charAt(j);
	        		if(result == 'N') {
	        			continue;
	        		} else if(result == 'L') {
	        			cnt++;
	        		} else {
	        			if(weights[j] > weight) {
	        				Overcnt++;
	        			}
	        			cnt++;
	        			wins++;
	        		}
	        	}
	        	
	        	double rate = (wins)/(double)cnt;
	        	pq.add(new boxer(rate, Overcnt, weight, now));
	        }
	       while(!pq.isEmpty()) {answer[--size] = pq.poll().number; }
	       return answer;
	}
 }

 

어떤 우선순위를 비교하여 정렬을 할 때에는 우선순위 큐에 비교순위 ( Comparator ) 를 오버라이딩해서 적어주자

 

비교하는 Boxer에 필요한 정보를 묶어서 Class로 다루면 편리하다.

 

 

 

7 주차.

https://programmers.co.kr/learn/courses/30/lessons/86048

 

코딩테스트 연습 - 7주차

사회적 거리두기를 위해 회의실에 출입할 때 명부에 이름을 적어야 합니다. 입실과 퇴실이 동시에 이뤄지는 경우는 없으며, 입실 시각과 퇴실 시각은 따로 기록하지 않습니다. 오늘 회의실에는

programmers.co.kr


import java.util.Arrays;
public class 위클리7주차 {
  public static int[] solution(int[] enter, int[] leave) {
        int size = enter.length;
    	int[] answer = new int[size];
        boolean gone[] = new boolean[size];
    	int i=0,j=0;
        for(;i<size;i++) {
        	for(int k=i-1;k>=0;k--){
        		if(!gone[enter[k]-1]) {
	        		answer[enter[k]-1]++;
	        		answer[enter[i]-1]++;
	        	}
        	}
        	for(int k=0;k<=i;k++) {
        		if(j<size&&!gone[leave[j]-1]&&leave[j]==enter[k]) {
        			gone[leave[j++]-1] =true;
        			k=-1;
        		}
        	}
        }
      return answer;
    }
}

 

반드시 만나는 최소의 경우를 구하기 위해서, 매턴마다 새로운 사람이 들어왔을때에

만남의 카운트를 해주고 현재 leave의 index까지 반복하여서 enter에 속했는지 여부를 판단해주자,

이전에 나간경우를 제외해야하기때문에, Gone이라는 Boolean변수로 이전에 나갔는지의 여부를 체크해주면서

들어오는 인원에대해서 서로 카운트를 진행한다.

 

 

 

8 주차.

 

https://programmers.co.kr/learn/courses/30/lessons/86491

 

코딩테스트 연습 - 8주차

[[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]] 120 [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]] 133

programmers.co.kr



public class 위클리8주차 {
  public static int[] solution(int[][] sizes) {
            int answer = 0;
	        int h=-1; 
	        int w=-1;
	        for(int i=0;i<sizes.length;i++) {
	        	if(sizes[i][1] > sizes[i][0]) {
	        		answer = sizes[i][1];
	        		sizes[i][1] = sizes[i][0];
	        		sizes[i][0] = answer;
	        	}
	        	h = h > sizes[i][1] ? h : sizes[i][1]; 
	    		w = w > sizes[i][0] ? w : sizes[i][0]; 
	        }
	        return h*w;
    }
}

모든 경우에 대해서 w>h 이나 w<h 인경으로 만들어 준다음 가장 큰값끼리 곱하면 

모든 명함을 담을수 있는 지갑의 크기를 구할 수 있다.

 


 

 

+ ) 후기 

 

사실 특정 알고리즘의 구현가능여부를 물어보는것은 코딩테스트 시험과는 거리가 멀다고 생각한다.

문제조건을 하나하나 읽고, 논리적으로 구현하는 방식을 평가해야한다.

그러다보면 구현이나 시뮬레이션으로 편중되는데, 이번 위클리챌린지문제는 그러한 부분을 잘 자료구조와 엮은것 같다

 

긴긁읽어주셔서 감사합니다.

 

'알고리즘 > 구현,시뮬' 카테고리의 다른 글

BOJ - 3020 ) 개똥벌레  (1) 2021.11.03
BOJ - 5373 ) 큐빙  (0) 2021.10.02
BOJ - 1120 ) 문자열  (0) 2021.09.13
BOJ - 2417 ) 정수제곱근  (0) 2021.08.01
BOJ - 11728 ) 배열 합치기  (0) 2021.07.29
Comments