codejcd 기술 블로그

이번 문제는 프로그래머스 사이트에 공개된 문제입니다.

문제

https://programmers.co.kr/learn/courses/30/lessons/12945

분석/설계

피보나치는 작은 범위라면 재귀 호출도 가능하고, 범위가 크다면 다이나믹 프로그래밍이 효율이 좋습니다.

10,000까지의 n의 범위를 보고 다이나믹 프로그래밍을 적용했습니다.

구현 코드

    public BigInteger solution(int n) {
        BigInteger[] d = new BigInteger[n+1];
        d[1] = BigInteger.ONE;
        d[2] = BigInteger.ONE;
  
        for (int i = 3; i <= n; i++) {
            d[i] = d[i - 1].add(d[i - 2]);
        }
        BigInteger T = new BigInteger("1234567");
        BigInteger answer = d[n].remainder(T);
        
        return answer;
    }

정답 코드(다른 사람의 코드와 비교)

    public static int solution(int n) {
        int answer = 0;
        //n이 3일때
        //f(3) = f(1)+f(2) = 1+1 = 2이므로 숫자 초기화
        int num1 = 1;
        int num2 = 1;
        
        if(n==1 || n==2) return 1;
        else {
            for(int i=3; i<=n; i++) {
                answer = (num1+num2)%1234567;
                num1 = num2;//전전수
                num2 = answer;//전수
                
            }
            return answer;
        }
    }

비교

n의 범위만 보고 결과값이 크다는 생각에 BigInteger를 적용하여 처리하였으나

1234567로 나눈 나머지를 리턴하기때문에 굳이 BigInteger를 사용하지

않아도 됩니다. 어쨌든 BigInteger로 코드 제출하여도 만점으로 채점은 됩니다.

정리

아는 문제이고 쉬운 문제라도 끝까지 문제의 조건을 잘 눈여겨봐야 

필요하지 않는 코드 작성을 줄일수 있습니다.

참고

https://programmers.co.kr/learn/courses/30/lessons/12945

이번 문제는 프로그래머스 사이트에 공개된 문제입니다.

문제

https://programmers.co.kr/learn/courses/30/lessons/42839

분석/설계

1. 소수를 몇 개 만들 수 있는지 리턴해야 하므로 소수 구분에 대한 부분은 반드시 포함해야 합니다.

2. numbers에 따른 모든 조합 중 011, 11 같이 중복되는 값이 존재하기 때문에 이런 특정 상태(값)를 제외해야 하며,

   여기서 적절한 알고리즘은 백트래킹 이란 걸 알 수 있습니다.

   백트래킹 알고리즘은 재귀적으로 문제를 하나 풀어나가되 현재 재귀를 통해 확인한 상태가 제한 조건에 해당되지

   않는지 판단하고 해당 상태를 제외하고 다음 단계로 나아가는 방식입니다.

   주의할 점은 시간복잡도에 따른 효율성 제한에 주의해서 사용해야 합니다.

구현 코드

import java.util.HashSet;

public class Main {
	    private static HashSet<Integer> set= new HashSet<>(); // 중복 X, 순서 X
	    private static char[] arr;
	    private static boolean[] visited;
	    
	    public int solution(String numbers) {
	        int answer = 0;
	        arr = new char[numbers.length()]; // 문자열 숫자를 쪼개서 저장.
	        visited = new boolean[numbers.length()];
	        
	        for(int i=0; i<numbers.length(); i++){
	            arr[i]=numbers.charAt(i);
	        }
	        dfs("", 0);
	        
	        answer= set.size();
	        return answer;
	    }
	   
	    public void dfs(String str, int idx){  //가능한 숫자 조합을 찾고 소수여부에 따라 set에 추가
	        int num;
	        if(str!="") { // 빈값일경우 실행하지 않음.
	            num= Integer.parseInt(str);
	            if(isPrime(num)) set.add(num); // 소수 여부 판단하여 추가
	        }
	        
	        if(idx== arr.length) return; // 탐색 중지
	        
	        for(int i=0; i<arr.length; i++){ // 
	            if(visited[i]) continue; // 아래 코드를 실행하지 않고 다음 반복을 시작
	            visited[i]= true;
	            dfs(str+arr[i], idx+1); // 다음 조합에 대해 재귀 탐색
	            visited[i]= false;
	        }
	    }
	    
	    public boolean isPrime(int num){ //소수 판별 O(√N)
	        if(num==1||num==0) return false;
	        for(int i=2; i<=Math.sqrt(num); i++){
	            if(num%i==0) return false;
	        }
	        
	        return true;
	    }
}

