[프로그래머스,Level 2] 숫자의 표현 (JAVA 구현)

- 첫 풀이 및 정답풀이 이 문제의 핵심은 연속된 자연수들로 n이라는 특정 수를 만들 수 있는 경우의 수를 찾는 것이다. dp로 푸는 방법이 있을까 하고 규칙성을 찾아보았지만, 찾지 못했고 단순한 완전 탐색 문제라고 생각되어 반복문을 이용해 간단하게 해결할 수 있었다. class Solution { public int solution(int n) { int answer = 0; int temp; // 1. 1부터 n까지 반복, 각 경우의 시작 숫자. for(int i = 1;i

→2021.01.26

코테/프로그래머스(Programmers)

[프로그래머스,Level 2] 땅따먹기 (JAVA 구현)

- 첫 풀이 및 정답풀이 이 문제는 처음 읽자마자 dp를 활용해야 하는 문제인 것을 알 수 있었다. 한 줄의 선택 횟수는 1번이고, 다음 줄에선 이전 줄에서 선택한 열의 숫자는 선택하지 못한다는 제약사항이 존재한다. 이러한 규칙 속에서 dp를 위한 점화식을 세워보면, x번째 행에서 0번째 열은 이전 행의 값들 중 가장 큰 값을 선택하고 와야 한다. 그렇기에 dp [x][0] = max(dp [i-1][1], dp [i-1][2], dp [i-1][3]) + land [x][0]와 같은 식이다. 이 과정을 n번째 행까지 수행하면, 각각의 경우의 수들 중 최댓값들이 저장되어 있으며 그 중에서도 가장 큰 값이 문제가 원하는 답이다. class Solution { int solution(int[][] land)..

→2021.01.25

코테/프로그래머스(Programmers)

[프로그래머스,Level 2] 다음 큰 숫자 (JAVA 구현)

- 첫 풀이 및 정답풀이 이 문제를 읽은 후, 바로 Integer.toBinaryString() 메서드를 활용해야겠다는 생각이 들었고 바로 정답 처리를 받을 수 있었다. 로직은 간단하다. 1. 입력된 n을 2진수로 변환한다. 2. 변환된 2진수의 비트가 1인 개수를 카운팅한다. 3. n+1부터 위 과정을 반복해 앞서 구한 개수와 일치하는 수를 찾는다. class Solution { public int solution(int n) { int answer = 0; // 1. n을 2진수 변환. String str = Integer.toBinaryString(n); // 2. n의 1인 비트의 수를 저장하는 변수. int cnt =0; // 3. 1인 비트의 수를 카운팅. for(int i = 0;i

→2021.01.25

코테/프로그래머스(Programmers)

[프로그래머스,Level 2] 올바른 괄호 (JAVA 구현)

- 첫 풀이 및 정답풀이 이 문제를 읽고 처음에는 정렬을 통해 각각의 괄호 개수를 카운팅 하는 방식으로 풀어보고자 했지만, 다시 생각해보니 주어진 문자열의 괄호들의 순서가 변하면 안된다는 사실을 알 수 있었다. 따라서 문자열 s를 탐색하면서 풀어나가야 되겠다고 생각했다. 우선 첫 번째로 배제한 경우는 문자열 s의 첫 문자가 ) 닫힌 괄호가 먼저 나오는 경우였다. 이렇게 처리하면 다음으로 고려해야 하는 것은 ( 열린 괄호부터 시작하는 경우뿐이다. 본인은 열린괄호의 개수를 통해 풀어보고자 했다. 1. 열린 괄호가 나오면 open이라는 변수를 증가시킨다. 2. 닫힌 괄호가 나오면 open을 감소시킨다. 3. 단, 열린 괄호가 1개 나온 상태에서 닫힌 괄호가 2번 나오는 경우를 배제하기 위해 닫힌 괄호를 만나면..

→2021.01.22

코테/프로그래머스(Programmers)

[프로그래머스,Level 2] 가장 큰 정사각형 찾기 (JAVA 구현)

- 첫 풀이 이 문제를 처음 풀 때는 board를 탐색하면서 1을 만나면 1부터 board의 길이만큼 증가시키며 정사각형을 만족하는지 판단하는 방식으로 진행하였는데, 몇몇 테스트 케이스는 통과하지만 이 경우는 모든 1에 대해서 수행하기 때문에 효율성 측면에서도 시간 초과가 발생한다. DFS나 BFS를 이용해 풀어볼까 했지만 불가능할 것 같아 다른 방법이 있나 찾아보게 되었다. - 정답풀이 결국 이 문제는 DP를 활용해야 한다. 자세한 설명은 다른 블로그를 참고하면 쉽게 알 수 있다. class Solution { public int solution(int [][]board) { // 1. DP 배열. int dp[][] = new int[board.length][board[0].length]; int a..

→2021.01.22

코테/프로그래머스(Programmers)

[프로그래머스,Level 2] 타겟 넘버 (JAVA 구현)

- 첫 풀이 및 정답풀이 DFS, BFS를 이용한 완전 탐색 문제를 풀 때는 항상 무엇을 탐색의 대상으로 삼아야 하는지에 대한 기준을 내리지 못해 삽질을 많이 하는 것 같다. 문제에 대한 이해는 간단했다. 완전탐색을 이용해 모든 경우의 수를 고려하면 된다. 예를 들어, 예제의 경우 1이 5가지가 있다. 이것을 이용해 만들 수 있는 경우의 수는 +1+1+1+1+1 / +1+1+1+1-1 / +1+1+1-1+1/ +1+1+1-1-1........ 등과 같이 다양하게 존재한다. 모든 숫자에 대한 탐색이 끝났을 때, 해당 식의 값이 target값과 동일하다면 카운팅 해주면 된다. 본인은 위의 내용을 모두 생각한 뒤 반복문을 이용해 짜보려고 하였지만 결국 삽질이었다. 결국 적절한 변수 하나만을 이용하면 간단하게 ..

→2021.01.22

코테/프로그래머스(Programmers)

[프로그래머스,Level 2] 카펫 (JAVA 구현)

- 첫 풀이 이 문제를 읽고 처음 발견해낸 사실은 노란색 격자가 들어가기 위해선 무조건 세로의 길이가 3 이상이어야 한다는 것이다. 가로의 길이에 상관없이, 갈색 테두리인 두 개의 라인을 제거했을 때 노란색 격자가 존재하기 위해서는 3 이상이어야 했다. 두 번째 알게 된 것은 갈색 격자 + 노란 격자 = 총 격자의 수이므로 총 격자의 수만큼 카펫을 만들 수 있는 경우는 총격자의 수의 약수들로 구할 수 있다는 사실이다. 입력 예제 3의 경우 갈색 격자 24개, 노란 격자 24개이므로 총격자의 수는 48이 되며, 만들 수 있는 경우의 수는 {1, 2, 3, 4, 6, 8, 12, 16, 24, 48}로 세로 1, 가로 48 /세로 2, 가로 24/ 세로 3 가로 16.....으로 총 5가지의 경우의 수가 발..

→2021.01.22

코테/프로그래머스(Programmers)

[프로그래머스,Level 2] 구명보트 (JAVA 구현)

- 첫 풀이 처음에 문제를 제대로 읽지 않아 보트의 정원이 2명이라는 점을 간과하여, people 배열의 무게를 오름차순으로 정렬한 뒤 가벼운 사람들을 limit까지 태우는 방식으로 풀어보려 했는데 계속 실패가 나왔다. 다른 분들의 풀이를 참고하는 과정에서 첫 문장에 '보트의 정원은 2명'이라는 강조 표시를 보고 깨달았다. (생각 외로 이를 놓치는 사람이 많은 것 같다.) - 정답풀이 결국 인원 제한이 2명인 보트를 그리디스럽게 채우기 위해서는, 가장 많은 무게가 나가는 사람과 함께 가장 적은 무게가 나가는 사람을 태우는 것이 최적일 것이다. import java.util.Arrays; class Solution { public int solution(int[] people, int limit) { in..

→2021.01.21

코테/프로그래머스(Programmers)

[프로그래머스,Level 2] 위장(JAVA 구현)

- 첫 풀이 문제 자체를 읽었을 때, 조합을 구하는 문제라고 생각해 버려 접근을 잘못하였다. 열심히 삽을 푸다 다른 분들의 풀이를 조금 참고하게 되었다. - 정답풀이 이 문제는 사실 수학적인 '데카르트 곱'의 곱집합에 대한 문제라고 생각할 수 있다. 곱집합은 두 집합의 요소들로 만들 수 있는 경우의 수를 구하는 개념으로 쓰인다. 이 개념을 이용하기 전에 주의해야 할 점은 각각의 옷 종류에는 아예 선택하지 않는 경우 또한 존재하기 때문에 각 요소들의 개수 +1로 고려해주어야 한다. 입력 예제 1번의 경우 headgear가 2개, eyewear가 1개이지만, 안 입는 경우를 포함해 각각 3개 2개로 고려한다. 곱집합을 이용해 3 * 2 =6개가 되지만, 여기에는 두 집합의 요소로 만들 수 있는 모든 경우의 ..

→2021.01.21

코테/프로그래머스(Programmers)

[프로그래머스,Level 2] 전화번호 목록(JAVA 구현)

- 첫 풀이 및 정답풀이 우선 이 문제는 해시로 분류되어 있는 문제이지만, 반복문을 이용해도 풀 수 있을 것 같아 시도해보아 풀 수 있었다. 문제 자체는 매우 간단하다. 한 전화번호가 다른 한 전화번호의 접두사가 된다면 false를 리턴하면 된다. 이 말은 접두사가 될 수 있는 전화번호가 하나라도 존재한다면 바로 false를 리턴하면 된다는 소리이기 때문에 다른 모든 전화번호를 탐색할 필요가 없어진다. 본인은 문자열 배열에서 하나의 기준점을 두고, 다른 전화번호와 비교하는 2중 반복문을 사용하였으며 이때, 비교하는 전화번호는 반드시 비교되는 문자열에 비해 길이가 짧아야 한다. 이는 애초에 길이가 긴 문자열이 자신보다 길이가 짧은 문자열의 접두사가 될 수 없기 때문이다. * for문을 이용한 풀이 impo..

→2021.01.21

티스토리툴바