Algorithm & Data Structure

[Java] 프로그래머스 : 문자열을 정수로 바꾸기(feat. String to Int)

https://programmers.co.kr/learn/courses/30/lessons/12925 코딩테스트 연습 - 문자열을 정수로 바꾸기 문자열 s를 숫자로 변환한 결과를 반환하는 함수, solution을 완성하세요. 제한 조건 s의 길이는 1 이상 5이하입니다. s의 맨앞에는 부호(+, -)가 올 수 있습니다. s는 부호와 숫자로만 이루어져있습니 programmers.co.kr 풀이 1. Integer.parseInt(); String -> Int 로 형변환을 해주면 한줄로 끝낼 수 있다. int answer = Integer.parseInt(s); 2. 알고리즘으로 풀기 먼저 맨 앞에 부호가 오는 경우를 고려해야 한다. '-' , 즉 음수가 오는 경우엔 boolean 변수 sign에 false..

[Java] 프로그래머스 Lv.2 : 가장 큰 정사각형 찾기

https://programmers.co.kr/learn/courses/30/lessons/12905 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 풀이 해당 문제의 규칙은 다음과 같다. 행 또는 열의 길이가 1이면 정사각형의 넓이는 1이다. 루프를 돌아 자신의 위치([i][j])의 값이 0이 아닌 경우, 자신의 기준으로 왼쪽상단(↖), 왼쪽(←), 위쪽(↑) 의 최솟값을 구한뒤, 자신의 위치에 최솟값+1을 할당한다. 그렇게 구한 board값 중 최댓값을 answer에 할당 해준 뒤 answer*answer로 정사각형 넓이를 구해 리턴한다. 2번의 최솟값이 0이상인 경우엔 1로 이루어진 정사각형이 ..

[Java] 프로그래머스 Lv.2 : 타겟 넘버

https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 programmers.co.kr 풀이 DFS를 이용한 풀이 depth 변수 값을 통해 탐색 중인 트리의 깊이를 알 수 있다. 트리 끝에 도착했다면, 여태 계산한 result와 target 값을 비교한다. class Solution { int count = 0; public int solution(int[] numbers, int target) { int answer = ..

[Java] 프로그래머스 Lv.2 : 구명보트

https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 풀이 구명보트를 최대한 적게 사용하여 모든 사람을 구출하기 위해, 가장 먼저 사람들의 몸무게가 담겨있는 배열 people을 Arrays.sort()로 정렬해준다. 몸무게가 가장 적은 사람(people[min])과 가장 많은 사람(people[max])의 합계를 limit와 비교해 구출여부를 따진다. 만약 두 명의 몸무게합이 limit가..

[Java] 프로그래머스 Lv.2 : 소수 찾기

https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 풀이 찾은 소수를 중복없이 저장하기 위해 자료구조로 HashSet을 사용 이미 사용했던 종이조각인지 아닌지를 확인하기위해 boolean visited[] 이용 완전탐색(DFS)으로 만들 수 있는 숫자조합을 찾고 (재귀적으로 구현) 소수인지 아닌지 판별한다. 마지막으로 set.size() 을 return 해준다. 전체 코드 import java.ut..

[Java] 프로그래머스 Lv.2 : 카펫

https://programmers.co.kr/learn/courses/30/lessons/42842?language=java 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr 풀이 카펫 격자의 수는 다음과 같다. (노란색) = (가로-2)*(세로-2) (갈색) = (가로*세로)-(노란색) 1. 노란색 격자의 수(yellow)의 약수의 중심까지 반복문을 돌려준다. (즉, 해당 숫자의 √N까지 확인) 2. i가 yellow의 약수라면, 가로에 i+2, 세로에 (yellow/i) +2을 저장한다. (가로 >= ..

[Java] 프로그래머스 Lv.2 : H-Index

https://programmers.co.kr/learn/courses/30/lessons/42747 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr 문제이해가 잘 되지않아서 테스트 케이스를 많이 추가해서 풀었었다.. # 테스트 케이스 공유 Parameters Return [3, 1, 0] 1 [3, 1, 1, 1, 4] 2 [0, 0, 0, 1] 1 [9, 9, 9, 12] 4 [1, 1, 5, 7, 6] 3 [0, 0, 0] (테스트 16번) 0 풀이 h를 발표한 논문 수(..

[Java] 프로그래머스 Lv.2 : 더 맵게

https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 풀이 우선순위 큐(Priority Queue)를 사용한다. 낮은 숫자가 우선순위인 int 형 우선순위 큐를 선언하고 큐에 스코빌지수를 넣어준다. 첫번째 heap의 요소가 K이상이 될 때까지 반복문을 돌린다. 앞의 두 음식을 꺼내(pop) 새로운 음식으로 만들어 다시 heap에 넣어준다.(pull) 가장 앞의 음식의 스코빌 지수가 K이상이 되면 bre..