정답 코드(다른 사람의 코드와 비교)

import java.util.HashSet;
class Solution {
    public int solution(String numbers) {
        HashSet<Integer> set = new HashSet<>();
        permutation("", numbers, set);
        int count = 0;
        while(set.iterator().hasNext()){
            int a = set.iterator().next();
            set.remove(a);
            if(a==2) count++;
            if(a%2!=0 && isPrime(a)){
                count++;
            }
        }        
        return count;
    }

    public boolean isPrime(int n){
        if(n==0 || n==1) return false;
        for(int i=3; i<=(int)Math.sqrt(n); i+=2){
            if(n%i==0) return false;
        }
        return true;
    }

        public void permutation(String prefix, String str, HashSet<Integer> set) {
        int n = str.length();
        //if (n == 0) System.out.println(prefix);
        if(!prefix.equals("")) set.add(Integer.valueOf(prefix));
        for (int i = 0; i < n; i++)
          permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), set);

    }

}

비교

permutation을 이용하여 처리하는 방법에 차이가 있습니다.

정리

에리토스테네스의 체를 사용하며, 소수 찾기에 효율성이 높고

백트래킹이라는 알고리즘과 백트래킹에 쓰이는 DFS에 대해 다시 한번 살펴봤습니다.

순열조합 풀이 방식은 코드가 아주 간결해 보입니다.

참고

https://programmers.co.kr/learn/courses/30/lessons/42839

이번 문제는 프로그래머스 사이트에 공개된 문제입니다.

문제

https://programmers.co.kr/learn/courses/30/lessons/42840

분석/설계

구현을 위해 나눠서 필요한 것들을 생각해봅니다.

1. 수포자는 3명의 찍는 방식을 저장할 배열 필요.

2. 정답 배열과 수포자 패턴 배열을 비교하여 점수를 저장할 배열 필요.

3. 패턴 비교 시 문제가 10000문제 이므로 수포자 1의 경우 1,2,3,4,5로 길이 5의 패턴이므로 5 이상의

   길이를 가진 문제일 경우 계속 패턴을 반복하여 비교할 수 있게 인덱스를 적절하게 조정해줘야 함.

   3명의 수포자가 각각 패턴이 다르므로 알맞게 조정 필요. 

3. 점수가 담긴 배열에서 최댓값을 구해야 함.

4. 최댓값을 2번 과정에서 저장한 점수 배열과 비교하여 누가 최대 득점자인지 구하여 리턴.

구현 코드

