코딩테스트/프로그래머스
[프로그래머스 Lv.1] JAVA 리스트, 배열 등
머밍
2024. 7. 1. 16:00
나누어 떨어지는 숫자 배열
배열보다 리스트가 편해..
import java.util.ArrayList;
class Solution {
public int[] solution(int[] arr, int divisor) {
ArrayList<Integer> answer = new ArrayList<>();
for(int i: arr) {
if(i%divisor == 0) {
answer.add(i);
}
}
if(answer.isEmpty()) {
answer.add(-1);
}
return answer.stream().mapToInt(i -> i).sorted().toArray();
}
}제일 작은 수 제거하기
- 배열로
class Solution {
public int[] solution(int[] arr) {
//배열 길이 1이면 -1 반환
if (arr.length == 1) {
int[] answer = {-1};
return answer;
}
int[] answer = new int[arr.length-1];
//최솟값 찾기
int min = arr[0];
for (int i = 0; i < arr.length; i++) {
min = Math.min(min, arr[i]);
}
//최솟값아니면 넣기
int index =0;
for(int i = 0; i < arr.length; i++) {
if( arr[i] == min) {
continue;
}
answer[index++] = arr[i];
}
return answer;
}
}리스트로
Collections.min
배열이나 리스트 등의 컬렉션에서 가장 작은 값 찾기
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
class Solution {
public int[] solution(int[] arr) {
//배열 길이 1이면 -1 반환
if (arr.length == 1) {
int[] answer = {-1};
return answer;
}
ArrayList<Integer> answer = new ArrayList<>();
for (int i :arr){
answer.add(i);
}
answer.remove(Collections.min(answer));
return answer.stream().mapToInt(i->i).toArray();
}
}행렬의 덧셈
class Solution {
public int[][] solution(int[][] arr1, int[][] arr2) {
int[][] answer = new int[arr1.length][arr1[0].length];
for(int i = 0; i < arr1.length; i++){
for(int j = 0; j < arr1[i].length; j++){
answer[i][j] = arr1[i][j] + arr2[i][j];
}
}
return answer;
}
}직사각형 별찍기
import java.util.*;
public class Solution {
public int[] solution(int []arr) {
ArrayList<Integer> answer = new ArrayList<>();
answer.add(arr[0]);
for(int i=1;i<arr.length;i++) {
if(arr[i]==arr[i-1]) {
continue;
} else{
answer.add(arr[i]);
}
}
return answer.stream().mapToInt(i->i).toArray();
}
}같은 숫자는 싫어
import java.util.*;
public class Solution {
public int[] solution(int []arr) {
ArrayList<Integer> answer = new ArrayList<>();
answer.add(arr[0]);
for(int i=1;i<arr.length;i++) {
if(arr[i]==arr[i-1]) {
continue;
} else{
answer.add(arr[i]);
}
}
return answer.stream().mapToInt(i->i).toArray();
}
}- 스택 풀이
스택이 비거나 바로 전의 스택 값과 다르면 넣기
import java.util.*;
public class Solution {
public int[] solution(int []arr) {
Stack<Integer> stack = new Stack<>();
for(int i : arr){
if(stack.isEmpty() || !stack.peek().equals(i)){
stack.push(i);
}
}
return stack.stream().mapToInt(i->i).toArray();
}
}
예산
오름차순으로 정렬한 뒤 차례대로 검사하면 된다.
import java.util.Arrays;
class Solution {
public int solution(int[] d, int budget) {
int answer = 0;
Arrays.sort(d);
int sum = 0;
for(int i=0; i<d.length; i++) {
sum += d[i];
if(sum > budget){
break;
}
answer++;
}
return answer;
}
}두 개 뽑아서 더하기
매번 하던 방식으로 ..
import java.util.ArrayList;
class Solution {
public int[] solution(int[] numbers) {
ArrayList<Integer> answer = new ArrayList<>();
for(int i= 0; i < numbers.length; i++){
for(int j = i+1; j < numbers.length; j++){
int num = numbers[i] + numbers[j];
if(!answer.contains(num)){
answer.add(num);
}
}
}
return answer.stream().sorted().mapToInt(i->i).toArray();
}
}- HashSet 사용
중복을 허용하지 않고 추가하는 거라 set생각이 나서 이 방법으로도 구현했다.
HashSet
중복된 요소를 허용하지 않으며, 빠른 검색, 삽입, 삭제 작업을 지원
-> 동일한 요소를 한 번만 저장
->십입, 삭제, 검색 연산의 평균 시간 복잡도는 O(1)
-> 요소의 순서를 보장 X. (순서가 중요한 경우 LinkedHashSet을 사용)
- 메서드
- set.add(요소): set집합에 요소 추가
- set.remove(요소): 특정 요소 제거
- set.contains(요소): 특정 요소 존재 확인
- set.size(): 집합의 크기(요소의 수)를 반환
- set.isEmpty(): 집합이 비어 있는지 확인
- set.clear(): 집합 모든 요소 제거
import java.util.HashSet;
import java.util.Set;
class Solution {
public int[] solution(int[] numbers) {
Set<Integer> answer = new HashSet<>();
for(int i = 0; i < numbers.length; i++) {
for(int j = i + 1; j < numbers.length; j++) {
int num = numbers[i] + numbers[j];
answer.add(num);
}
}
return answer.stream().sorted().mapToInt(i->i).toArray();
}
}K번째수
- 배열로만
리스트로만 풀고 싶었는데 배열이 아직 익숙하지 않아서 끝까지 배열만 썼다..
import java.util.Arrays;
class Solution {
public int[] solution(int[] array, int[][] commands) {
int[] answer = new int[commands.length];
int n = 0;
for(int[] i : commands){
int cur = 0;
int[] num = new int[i[1]- i[0] +1];
for(int j = i[0]; j <= i[1]; j++){
num[cur++] = array[j-1];
}
Arrays.sort(num);
answer[n++] =num[i[2]-1];
}
return answer;
}
}- Arrays.copyOfRange() 사용~
없어서는 안될 함수~!
import java.util.Arrays;
class Solution {
public int[] solution(int[] array, int[][] commands) {
int[] answer = new int[commands.length];
for(int i = 0; i < commands.length; i++){
int[] list = Arrays.copyOfRange(array,commands[i][0]-1,commands[i][1]);
Arrays.sort(list);
answer[i] = list[commands[i][2]-1];
}
return answer;
}
}
푸드 파이트 대회
문자열 + 0 + 앞의 문자열 역순이기 때문에 StringBuilder를 이용했다.
class Solution {
public String solution(int[] food) {
String answer = "";
StringBuilder sb = new StringBuilder();
for(int i=0; i<food.length; i++) {
if(food[i] <2){
continue;
} else{
String str = Integer.toString(i);
sb.append(str.repeat(food[i]/2));
}
}
answer = sb.toString() + "0";
sb.reverse();
answer += sb.toString();
return answer;
}
}
콜라 문제
예시를 잘 생각하면서 풀면 금방 풀린다.
class Solution {
public int solution(int a, int b, int n) {
// 마트에 주어야 하는 병 수 a, 2
//빈 병 a개를 가져다 주면 마트가 주는 콜라 병 수 b, 1
//상빈이가 가지고 있는 빈 병의 개수 n, 20
int answer = 0;
while(n >= a){
//빈병돌려주고 받은 병
int cur = (n/a) *b;
// 받은 만큼의 병
answer += cur;
//남은 병= 나머지 +새로받은거
n = (n%a) + cur;
}
return answer;
}
}여기부터 생각이 필요했던 문제~!
문자열 내 마음대로 정렬하기
힌트를 얻은 문제다.
"인덱스 1의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치합니다."라는 문제의 조건이 어려웠다. 사전순이면 결국 원래 문자의 첫 글자부터 정렬해야한다는 것인데, 그러기엔 정해진 인덱스순의 정렬이 먼저기에 이 부분에서 막혔다.
주어진 n에 해당하는 인덱스 부분을 원래 글자의 맨 앞에 저장시킨 뒤 정렬하면 모든 문제가 해결된다는 것을 구글링을 통해 알았다. 감탄했다. 와..
정렬 이후에는 앞에 추가한 문자 한개를 제외해서 answer배열에 넣어주면 되기때문에 코드가 한결 간단하다.
import java.util.ArrayList;
import java.util.Collections;
class Solution {
public String[] solution(String[] strings, int n) {
ArrayList<String> list = new ArrayList<>();
for(int i =0; i<strings.length; i++){
list.add("" + strings[i].charAt(n) + strings[i]);
}
Collections.sort(list);
String[] answer = new String[list.size()];
for(int i =0; i<list.size(); i++){
answer[i] = list.get(i).substring(1,list.get(i).length());
}
return answer;
}
}
[1차] 비밀지도
풀이 과정
1. 두 수를 비트연산중 OR한 값,즉 둘 중 하나가 1이면 1인 연산의 결과로 #과 공백 출력을 하기 때문에 먼저 비트 연산을 한다.
2. 그 연산 결과를 2진수의 문자열 형태로 받기 위해 Integer.toBinaryString()을 사용했다.
3. 이 함수의 결과는 맨앞의 0을 생략하기 때문에 자릿수를 맞추는 while문을 구현했다.
4. 0이면 공백, 1이면 #을 출력해야한다. 여기서 좀 고민을 했는데 그냥 replaceAll이 가장 간단할 것 같아 사용했다.
함수에 대해 매번 찾아서 공부한 보람있는 문제였다.
class Solution {
public String[] solution(int n, int[] arr1, int[] arr2) {
String[] answer = new String[n];
for (int i = 0; i < n; i++) {
int num = arr1[i] | arr2[i];
String str = Integer.toBinaryString(num);
while(str.length() < n) {
str = "0" + str;
}
answer[i] = str.replaceAll("1","#").replaceAll("0"," ");
}
return answer;
}
}명예의 전당(1)
문제설명
k전까진 명예의 전당(list)에 추가하고
k이후는 최하위 점수와 새로운 score의 점수를 비교하여 더 작은 점수는 명예의 전당에서 나간다.
score를 하나씩 비교하며 최하위 점수만 answer에 추가하고 이를 출력한다.
- 풀이 과정
- 먼저 리스트를 만들고 k전까지는 추가한다.
- k이후에 현재 최하위 점수와 score의 점수를 비교하는 부분이 어려웠다. 그러다 answer에 담기는 점수는 최하위이다. 이점이 힌트라고 생각해서 정렬을 이용했다.
그래서 list[0]이 최하위 점수였고
set()함수를 사용하여 현재 최하위점순보다 새로운 점수가 클경우에 0번째에 새로운 점수를 넣는 식으로 구현하였다.
재밌는 문제였다.
import java.util.ArrayList;
import java.util.Collections;
class Solution {
public int[] solution(int k, int[] score) {
int[] answer = new int[score.length];
ArrayList<Integer> list = new ArrayList<>();
for(int i = 0; i < score.length; i++) {
if(i<k){
list.add(score[i]);
} else{
if(list.get(0) < score[i]){
list.set(0, score[i]);
}
}
Collections.sort(list);
answer[i] = list.get(0);
}
return answer;
}
}
- 우선순위 큐 이용
: 다른 풀이를 찾아보다가 큐중에서도 숫자 배열에서 상위 k개의 최소값을 유지하고자 할때 유용하다는 사실을 알았다.
-> 최소값, 최대값을 추적하는데 유용 - 장점:
- 현재 상태에서의 최솟값 조회: peek() 메서드를 사용하면 큐의 헤드 요소를 제거하지 않고도 최솟값을 조회
- 최솟값 유지: 항상 최솟값을 큐의 앞에 위치
- 효율적인 삽입과 삭제: 삽입(add())과 삭제(poll()) 작업은 O(log n)의 시간 복잡도
메서드 정리
q.add(요소): 요소를 큐에 추가
q.poll(): 큐의 헤드(최솟값)를 제거하고 반환(큐가 비어 있는 경우 null을 반환)
q.peek(): 큐의 헤드(최솟값)를 제거하지 않고 반환(큐가 비어 있는 경우 null을 반환)
q.size(): 큐의 크기 반환
import java.util.PriorityQueue;
class Solution {
public int[] solution(int k, int[] score) {
int[] answer = new int[score.length];
// 선언
PriorityQueue<Integer> q = new PriorityQueue<>();
for(int i = 0; i < score.length; i++) {
q.add(score[i]);
//크기가 k 초과하면 최소값 제거 -> k개 유지
if(q.size() >k ){
q.poll();
}
//현재 q의 최소값을 저장
answer[i] = q.peek();
}
return answer;
}
}
추억 점수
문자열인 이름과 이에 따른 점수가 정해져 있어서 map을 사용했다.
import java.util.HashMap;
import java.util.Map;
class Solution {
public int[] solution(String[] name, int[] yearning, String[][] photo) {
int[] answer = new int[photo.length];
//map 생성
Map<String, Integer> info = new HashMap<>();
// 이름과 점수를 저장
for(int i = 0; i < name.length; i++) {
info.put(name[i], yearning[i]);
}
for(int i = 0; i < photo.length; i++) {
String[] person = photo[i];
int score = 0;
for(int j = 0; j < person.length; j++) {
//이름이 key값에 있으면
if(info.containsKey(person[j])) {
//해당 이름의 점수를 누적
score += info.get(person[j]);
}
}
answer[i] = score;
}
return answer;
}
}
폰켓몬
중복 제거하고 n마리 있을때 n/2마리를 골라 종류를 반환한다 -> hashset사용
문제 귀여워..
import java.util.HashSet;
class Solution {
public int solution(int[] nums) {
int answer = 0;
//선택할 수 있는 개수
int n = nums.length / 2;
HashSet<Integer> set = new HashSet<>();
for(int i = 0; i < nums.length; i++){
set.add(nums[i]);
}
// 서로 다른 개수가 선택할 수 있는 개수보다 크면 결국 n만 선택가능
return answer = n < set.size() ? n : set.size();
}
}
카드 뭉치
동시에 탐색하면 된다.
class Solution {
public String solution(String[] cards1, String[] cards2, String[] goal) {
String answer = "Yes";
int c1 =0;
int c2 =0;
for(String str : goal){
//일치하면 다음 카드로 이동
if(c1 < cards1.length && str.equals(cards1[c1])){
c1++;
} else if(c2 < cards2.length && str.equals(cards2[c2])){
c2++;
} else{
//못찾으면
return "No";
}
}
return answer;
}
}
2016년
요일은 금요일부터 시작해서 1월 8일이 되면 다시 금요일이다 -> 7로 나눈 나머지로 계산하면 요일이 나옴!
class Solution {
public String solution(int a, int b) {
String answer = "";
//2016년은 윤년이라 2월은 29일까지, 1월 1일은 금요일
String[] day = { "FRI", "SAT", "SUN", "MON", "TUE", "WED", "THU" };
int[] date = { 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
//총 날짜만 계산
int days =0;
for(int i = 0; i < a -1; i++){
days += date[i];
}
days += b-1;
return day[days%7];
}
}