PS/프로그래머스
프로그래머스 Lv.2 예상 대진표 [Java]
1. 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12985 2. 문제 해설 간단한 문제였다. a 와 b를 2로 나눠주면서 나눠준 횟수를 구하면 된다.(짝수이냐 홀수이냐는 구분해줘야한다.) 단, 언제까지 나눠줄 것인지 조건을 설정하는 것이 문제의 핵심이다. 조건 1. a 와 b의 차이가 1이어야 함. 조건 2. a 와 b 중 작은 수가 홀수여야함. 예를 들어 a = 4이고 b =5 이면, 차이가 1이지만 한 라운드를 더 치뤄야한다. 위 조건을 동시에 만족할 때까지 a와 b를 나누어주면 된다. 3. 코드 보기 class Solution { public int solution(int n, int a, int b) { int answer =..
프로그래머스 Lv.3 순위 [Java]
1. 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/49191 2. 문제 해설 순위를 확정 짓는 방법은 생각해내기 쉽다. 자신과 연관된 results 값이 n-1 개면 순위는 확정된다. (이때 n은 총 선수의 수) 문제에서 나온 경우로 예를 들자면, 2번 선수와 관련된 results 값은 [4, 3], [4, 2], [3, 2], [1, 2], [2, 5]이다. 즉, 1, 3, 4번 선수에게는 패했고, 5번 선수에게는 이긴 것이다. 자신과 관련된 경기 결과가 4개이므로 순위가 확정되었다. 2번 선수의 경우는 처리하기 쉽지만, 여기서 문제는 5번 선수와 같은 경우를 어떻게 처리할 것인가이다. 5번 선수는 주어진 results 값에서 자신과..
프로그래머스 Lv.2 게임 맵 최단거리 [Java]
1. 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/1844 2. 문제 해설 최단거리를 찾는 대표적인 문제이다. 이렇게 최단거리를 찾아야하는 문제는 bfs를 이용하여서 푸는 것이 편하다. 처음에 풀었을 때는 dfs도 간만에 구현해볼 겸하고 dfs로 풀었다가 시간 초과로 효율성 테스트를 통과하지 못했다. bfs는 목적지에 도착했을 때, 최단거리로 방문하는 것이 보장되지만 dfs는 모든 경우의 수를 다 보기 때문에 더 오랜 시간이 걸리기 때문이다. 3. 코드 보기 import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; class Solution { class..
2021 카카오 채용연계형 인턴십 Lv3 표 편집 [Java]
2021 카카오 채용연계형 인턴십 Lv3 표 편집 1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/81303 2. 문제 해설 배열의 경우 삽입, 삭제의 시간복잡도가 O(n), 연결리스트의 경우 O(1)이다. 삽입, 삭제가 빈번하게 이뤄지는 경우 연결리스트를 이용하는 것이 효율적이다. 이 문제의 경우 행의 최대 갯수도 100만이고 명령의 갯수도 최대 20만이기에 이므로 연결리스트를 이용하여 푸는 것이 좋다고 생각했다. 행들의 정보를 담기 위해 Node 클래스를 만들었다. Node 클래스에는 이전 노드를 가리키는 prev, 다음 노드를 가리키는 next, 삭제 여부를 담는 removed가 있다. 각 행들은 Node 클래스를 이용하여 표현했고, 행들을..
2021 카카오 채용연계형 인턴십 Lv2 거리두기 확인하기 [Java]
2021 카카오 채용연계형 인턴십 Lv2 거리두기 확인하기 1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/81302 2. 문제 해설 카카오 2021 채용연계형 인턴십 코딩테스트의 2번 문제이다. 맨해튼 거리가 2이하면 안된다는 의미는 bfs를 동서남북으로 돌았을 때 깊이 2 이하로는 참가자가 있으면 안된다는 의미이다. 각 대기실을 돌면서 참가자를 만나면 bfs를 돌아 거리두기 확인 여부를 검사하는 방식으로 풀고자 했다. 일단 큰 틀을 먼저 잡기 위해 int 배열을 반환하는 solution 메서드를 먼저 구현했다. 5가지 대기실의 거리두기를 지켰는지 여부를 담을 answer 배열을 만들어준다. 그리고 3중 for문을 돌아야하는데, i는 대기실의 ..