public static int[] solution(int[] answers) {
	int[] score = {0,0,0}; // 응시자 점수를 담을 배열 생성
	ArrayList<Integer> maxScore = new ArrayList<Integer>(); // 최대 점수 담을 ArrayList  
	int[][] patterns = {{1,2,3,4,5}, 
			    {2,1,2,3,2,4,2,5},
			    {3,3,1,1,2,2,4,4,5,5}}; // 응시자 pattern 배열
	
	for(int i = 0; i < answers.length; i++) {
		
		if (patterns[0][i%5] == answers[i]) { // 1번 응시자
			score[0]++;
		}
		if (patterns[1][i%8] == answers[i]) { // 2번 응시자
			score[1]++;
		}
		if (patterns[2][i%10] == answers[i]) { // 3번 응시자
			score[2]++;
		}
	}
	
	int [] sortScore = score.clone();
	Arrays.sort(sortScore);
	int max = sortScore[2]; // 정렬해서 max값을 얻음
	for(int i = 0; i < score.length; i++) {
		if(score[i]==max) {
			maxScore.add(i+1); // 인덱스 저장
		}
	}
	
	int[] answer = new int[maxScore.size()];
	for(int i = 0; i < answer.length; i++) {
		answer[i] = maxScore.get(i);
	}
return answer;

정답 코드(다른 사람의 코드와 비교)

    public int[] solution(int[] answer) {
        int[] a = {1, 2, 3, 4, 5};
        int[] b = {2, 1, 2, 3, 2, 4, 2, 5};
        int[] c = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
        int[] score = new int[3];
        for(int i=0; i<answer.length; i++) {
            if(answer[i] == a[i%a.length]) {score[0]++;}
            if(answer[i] == b[i%b.length]) {score[1]++;}
            if(answer[i] == c[i%c.length]) {score[2]++;}
        }
        int maxScore = Math.max(score[0], Math.max(score[1], score[2]));
        ArrayList<Integer> list = new ArrayList<>();
        if(maxScore == score[0]) {list.add(1);}
        if(maxScore == score[1]) {list.add(2);}
        if(maxScore == score[2]) {list.add(3);}
        return list.stream().mapToInt(i->i.intValue()).toArray();
    }

비교

1. 정답과 수포자 패턴 비교

   정답과 패턴 비교 시 패턴 길이를 하드코딩을 했는데 문제의 수포자가 3명으로 제한되어있지만

   N명일 경우 패턴 배열의 length 메서드를 써서 풀어야 합니다.

2. 최대 값 구하기

   최대 값을 구하기 위해 Math 클래스의 max를 사용했고 저같은 경우 Arrays 클래스의 sort 메서드를

   사용하여 최댓값을 구했습니다.

   참고로 Arrays.sort 메서드의 경우 내부 정렬을 위해 기본 자료형은 Quick sort 그리고 객체는 Tim sort

   를 사용합니다.

   Tim Sort는 참고에 Naver D2 글을 참고하면 도움이 될 것 같습니다.

3. 결괏값 배열 리턴

   제 코드에서는 ArrayList의 꺼내어 정답 배열(최대 득점 자) 옮기기 위해 for 문을 사용했는데요.

   다른 사람 코드는 stream을 mapToInt 메서드를 활용하여 Int Stream으로 전환 후 toArray 메서드로

   배열로 리턴할 수 있게 처리하였습니다.

정리

Stream을 JDK 8부터 소개되었는데 배열, 컬렉션을 다루고 여기서 특정 값을 탐색할 때 아주 유용합니다.

람다를 이용해서 코드량을 많이 줄 일수 있습니다.

익숙한 for 문을 사용한 접근 대신 stream으로 접근도 많이 시도해봐야 해봐야 할 것 같습니다.

stream 관련해서는 잘 정리된 블로그 글이 있어 참고에 링크했습니다.

참고

https://programmers.co.kr/learn/courses/30/lessons/42840

https://d2.naver.com/helloworld/0315536

https://futurecreator.github.io/2018/08/26/java-8-streams/

최근에 코딩 테스트를 오랜만에 접할 기회가 있었다.

이미 현재 다니고 있는 회사에 근무한 지 오래됐기 때문에 코딩 테스트 자체를 몇 년 만에 보게 되었다.

SQL 문제는 계속 꾸준히 실무에 접하고 있는 부분이기 때문에 별도의 준비조차 하지 않았지만 아주 쉽게 풀렸다.

자바 알고리즘 문제는 생각보다 난이도가 있었고 바짝 며칠간 준비는 했지만 준비 부족인지 풀기가

매우 어려웠다.

현업에서 자바로 계속 코딩은 하지만 생각해보면 알고리즘을 고민해서 쓸 만큼의 문제들은 많지가 않았던 것 같다.

MVC model로 나눠진 레이어에 try~catch~exception 처리, 트랜잭션 처리, 비즈니스 구현으로 제한적이었던 것 같다.

하루에 1-2문 제정 도라도 알고리즘 테스트를 위해 꾸준히 문제 풀이를 할 필요가 있는 것 같다.

물론 누군가는 경력은 무슨 그런 거 준비하고 그게 현업에서 쓸모가 있냐고 하겠지만

어쨌든 문제 해결을 위한 사고를 측정하는 방법이 한정된 시간 내에서는 이 방법밖에 없지 않은가 싶다.

요새는 과제 테스트도 있다고 하지만 과제 테스트도 결국 한계는 있다고 본다.

하여튼 꾸준히 준비를 해야겠다.

꾸준히 준비를 해야 할 목록에 또 하나가 늘었다.

1. 소개

JAVA 진영의 ORM 표준.

스프링 기반의 실무에서는 Spring Data JPA를 주로 사용하여 개발하며 Hibernate 구현체를 대부분 많이 사용합니다.

JPA, Spring Data JPA, Hibernate 관계에 대해 조금 쉽게 설명하면 Hibernate는 JPA 구현체이고

Spring Data JPA는 Spring 프레임워크에서 JPA를 다루기 쉽게 구현된 것이라 생각하면 됩니다.

Spring Data JPA는 Hibernate만을 구현체로 사용하지 않고 여러 다른 구현체를 선택할 수 있습니다.

하지만 대부분 Hibernate를 구현체로 사용하고 있기때문에

이런 관계에 대해서 많이 혼동이 있는 분들이 많은 것 같습니다.

JPA, Spring Data JPA, Hibernate 가 혼동된다면 아래 이미지를 보며 어느 정도 관계에 대해서 이해가 쉬울 것 같습니다.

2. ORM(Object-relational mapping) 

객체와 관계형 데이터베이스를 맵핑하는 기술.

객체는 객체대로 설계하고 RDBMS는 RDBMS대로 설계하고 ORM 프레임워크가 중간에서 맵핑.

3. 기존 SQL 중심 개발의 문제점

public Class User {
	private String userId;
    private String userName;
    private String email;
    private UserGroup userGroup;
}

public Class UserGroup {
	private String groupId;
    private String name;
}

두 개의 참조 관계의 객체들이 있다면 조인하여 데이터를 얻을 수 있는

SQL을 조회 개발이 필요하고 SQL문의 조회 결과를 각각의 두 개의 객체에 결과를 다음과 같이 맵핑해줘야 합니다.

SELECT U.*, UG.*
  FROM USER U JOIN USER_GROUP UG ON U.groupId = UG.groupId

public User findUser(String userId) {
	// SQL 실행 결과를 아래의 객체에 세팅
    User user  = new User();
    user.setUserName(name);
    		...
    UserGroup userGroup = new UserGroup();
    user.setGroupName(name);
    		...
    // 회원과 그룹의 관계 세팅
    user.setUserGroup(userGroup);
    return user;
}

이런 맵핑 작업이 계속 필요하기 때문에 생산성이 떨어지다 보니 하나의 객체로 처리할 수 있게 DTO를 만들어서

조회 결과에 대해 setter/getter 처리하는 경우 많습니다.

그런데 이런 경우 SQL 문에 SELECT 필드에 따라서 데이터가 있을 수도 없을 수도 있는 경우가 발생하게 됩니다.

그러다 보니 일반적으로 MVC model을 사용하여 계층적으로 분리를 많이 하지만 논리적으로는 얽혀있는 상태가 되면서

SQL 문까지 전부 확인하기 전까지는 슈퍼 DTO(객체)의 데이터가 없어서 안 들어간 것인지 필요가 없어서 뺀 것인지

신뢰하기 어렵기 때문에 여기서 또 개발에 생산성과 유지보수가 점점 어려워지게 됩니다

문제는 객체지향 모델링할수록 이런 맵핑 작업이 늘어나게 되고

그러다 보니 SQL 문에 맞춰서 객체를 설계하는 경우가 많아지게 되면서 생산성은 떨어지게 되는 악순환이 반복됩니다.

또 다른 경우를 확인해보면 예를 들어 어떤 기능을 개발한다고 가정하면 관련 CRUD SQL에 생성이 필요하고

이렇게 생성한 상태에서 DB 테이블에 칼럼 하나가 추가된다고 하면 관련된 SQL 문 모두 수정 필요합니다.

번거롭고 생산성이 떨어지는데 혹시 실수로 하나라도 추가나 수정해야 할 필드를 SQL문에서

놓치게 되면 에러가 발생하게 됩니다.

4. JPA를 활용한 해결

이런 문제들에 대해서는 JPA는 솔루션이될 수 있습니다.

별도의 SQL 문 작성 없이 객체 관계 설정을 통해 SQL 문을 생성해주므로 단순히 JPA에 정의한 CRUD 메서드를 

사용하여 생산성을 높일 수 있습니다.

지연 로딩 기능을 활용해 조인 관계 놓인 객체 데이터라고 해도 객체가 조회되는 시점에 SQL을 생성/조회할 수 있고

만약 항시 채워진 데이터가 필요할 경우 옵션 설정을 통한 즉시 로딩 기능으로 데이터를 모두 하나의 SQL을 생성/조회할 수 있습니다.  이런 기능을 활용하여 맵핑을 위한 복잡한 추가 코딩을 줄일 수 있습니다.

모든 부분이 직접적인 SQL 작성 없이 처리할 수 없는 경우를 처리하기 위한 SQL과 유사한 JPQL를 사용하여 조회할 수 있게 만든 기능도 있습니다.

5. 마치며

간단하게 개념과 기존 SQL 중심 개발의 문제점과 JPA에 어떤 해결방법이 있는지 확인해보았습니다.

다음 글에서는 영속적 콘텍스트와 4번 항목에서 말한 지연 로딩 같은 솔루션에 대한 예제를 살펴보겠습니다.

※ 참고

https://docs.jboss.org/hibernate/orm/5.4/userguide/html_single/Hibernate_User_Guide.html

https://suhwan.dev/2019/02/24/jpa-vs-hibernate-vs-spring-data-jpa/ 

자바 ORM 표준 JPA 프로그래밍 / 김영한 저자

알고리즘 문제를 구현한 코드와 정답을 비교해보도록 하겠습니다.

문제

알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어집니다.

이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에,

그 뒤에 모든 숫자를 더한 값을 이어서 출력합니다.

입력 조건
문자열 S (1 <= S의 길이 <= 10000)

입력 예시1
K1KA5CB7

출력 예시1
ABCKK13

입력 예시2
AJKDLSI412K4JS9D

출력 예시2
ADDIJJJKKLSS20

구현을 위해 나눠서 필요한 것들을 생각해봅니다.

1. 문자열을 입력받기 위한 코드가 필요.

2. 입력받은 문자열은 알파벳 대문자와 숫자로 구성되는 제약이 있는데 알파벳을 오름차순으로 정렬 필요.

   따라서 알파벳과 숫자 분리 필요.

3. 분리한 숫자 문자열은 숫자로 변환하여 합을 구함.

4. 정렬된 알파벳 문자열과 숫자를 합친 문자열을 만들어 출력.

구현 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main  {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String S = scanner.next(); // 시스템 입력을 받아 문자열 저장 
		char tempArr[] = S.toCharArray(); // 문자열을 Char 형의 Array로 변환
		int num = 0; 
		String str = "";
		
		Arrays.sort(tempArr); // 오름 차순 정렬
		
		for(int i=0; i<tempArr.length; i++) {
			// 대문자 A~Z 일 경우에 문자열을 str 변수에 추가.
			if(tempArr[i] -'A' >= 0 && tempArr[i]-'Z' <= 0) {
				str += tempArr[i];
			} else { // 아닐 경우 숫자를 따로 더한다.
				num += tempArr[i] - '0';
			}
		}
		
		if(num != 0) { // 알파벳 단독 구성인 경우를 구분하여 출력
			System.out.println(str + num);
		} else {
			System.out.println(str);
		}
		scanner.close();
	}
}

