Daily Coding - 28번
괄호의 짝이 맞는지 확인하시오.
public boolean balancedBrackets(String str) {
if(str == null) return true;
StringBuffer str2 = new StringBuffer(str);
if(str.contains("[")||str.contains("{")||str.contains("(")){
for(int i=0; i<str2.length(); i++){
if(str2.charAt(i)=='['){
boolean isclosed = false;
for(int j=i; j<str.length(); j++){
char jchar = str.charAt(j);
if(jchar=='}'||jchar==')')return false;
else if (jchar==']') {
isclosed =true;
str2.deleteCharAt(j);
break;
}
}
if(isclosed==false) return false;
}
if(str2.charAt(i)=='('){
boolean isclosed = false;
for(int j=i; j<str2.length(); j++){
char jchar = str2.charAt(j);
if(jchar=='}'||jchar==']')return false;
else if (jchar==')') {
isclosed =true;
str2.deleteCharAt(j);
break;
}
}
if(isclosed==false) return false;
}
if(str2.charAt(i)=='{'){
boolean isclosed = false;
for(int j=i; j<str2.length(); j++){
char jchar = str2.charAt(j);
if(jchar==']'||jchar==')')return false;
else if (jchar=='}') {
isclosed =true;
str2.deleteCharAt(j);
break;
}
}
if(isclosed==false) return false;
}
}
return true;
}
return false;
}
//입력
"[[[{{{((()))}}}]]]" "[(]{)}"
//출력
false true
//정답
true false위와 같이 오류는 case의 경우의 수에 대한 처리를 빼먹었다.
public boolean balancedBrackets(String str) {
if(str == null) return true;
StringBuffer str2 = new StringBuffer(str);
//String[] s = {"[","]","{","}","(",")"}; // 배열이용해서 하면 조금 더 간단할듯
if(str.contains("[")||str.contains("{")||str.contains("(")){
for(int i=0; i<str2.length(); i++){
if(str2.charAt(i)=='['){
boolean isclosed = false;
for(int j=i; j<str.length(); j++){
char jchar = str.charAt(j);
if(jchar=='}'){
if(str2.indexOf("{")>j||str2.indexOf("{")==-1) { //여는 괄호가 더 뒤에 있거나 없으면
return false;
}
}else if(jchar==')'){
if(str2.indexOf("(")>j||str2.indexOf("(")==-1) { //여는 괄호가 더 뒤에 있거나 없으면 false
return false;
}
}
else if (jchar==']') {
isclosed =true;
str2.deleteCharAt(j);
break;
}
}
if(isclosed==false) return false;
}
if(str2.charAt(i)=='('){
boolean isclosed = false;
for(int j=i; j<str2.length(); j++){
char jchar = str2.charAt(j);
if(jchar=='}'){
if(str2.indexOf("{")>j||str2.indexOf("{")==-1) { //여는 괄호가 더 뒤에 있거나 없으면
return false;
}
}else if(jchar==']'){
if(str2.indexOf("[")>j||str2.indexOf("[")==-1) { //여는 괄호가 더 뒤에 있거나 없으면 false
return false;
}
}
else if (jchar==')') {
isclosed =true;
str2.deleteCharAt(j);
break;
}
}
if(isclosed==false) return false;
}
if(str2.charAt(i)=='{'){
boolean isclosed = false;
for(int j=i; j<str2.length(); j++){
char jchar = str2.charAt(j);
if(jchar==']'){
if(str2.indexOf("[")>j||str2.indexOf("[")==-1) { //여는 괄호가 더 뒤에 있거나 없으면
return false;
}
}else if(jchar==')'){
if(str2.indexOf("(")>j||str2.indexOf("(")==-1) { //여는 괄호가 더 뒤에 있거나 없으면 false
return false;
}
}
else if (jchar=='}') {
isclosed =true;
str2.deleteCharAt(j);
break;
}
}
if(isclosed==false) return false;
}
}
return true;
}
return false;
}
//입력
"[(]{)}"
//출력
true
//정답
false
문제가 요구하는 로직이 뭔지 문제 자체를 이해하지 못한 것 같다.
위에 실패한 입력예시 "[(]{)}"는 열린만큼 닫혔는데 이게 왜 false가 나와야한는지 이해가 안됐었다.
문제에서 요하는바는 괄호안에 괄호가 열리고 닫혀야만 한다는 뜻 같다.
public boolean balancedBrackets(String str) {
if(str.equals(null)||str.equals("")) return true;
StringBuffer str2 = new StringBuffer(str);
//String[] s = {"[","]","{","}","(",")"}; // 배열이용해서 하면 조금 더 간단할듯
if(str.charAt(0)=='{'||str.charAt(0)=='['||str.charAt(0)=='('){
for(int i=0; i<str2.length(); i++){
if(str2.charAt(i)=='['){
boolean isclosed = false;
for(int j=1; j<str2.length()-i; j++){
char jchar = str.charAt(str2.length()-j);
if (jchar==']') {
String test = str2.substring(i+1, str2.length()-j);
isclosed =balancedBrackets(test);
i=str2.length()-j;
break;
}
}
if(isclosed==false) return false;
}
if(str2.charAt(i)=='('){
boolean isclosed = false;
for(int j=1; j<str2.length()-i; j++){
char jchar = str.charAt(str2.length()-j);
if (jchar==')') {
String test = str2.substring(i+1, str2.length()-j);
isclosed = balancedBrackets(test);
i=str2.length()-j;
break;
}
}
if(isclosed==false) return false;
}
if(str2.charAt(i)=='{'){
boolean isclosed = false;
for(int j=1; j<str2.length()-i; j++){
char jchar = str.charAt(str2.length()-j);
if (jchar=='}') {
String test = str2.substring(i+1, str2.length()-j);
isclosed =balancedBrackets(test);
i=str2.length()-j;
break;
}
}
if(isclosed==false) return false;
}
}
return true;
}
return false;
}
//입력
"( ( ))()(( ) )"
//출력
true
//정답
false정말 쉽지 않다...
열린 괄호와 닫힌괄호를 제대로 짝지어서 뺴지 못했기 때문에 발생한 오류다.
열리는 괄호와 닫히는 괄호를 짝지을 방법을 더 생각해봐야겠다.
public boolean balancedBrackets(String str) {
str = str.replaceAll("[^\\[\\]{}\\(\\)]", ""); // 괄호를 제외한 문자 삭제
if (str == null || str.equals("")) return true;
StringBuffer str2 = new StringBuffer(str);
char[] open = {'[', '{', '('};
char[] close = {']', '}', ')'};
for(char c : close) {
if (str.charAt(0) == c) return false;
}
for (int k = 0; k < 3; k++) {
for (int i = 0; i < str2.length(); i++) {
if (str2.charAt(i) == open[k]) {
boolean isclosed = false;
for (int j = i + 1; j < str2.length(); j++) {
char jchar = str2.charAt(j);
if (jchar == open[k]) {
StringBuffer test = str2.deleteCharAt(i);
isclosed = balancedBrackets(test.toString());
} else if (jchar == close[k]) {
StringBuffer test = str2.deleteCharAt(j).deleteCharAt(i);
isclosed = balancedBrackets(test.toString());
}
}
if (!isclosed) return false;
}
}
}
return true;
}이것도 오류투성이...그냥 처음부터 방법을 새롭게 생각해봐야겠다.
이렇게 괄호의 위치를 숫자로 나타내고 수학문제다 생각하고 규칙을 고민해 봤다.
가장 마지막에 있는 열린괄호를 기준으로 짝을 찾아서 지워나가면 될 것 같다.
public boolean balancedBrackets(String str) {
if (str == null || str.equals("")) return true;
str = str.replaceAll("[^\\[\\]{}\\(\\)]", ""); // 괄호를 제외한 문자 삭제
// StringBuffer str2 = new StringBuffer(str);
char[] open = {'[', '{', '('};
char[] close = {']', '}', ')'};
for (int j=0; j<3; j++) {
List<Integer> openList = new ArrayList<>();
List<Integer> closeList = new ArrayList<>();
for (int i = 0; i < str.length(); i++) {
if(str.charAt(i)==open[j]) openList.add(i);
else if(str.charAt(i)==close[j]) closeList.add(i);
}
if(openList.size() != closeList.size()) return false; // 열린괄호와 닫힌괄호의 갯수가 다르면 return false
Map<Integer,Integer> willBeDelete = new LinkedHashMap<>(); // 짝지은 괄호들을 삭제하기 위해 사용
while (openList.size()!=0 && closeList.size()!=0){
int openMax = Collections.max(openList);
int closeMax = Collections.max(closeList);
if(openMax>closeMax) return false; // 열린 괄호로 끝나면 false
int sltom = 0;// smallestLargerThanOpenMax의 약자
for (int value : closeList) {
if (value > openMax) { // openMax보다 큰 값들 중
if (sltom == 0 || value < sltom) { // 가장 작은 값 찾기
sltom = value;
}
}
}
if( sltom-openMax!=1 && !balancedBrackets(str.substring(openMax+1, sltom))) return false; // 연결된 괄호 사이의 문자열이 괄호가 짝지어져 있지 않으면 false
openList.remove(Integer.valueOf(openMax));
closeList.remove(Integer.valueOf(sltom));
}
}
return true;
}모든 테스트케이스에 통과했다.
다만 코드를 구현하다보니 짝지어진 괄호를 삭제하다 보면 구해놨던 인덱스의 값이 계속 바뀌어야하는 상황이 생겨 복잡해 졌다. 단순하게 괄호 내부를 불필요한 반복이라도 추가로 반복하며 확인해 기능을 수행하는데 문제는 없게 할 수 있었지만 시간복잡도면에서 매우 안좋다.
열린괄호가 시작되면, 이후로 다른 종류의 닫힌 괄호가 바로 나올 수 없다는 아이디어를 중심으로 다시 코드를 짜보면 아래 두 코드와 같이 시간복잡도를 많이 줄일 수 있다.
public boolean balancedBrackets2(String str) {
Stack<Character> stack = new Stack<>(); // 먼저 들어간 요소가 나중에 나오는 stack을 활용
HashMap<Character, Character> opener = new HashMap<>();
opener.put('{', '}');
opener.put('[', ']');
opener.put('(', ')');
String closer = "}])";
for(int i = 0; i < str.length(); i++) {
if(opener.containsKey(str.charAt(i))) { // 열린괄호일 경우
stack.push(str.charAt(i)); // stack에 추가
} else if(closer.indexOf(str.charAt(i)) != -1 && stack.size() > 0) { //닫힌괄호이며 스택이 비어있지 않은 경우 즉, 열린괄호가 나온 이후에 닫힌괄호가 나온 경우
char top = stack.pop();
char pair = opener.get(top);
if(pair != str.charAt(i)) { // 다른 종류의 닫힌 괄호가 나오면 false
return false;
}
} else { // stack이 비어있는데 닫힌 괄호가 나왔다? = false
return false;
}
}
return stack.size() == 0; // 남는 stack이 있다면 짝지지지 못하는 괄호가 남은거니 false 남은게 없이 위 과정을 거치면 다 제대로 짝지어진 것이니 true
} public boolean balancedBrackets3(String str) {
if (str == null || str.equals("")) {
return true;
}
Stack<Character> stack = new Stack<>();
for (char c : str.toCharArray()) {
if (c == '(' || c == '[' || c == '{') { // 열린괄호면 stack에 담아두고
stack.push(c);
} else if (c == ')' || c == ']' || c == '}') { // 단힌괄호면 담겨져 있는 열린괄호가 있는지 확인
if (stack.isEmpty()) { // 없으면 false
return false;
}
char top = stack.pop(); // 있으면 저장해둔 열린괄호 꺼내서
if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) { // 열린괄호가 시작되면, 이후로 다른 종류의 닫힌 괄호가 바로 나올 수 없다.
return false;
}
}
}
return stack.isEmpty();
}Daily Coding - 29번
2xn 보드의 2x1 타일을 깔 수 있는 경우의 수를 구하시오
경우의 수를 생각해 보면 num일 때의 경우의 수는 num-1때의 경우의 수와 num-2때의 경우의 수를 합친 것과 같다.
이전에 했던 피보나치와 매우 유사하다.
public int tiling(int num) { // 2xn 보드의 2x1 타일을 깔 수 있는 경우의 수를 구하시오
List<Integer> list = new ArrayList<>();
list.add(0);
list.add(1);
list.add(2);
return tile(num, list);
}
public int tile(int num, List<Integer> list){
if(list.size()<=num) {
list.add(tile(num-1, list) + tile(num-2, list));
}
return list.get(num);
}모든 테스트케이스 통과
Daily Coding - 30번
부분적으로 오름차순 정렬 된 배열에서 target을 요소로 갖는 인덱스 위치를 찾아라.
시간복잡도를 최대한 줄여 O(logN)으로 구해보자.
public int rotatedArraySearch(int[] rotated, int target) { // 부분적으로 오름차순 정렬 된 배열에서 target을 요소로 갖는 인덱스 위치를 찾기
for(int i=0; i<rotated.length; i++){
if(rotated[i]>target&&(rotated[i]-target)>rotated.length/2) break;
if(rotated[i]==target) return i;
}
for(int i=rotated.length-1; i>=0; i--){
if(rotated[i]==target) return i;
}
return -1;
}// 이것도 결국엔 O(N)이다..이진탐색트리를 활용해보자.
public int rotatedArraySearch2(int[] rotated, int target) {
int left = 0;
int right = rotated.length - 1;
while(left <= right) {
int middle = (right + left) / 2;
if(rotated[middle] == target) {
return middle;
}
if (rotated[left] < rotated[middle]) {
if (target < rotated[middle] && rotated[left] <= target) {
right = middle - 1;
} else {
left = middle + 1;
}
} else {
if (target <= rotated[right] && rotated[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
}
return -1;
}[Spring MVC] JPA 기반 데이터 액세스 계층
JPA(Java Persistence API)
개념정리
JPA(Java Persistence API)
- Java 진영에서 사용하는 ORM(Object-Relational Mapping) 기술의 표준 사양(또는 명세, Specification)
- Entity를 영구 저장하는 환경
사용기능
EntityManager 클래스
-
엔티티를 관리하는 다양한 기능(메서드)를 갖고 있는 클래스.
-
JPA의 영속성 컨텍스트는
EntityManager클래스에 의해서 관리 됨. -
여러 스레드가 동시에 접근하게 되면 동시성 문제(두 스레드가 값을 동시에 바꾸다 오류가 나는 등의 문제)가 발생하지 않도록 하나의
EntityManager클래스로 엔티티를 관리하면 안된다.
(즉, 상황에 따라EntityManagerFactory를 이용해 계속 만들어줘야 함) -
persist()메서드 = 영속성 컨텍스트에 엔티티 객체 정보를 저장하는 메서드(DB에 저장하는 것 x)- 1차 캐쉬에 엔티티 객체가 저장되고, 쿼리문(쓰기 지연 SQL) 저장소에 INSERT 쿼리 형태로 등록 된다.
-
find(조회 할 엔티티 클래스의 타입, 조회 할 엔티티 클래스의 식별자 값)메서드 = 영속성 컨텍스트에 저장된 객체를 가져오는 메서드- 만약 1차 캐시에 찾으려는 객체가 없으면 DB 테이블에 SELECT 쿼리를 전송해서 조회한다.
-
flush()메서드 = 영속성 컨텍스트의 변경 사항을 테이블에 반영할 수 있다.commit()을 호출하면 내부적으로flush()가 호출된다.
EntityTransaction 클래스
commit()메서드 = Persistence Context에 있는 객체를 DB에 저장하는 메서드- DB저장 후에도 Persistence Context에 있는 1차 캐시에는 객체 정보가 남음
- 쓰기 지연 SQL 저장소(쿼리문 저장소)에는 객체 정보가 남지 않음
commit()을 호출하면 내부적으로flush()가 호출된다.
- 엔티티를 관리하는
EntityManager를 찍어내 만드는 클래스 createEntityManager()메서드 =EntityManager객체 생성하는 메서드
1차캐시 + DB 테이블에 저장하는 방법
Transaction 클래스을 이용한다.
- Transaction을 시작하기 위해서
begin()메서드를 먼저 호출해야 한다. persist()메서드를 이용해 엔티티 객체를 Persistence Context에 저장commit()메서드를 사용해 Persistence Context에 저장되어 있는 객체를 DB 테이블에 저장- DB저장 후 1차캐시에는 객체가 남아있지만 쿼리 저장소에서는 삭제 됨
DB에 저장한 객체 수정(UPDATE)
위와 같이 begin() -> persist() -> commit()순으로 DB 테이블에 저장해 둔 정보를 수정하는 방법.
find()메서드를 이용해 수정하려는 데이터 조회- setter 메서드로 정보 변경
- 다시
commit()
DB에 저장한 객체 삭제(DELETE)
위와 같이 begin() -> persist() -> commit()순으로 DB 테이블에 저장해 둔 정보를 삭제하는 방법.
find()메서드를 사용해 삭제하려는 데이터 조회remove()메서드를 사용해 1차 캐시에 있는 엔티티를 제거를 요청commit()메서드를 사용해 1차 캐시에 있는 엔티티를 제거하고, 쓰기 지연 SQL 저장소에 등록된 DELETE 쿼리 실행
JPA 엔티티(Entity) 매핑과 연관 관계 매핑
엔티티와 테이블 간의 매핑
@Entity
- JPA 관리 대상 엔티티가 되게 함
@Entity(name = "entityName")과 같이 이름 지정 가능- 이름 기본값 = 클래스명
@Id애너테이션을 필수로 추가해야 함
@Table(name = "tableName")
- 엔티티와 매핑할 테이블을 지정
- 주로 테이블명을 클래스명과 다르게 지정하는데 사용 (옵션 o 필수 x)
- 이름 기본값 = 클래스명
기본키 매핑
기본키 직접 할당 전략
@Id애너테이션만 추가
기본키 자동 생성
-
IDENTITY = 기본키 생성을 데이터베이스에 위임하는 방법
@Id+@GeneratedValue(strategy = GenerationType.IDENTITY)commit을 안해도persist만 해도 DB에 반영된다.
-
SEQUENCE = 데이터베이스에서 제공하는 시퀀스를 사용해서 기본키를 생성하는 방법
@Id+@GeneratedValue(strategy = GenerationType.SEQUENCE)persist+commit을 해야 DB에 반영 된다.
-
TABLE = 별도의 키 생성 테이블을 사용하는 방법
- 거의 사용X
-
AUTO = JPA가 데이터베이스의 Dialect에 따라서 적절한 방법을 자동으로 선택해서 기본키 생성
@Id+@GeneratedValue(strategy = GenerationType.AUTO)
필드(멤버 변수 )와 컬럼 간의 매핑
@Column(nullable = false, updatable = false, unique = true, length = 10)
- 필드와 컬럼을 매핑해주는 애너테이션
- nullable = null 값을 허용여부
- 기본값 = true
- updatable = 컬럼 데이터 수정 가능여부
- 기본값 = true
- unique = 고유값으로 설정할지에 대한 여부
- 기본값 = false
- length = 컬럼에 저장할 수 있는 문자 길이를 지정
- 디폴트값 = 255
그냥
@Column만 쓰면 기본값으로 설정되니 주의
@Column을 생략하면 nullable=false가 된다.
@Transient
- 테이블 컬럼과 매핑하지 않겠다는 의미
- DB에 저장되지 않고, 조회할 때 역시 매핑되지 않는다.
- 주로 임시 데이터를 메모리에서 사용하기위한 용도로 사용
@Enumerated
- enum 타입과 매핑할 때 사용하는 애너테이션
- 두가지 타입이 있음
@Enumerated(EnumType.ORDINAL)= enum의 순서를 나타내는 숫자를 테이블에 저장- 기존에 정의되어 있는 enum 사이에 새로운 enum 하나가 추가하면 enum에 정의되어 있는 순서가 일치하지 않게 되는 문제가 발생
@Enumerated(EnumType.STRING)= enum의 이름을 테이블에 저장
엔티티와 테이블 매핑 권장 사용 방법
-
클래스 이름 중복 등의 특별한 이유가 없다면 @Entity와 @Id 애너테이션만 추가하자
@Table애너테이션으로 테이블명 지정 가능
-
기본키 생성은 DB에서 지원해주는 AUTO_INCREMENT 또는 SEQUENCE를
이용할 수 있도록 IDENTITY 또는 SEQUENCE 방식을 사용하자 -
@Column정보를 명시적으로 모두 지정하자. (유지보수 가시성 좋아짐) -
엔티티 클래스 필드 타입이 Java의 원시타입일 경우,
@Column애너테이션을 생략하지 말고, 최소한 nullable=false 설정은 하자 -
@Enumerated애너테이션을 사용할 때EnumType.STRING으로 쓰자.
엔티티 간의 연관 관계 매핑
풀코드 GitHub주소 (외부인 조회 불가)
joincolum과 mappedby의 차이
joincolum
- joincolum을 사용한 엔티티가 관계의 주인인 것이다.
- 단방향 연결을 위해 사용. (
mappedby에 의한 추가관계가 이루어지면 양방향이 될 수 있음) - 참조한 colum을 갖고있다.
- 연관관계의 주인인 entity에서 사용하는 것
mappedby
- 참조된 엔티티를 참조하기 위해 사용한다.
- 양방향 관계로 만드는데 사용
- 자기 자신인 entity 객체를 참조한 엔티티와의 연관관계를 맺기 위해 사용하는 것
- 참조한 객체의 colum을 갖고있지 않다.
- 연관관계의 주인이 아닌 entity에서 사용하는 것
연관관계의 주인이라 함은 참조한 객체의 colum을 갖고 있는지의 여부로 판단하면 된다.
테이블관점의 스키마, 객체관점의 스키마
테이블 관점의 스키마
객체관점의 스키마
연관관계는 객체참조로 이루어진다.
따라서 연관관계에 대한 객체 참조구조는 테이블 관점의 스키마에서 직관적으로 알기 어렵다.
테이블 괌점의 스키마를 머릿속에 그리고 코드를 구현한다고 하면 각 변수들을 설정함과 동시에 연관관계에 대한 생각을 일일히 판단하며 코드를 구현해야하기 때문에 실수를 할 수 있는 확률이 올라간다고 생각한다.
따라서 객체관점으로 코딩할 구조를 정리해 그려보고 코드를 구현하는게 좋을 것 같다.
Spring Data JPA를 통한 데이터 액세스 계층 구현
JPA vs Hibernate ORM vs Spring Data JPA
JPA(Java Persistence API)
- 관계형 데이터베이스를 사용하기 위해 정해 놓은 표준 스펙(사양 또는 명세, Specification)
- "이 기술은 뭐고~ 이 기술은 이렇게 이렇게 구현해서 쓰면 돼" 라고 적어 놓은 기술 명세
Hibernate ORM
- JPA라는 표준 스펙을 구현한 구현체
- 실제로 사용하는 API
Spring Data JPA
- JPA 스펙을 구현한 구현체의 API(일반적으로 Hibernate ORM)를 조금 더 쉽게 사용할 수 있도록 해주는 모듈
사용기능
@Enumerated
- Spring Data API에서 열거형(Enum) 타입의 필드를 매핑할 때 사용
@Enumerated(value = EnumType.STRING)- 열거형을 문자열로 저장
@Enumerated(value = EnumType.ORDINAL)- 열거형을 숫자로 저장
JpaReposiroty
- jdbc에서 사용한
CrudRepository와 비슷한 인터페이스 - JPA에 특화된 더 많은 기능들을 포함하고 있음
JPQL
- JPA(Java Persistence API)에서 제공하는 쿼리 언어
- 객체지향적인 쿼리 작성을 지원
- 엔티티 클래스의 객체를 대상으로 객체를 조회 가능 (테이블을 대상으로 조회 X 객체를 대상으로 조회 O)
