[Eulji_LikeLion_2024_BackEnd] 6차 JAVA 연습

6차 목차  

  6-1 JAVA 코테

    1) 연습문제(콜라문제) 

    2) 연습문제(삼총사)

    3) 해시문제(폰켓몬)

 

6-2 풀이 및 Q&A

    1) 연습문제(콜라문제) 

    2) 연습문제(삼총사)

    3) 해시문제(폰켓몬)

6-3 SET

 

6-1. JAVA 코테

이번 세션은 체육대회 일정으로 인해서 잠시 쉬어가는 타임으로 준비하였습니다:)

몇몇분들이 빠져서 원활한 토론이 지장이 있을 것같아서 재밌는 문제로 각자 설명하는 시간을 가져보려고 합니다

문제는 간단하게 3문제를 준비하였습니다

JAVA를 이용하여 문제를 해결하셔야 합니다.

 

1) 연습문제(콜라문제)

코딩테스트 연습 - 콜라 문제 | 프로그래머스 스쿨 (programmers.co.kr)

 

 

2) 연습문제(삼총사)

코딩테스트 연습 - 삼총사 | 프로그래머스 스쿨 (programmers.co.kr)

 

 

3) 해시문제(폰켓몬)

코딩테스트 연습 - 폰켓몬 | 프로그래머스 스쿨 (programmers.co.kr)

 

 

 

 

 

아래에는 풀이가 있습니다

---

 

 

 

 

6-2.  풀이 및 Q&A

1) 연습문제(콜라문제)

Github

해당문제는 N개의 콜라병이 초기에 지급이 되고 A만큼 병을 제출하면 B만큼의 콜라로 돌려주고 계속 가능한 제출하여

총 돌려받을 수 있는 콜라의 갯수를 구하는 문제입니다.

 

즉 매순간 가지고 있는 병을 A로 나누었을경우 몫*B만큼 돌려 받는겁니다.

 

따라서 매반복마다 정답에는 b*(n/a)를 더해주면 되겠네요.

 

answer += b*(n/a);  //n과 a는 int이기 때문에 나눠도 그대로 int값이 나옵니다 따라서 몫과같음

 

그후 바꿀 수 있는 병의 갯수를 다시 정립해야겠죠

방금 받은 갯수에 교환을 하지못한 병울 더하면 현재 보유하고 있는 병의 갯수와 같을 것입니다

즉 방금식에 나머지값을 더하면 해결이 될 것입니다.

n = b*(n/a) +n%a;

 

그후 매번 반복을 해야 하는데 언제 까지 반복해야 할까요

n의 갯수가 a보다 작아 더 이상 변경이 불가능할때까지 해야겠죠

즉, (n>=a)이 만족하지 않을때 탈출하면 됩니다

 

따라서 다음과 같이 해결할 수 있습니다.

class Solution {
    public int solution(int a, int b, int n) {
        int answer = 0;
        while(n>=a){
            answer += b*(n/a);
            n=b*(n/a)+n%a;
        }
         
        return answer;
    }
}

 

 

 

2) 연습문제(삼총사)

Github

해당 문제는 배열에 있는 합을 3개씩 조합했을때 0이되면 삼총사라는 문제로

즉, 조합(Combination) 문제

3개씩 조합하라 했고 주어진 조건에서 3 ≤number의 길이 ≤ 13을 확인했을때

해당 최대 연산 횟수는 13C3 = 286로 나온다

Big-O기준으로 N^3까지 가능하므로 for문을 3중까지 사용가능하다.

시간복잡도	최대 연산 횟수
O(N!)	10
O(2^N)	20~25
O(N^3)	200~300
O(N^2)	3000~5000
O(NlogN)	100만
O(N)	1000~2000만

 

 

그럼 for문을 3중으로 사용가능하기때문에 for문을 이용하여 하나하나 확인하여 해결해도 괜찮겠다.

 

문제 해결을 위한 지식
배열의 길이: 배열이름.length

 

class Solution {
    public int solution(int[] number) {
        int answer = 0;
        for(int i =0; i<number.length-2;i++) {
            for(int j = i+1; j<number.length-1;j++) {
                for(int k =j+1; k<number.length;k++) {
                    if(number[i]+number[j]+number[k] == 0) {
                        answer++;
                    }
                }
            }
        }
        return answer; 
    }
}

 

 

 

3) 해시문제(폰켓몬)

Github

해당문제는 전체 제공하는 N마리중에서 N/2마리를 가져가도 된다라는 조건에서 가져갈 수있는 종류의 최댓값을 구하는 문제입니다.

여기서 문제의 포인트는 중복제거입니다.

 

1. 중복제거를 해서 전체 폰켓몬의 종류를 구합니다.

2. 폰켓몬 종류가  N/2보다 같거나 클경우 각 종류별로 가져간다 해도 N/2를 넘지 못합니다.

3. 폰켓몬 종류가 N/2보다 적을경우 가져갈 수 있는 종류는 폰켓몬 종류의 갯수와 같습니다

 

2번 3번의 예시로 폰켓몬 종류가 A종이라고 했을때 

answer = A>= N/2 ? N/2 : A;
//삼항연산자  조건 ? 참일 경우의 값 : 거짓일 경우의 값

 

 

중복제거는 직접 제거하는 방법에따라 방법이 많습니다

 

1. 값이 존재하는지 검사하여 제거

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        ArrayList<Integer> list = new ArrayList<Integer>(); 
        for(int i =0; i<nums.length;i++) {
            if(!list.contains(nums[i])) //값이 리스트에 있으면 true -> !있어서 false
                list.add(nums[i]);
            }
            return list.size()>nums.length/2 ? nums.length/2 :list.size();
    }
}

 

2. 정렬후에 하나씩 검사하는 방법

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        ArrayList<Integer> list = new ArrayList<Integer>();
        Arrays.sort(nums);  
        for(int i =0; i<nums.length;i++) {
            if(i==0||nums[i]!=list.get(list.size() - 1))
                list.add(nums[i]);
            }
          return list.size()>nums.length/2 ? nums.length/2 :list.size();
    }
}

 

3. Set사용

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        HashSet<Integer> hashSet = new HashSet<>();
            for(int i =0; i<nums.length;i++)
                hashSet.add(nums[i]);        
            return hashSet.size()>nums.length/2 ? nums.length/2 :hashSet.size();
    }
}

 

 

 

6-3.  Set

Set은 비선형 구조로써 인덱스,순서라는 개념이 존재하지 않으며 따라서 중복값이 존재하지 않습니다.

(Null도 요소로 허용)

값을 추가/ 삭제하는 경우에는 Set 내부에 인덱스,순서가 없기 때문에 직접 해당 값을 검색해야한다.

 

HashSet은

Set 인터페이스에서 지원하는 구현 클래스입니다.

Set과 동일하게 순서,인덱스,중복값이 존재 안하고 null도 하나의 요소로 포함시켜줍니다.

 

즉 Set은 중복을 자동으로 제거하여 중복해서 저장할 수 없는 구조이다.

 

해당문제로 Hash문제중 하나인 폰켓몬을 풀어보았습니다

---

이 글은 을지대학교 백엔드 세션 강의를 위해 제작된 게시글입니다 
언제나 조언부탁드립니다