정답 코드

import java.util.*;

public class Main {

    public static String str;
    public static ArrayList<Character> result = new ArrayList<Character>();
    public static int value = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        str = sc.next();

        // 문자를 하나씩 확인하며
        for (int i = 0; i < str.length(); i++) {
            // 알파벳인 경우 결과 리스트에 삽입
            if (Character.isLetter(str.charAt(i))) {
                result.add(str.charAt(i));
            }
            // 숫자는 따로 더하기
            else {
                value += str.charAt(i) - '0';
            }
        }

        // 알파벳을 오름차순으로 정렬
        Collections.sort(result);

        // 알파벳을 차례대로 출력
        for (int i = 0; i < result.size(); i++) {
            System.out.print(result.get(i));
        }

        // 숫자가 하나라도 존재하는 경우 가장 뒤에 출력
        if (value != 0) System.out.print(value);
        System.out.println();
    }
}

비교

1. 정렬
제가 작성한 코드의 경우 문자열 입력 후 Char 형 Array 전환 후 바로 정렬했다는 점이고
정답의 경우 알파벳 문자를 분리하여 정렬하였습니다. 
따라서 여기서 정렬할 문자 길이에 따른 시간 차이가 발생합니다.

2. 알파벳 문자인지 확인하기 위한 코드
알파벳 문자인지 구분을 위해 Character isLetter 메소드를 사용했다는 점입니다.

3. for문 사용
제가 작성한 코드의 경우 알파벳 문자와 숫자 문자를 구분 및 변수에 저장하기 위해 1번 사용.
정답의 경우 알파벳 출력을 위해 for문을 한번 더 사용하여 총 2번을 사용합니다.

정리

정답에서 char문자 구분을 위해 사용한 메소드 외에 알파벳 문자만을 위한 메서드와 숫자를 구분하는 메서드가
있어서 정리해봅니다.

1. Character isLetter 메서드
    char 값이 문자인지 판단하여 true / false를 리턴.

2.  Character isDigit 메서드
    char 값이 숫자인지 판단하여 true / false를 리턴.

3.  Character isAlphabetic 메서드
    char 값이 알파벳 문자인지 판단하여 true / false를 리턴

참고

https://www.baeldung.com/java-character-isletter-isalphabetic
https://github.com/ndb796/python-for-coding-test/blob/master/12/2.java