본문 바로가기

Algorithm/Programmers

 (8)
[Java] 2021 위클리 챌린지 12주차 - 피로도 던전의 개수가 8개로 수가 많지 않다. 던전을 탐험하는 경우의 수는 8! 인데, 이는 작은 숫자이므로 Brute force로 해결이 가능하다. 순열을 찾는 알고리즘은 back tracking을 사용할 수 있는데, 던전을 방문하고 함수를 탐색을 하고 탐색이 끝나면 방문 내역에서 지워주면 된다. import java.util.HashSet; import java.util.Set; class Solution { Set visited = new HashSet(); int answer = 0; public String makeKey(int[] d){ return d[0] + "&" + d[1]; } public void solve(int k, int[][] dungeons, int depth){ int n = d..
[Java] 2021 위클리 챌린지 11주차 - 아이템 줍기 테두리와 안쪽을 구분해야 한다. 단순하게 좌표의 길이를 2배로 키우면 테두리와 안쪽을 구분하기가 쉬워진다. 1. (짝수, 짝수) 는 점 2. (짝수, 홀수) 와 (홀수, 짝수)는 선분 위 3. (홀수, 홀수)는 내부가 된다. 먼저 모든 사각형을 1로 채워준 다음, 내부를 0으로 채워주면 제일 바깥쪽 테두리만 남게 된다. 이 이후에는 BFS를 통해서 얼마나 걸리는지 확인해주면 된다. 2배로 키워놨기 때문에 정답은 2로 나눈 값이 된다. class Point{ int x; int y; int depth; public Point(int x, int y, int depth){ this.x = x; this.y = y; this.depth = depth; } } class Solution { public int ..
[Java] 2021 위클리 챌린지 10주차 - 교점에 별 만들기 직선의 교점 중 정수가 되는 교점에 * 모양으로 표시하고, 이 별들을 포함하는 최소한의 사각형을 만들어서 출력하는 것이 문제이다. 먼저 정수가 되는 교점을 찾아야된다. 문제에서 친절하게 교점을 구하는 식을 알려주었다. $$Ax + By + E = 0$$ $$Cx + Dy + F = 0$$ $$ x = {BF - ED \over AD -BC}, y = {EC - AF \over AD -BC}$$ 이 식을 이용해서 교점을 구하면 된다. 단, AD-BC가 0인 경우에는 두직선이 평행하는 경우로 제외해준다. 그리고 나머지 연산을 이용해서 딱 나누어 떨어지는지를 체크하고, 정수의 교점만 찾는 것이기 때문에 딱 나누어 떨어지지 않으면 마찬가지로 제외해준다. 이렇게 구한 교점들을 배열에 넣어서 저장하고, 각각의 x와..
[Java] 2021 위클리 챌린지 9주차 - 전력망을 둘로 나누기 Node라는 클래스를 만들어서 wire로 연결된 송전탑들을 연결을 시켜준다. 이후 어떤 wire를 제거하였을 때, 차가 최소가 되는지 모르기 때문에 각 wire들을 순회하면서 제거한다. 그리고 bfs를 이용해서 각 송전탑들이 몇개가 연결이 되었는지 구하고, 두 그룹의 차이를 출력하면 된다. class Node { int id; List children; public Node(int id) { this.id = id; children = new ArrayList(); } } class Solution { public int solution(int n, int[][] wires) { int answer = n; Node[] nodeArr = new Node[n + 1]; for (int i = 0; i
[Java] 위클리 챌린지 8주차 - 최소직사각형 sizes에 이차원 배열로 가로 세로의 값이 주어진다. 가로세로중 긴 길이를 가로로, 짧은 길이를 세로로 바꾸어서 각각 가로의 최대값과 세로의 최대값을 구한 후 이를 곱해주어 반환한다. class Solution { public int solution(int[][] sizes) { int answer = 0; int n = sizes.length; int maxWidth = 0; int maxHeight = 0; for(int i = 0; i < n; i ++){ maxWidth = Math.max(maxWidth, Math.max(sizes[i][0], sizes[i][1])); maxHeight = Math.max(maxHeight, Math.min(sizes[i][0], sizes[i][1])); ..
[Java] 2021 위클리 챌린지 7주차 - 입실 퇴실 모기업 코딩테스트의 기출문제로 당시 너무 어려워서 이것을 빼고 제출했던 기억이 있다. 프로그래머스의 정답자 수가 다른 주차수에 비해서 적은 것을 보면 풀기 어려운 문제임을 직감할 수 있다. 나는 그림을 그려서 문제의 규칙을 찾아보고자 했다. 먼저 입실을 1, 4, 2, 3 순으로 하고, 퇴실을 2, 1, 4, 3으로 하는 경우를 살펴보자. 입실과 퇴실을 일렬로 쓰고, 같은 번호를 선으로 이었다. 선으로 둘러쌓아진 부분이 각 번호가 존재한 시간을 나타내게 된다. 1번과 다른 번호들의 관계를 보면서 어떤 경우일 때 확정적으로 만나게 되는지 알아보자. - 1번과 2번의 관계 1번의 파란선이 2번의 노란선을 감싸고 있는 구조가 보이게 되는데, 이 경우에는 1번과 2번이 무조건 만났다는 것을 알 수 있다. 그래서..
[Java] 2021 위클리 챌린지 6주차 - 복서 정렬하기 복서들의 승패 정보를 가지고 정렬을 하면 되는 문제이다. 전체 승률이 높은 복서의 번호가 앞쪽으로 갑니다. 아직 다른 복서랑 붙어본 적이 없는 복서의 승률은 0%로 취급합니다. 승률이 동일한 복서의 번호들 중에서는 자신보다 몸무게가 무거운 복서를 이긴 횟수가 많은 복서의 번호가 앞쪽으로 갑니다. 자신보다 무거운 복서를 이긴 횟수까지 동일한 복서의 번호들 중에서는 자기 몸무게가 무거운 복서의 번호가 앞쪽으로 갑니다. 자기 몸무게까지 동일한 복서의 번호들 중에서는 작은 번호가 앞쪽으로 갑니다. 위 4가지 조건으로 정렬을 시키면 된다. 그래서 복서의 정보를 담을 class를 선언해주고, 해당 값들을 저장한다. 승률의 경우 플레이한 게임의 수가 0인 경우에 0/0 이 되지 않도록 주의를 기울이면 쉽게 해결이 가..
[Java] 2021 위클리 챌린지 5주차 - 모음 사전 A, E, I, O, U 5개의 모음을 사용하여 만들 수 있는 길이 5 이하의 모든 단어가 수록된 단어집이 있다. 단어는 사전순으로 배열되어 있으며, 첫번째 단어는 "A"이고, 두번재 단어는 "AA"이고 마지막 단어는 "UUUUU"이다. word를 input으로 받을 때, 이 단어가 단어집에서 몇번째째 단어인지 return 하는 문제이다. 대략적으로 계산해보았을 때 총 단어의 개수는 6^5 = 7776 개를 넘을 수 없다. 단어의 위치를 알 수 있는 규칙을 찾는 것도 방법이겠지만, 단어의 수가 많지 않으니 brute force 방법을 이용해 풀어도 된다. orderMap이라는 map변수를 만들어서 (단어, 순번) 조합으로 map에다 저장을 하고, solution에는 map에서 순번을 찾아서 return하..

티스토리툴바