자몽 스토리

[힙(Heap)]

1. Heap이란?

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
• 여러 값 중, 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조로 반정렬 상태(느슨한 정렬 상태)이다.
• 힙 트리는 중복된 값을 허용한다. (이진 탐색 트리는 중복값 허용X)

※ 완전 이진 트리의 특징

1) 완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다. 

2) 마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 왼쪽에서 오른쪽으로 채워져야 한다.

3) 완전 이진 트리는 배열을 사용해 효율적으로 표현 가능하다.

※ 반정렬 상태

트리 구조를 배열에 저장한 것이므로 배열로만 보았을 때는 완전히 정렬된 상태로 보이지는 않는다는 것을 의미.

2. 힙의 종류

1) 최대 힙(max heap)

부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

2) 최소 힙(min heap)

부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

3. 힙의 구현

• 힙을 저장하는 표준적인 자료구조는 배열이다.
• 구현을 쉽게 하기 위하여 배열의 첫번째 인덱스인 0은 사용되지않는다.
• 특정 위치의 노드번호는 새로운 노드가 추가되어도 변하지 않는다.
  예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다.
  • 왼쪽 자식의 인덱스 = (부모의 인덱스)*2
  • 오른쪽 자식의 인덱스 = (부모의 인덱스)*2+1
  • 부모의 인덱스 = (자식의 인덱스)/2
  • 힙에서의 부모 노드와 자식 노드의 관계

4. 힙의 삽입

• 힙에 새로운 요소가 들어오면, 새로운 노드를 힙의 마지막 노드에 이이서 삽입한다.
• 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.

예시)

※ 같은 레벨의 자식노드들 끼리의 크기는 중요하지 않다.

5. 힙의 삭제

1) 최대 힙에서 최대값은 루트 노드이므로 루트 노드가 삭제된다.(최소 힙에서는 최소값인 루트노드가 삭제

2) 삭제된 루트 노드에는 마지막 노드를 가져온다.

3) 힙을 재구성한다. 

예시)

6. JAVA Priority Queue 사용법

1) Priority Queue 선언

import java.util.PriorityQueue; //import

//int형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
//int형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

//String형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(); 
//String형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

2) Priority Queue 값 추가

priorityQueue.add(1);     // priorityQueue 값 1 추가
priorityQueue.add(2);     // priorityQueue 값 2 추가
priorityQueue.offer(3);   // priorityQueue 값 3 추가

자바의 우선순위 큐에 값을 추가하고 싶다면 add(value) 또는 offer(value)라는 메서드를 활용하면 된다.

• add() : 삽입에 성공하면 true를 반환, 큐가 꽉 찬 경우 IllegalStateException을 발생
• offer() : 값 추가 성공 시에 true를 반환, 값 추가 실패 시 false를 반환

3) Priority Queue 값 삭제

priorityQueue.poll();       // priorityQueue에 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueue.remove();     // priorityQueue에 첫번째 값 제거
priorityQueue.clear();      // priorityQueue에 초기화

• poll() : 큐가 비어 있을 경우 null 반환
• remove() : 큐가 비어 있는 경우 NoSuchElementException 에러 발생
• clear() : 큐 비우기

4) Priority Queue에서 우선순위가 가장 높은 값 출력

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();//int형 priorityQueue 선언
priorityQueue.offer(2);     // priorityQueue에 값 2 추가
priorityQueue.offer(1);     // priorityQueue에 값 1 추가
priorityQueue.offer(3);     // priorityQueue에 값 3 추가
priorityQueue.peek();       // priorityQueue에 첫번째 값 참조 = 1

- 프로그래머스 Heap 관련 문제 ( Level2 / 더 맵게 ) 

- 참고 지식

※ 자료구조 heap과 메모리영역의 heap의 관련성?

과거에 일부 개발자들이 가용 메모리를 heap이라 부르기 시작한 것 같고, 특별한 이유는 없는 것으로 보임.

결국 stack 메모리는 stack 자료구조로 된 것이 맞지만,

heap 메모리는 heap(우선순위큐) 자료구조와 아무런 연관성이 없다고 볼 수 있다.

- 출처

[해시(Hash)]

1. 해시의 등장배경

배열은 내부 인덱스를 이용하여 자료의 검색이 한번에 이루어지기 때문에 빠른 검색 속도를 보이는 반면 

데이터의 삽입, 삭제 시 많은 데이터가 밀리거나 빈자리를 채우기 위해 이동해야하기 때문에 많은 시간이 소요된다.
반면에 연결리스트는 삽입, 삭제 시 인근 노드들의 참조값만 수정해줌으로써 빠른 처리가 가능했었다.
단, 처음 노드 마지막 노드 이외의 위치에서 데이터를 삽입, 삭제할 경우나 데이터를 검색할 경우에는 해당 노드를
찾기 위하여 처음부터 순회 검색을 해야하기 때문에 데이터의 수가 많아질수록 효율이 떨어질 수 밖에 없는 구조다.
이러한 한계를 극복하기 위하여 제시된 방법이 바로 해시(Hash)이다.

2. 해시란?

해시는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 가진다.
그리고 데이터의 삽입과 삭제 시 기존 데이터를 밀어내거나 채우는 작업이 필요없도록 특별한 알고리즘을 이용하여 

데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다.

특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기때문에 삽입 시 다른 데이터의 사이에 끼어들거나
삭제 시 다른 데이터로 채울 필요가 없으므로 삽입과 삭제 시 데이터의 이동이 없도록 만들어진 구조이다.

* 해시의 특징

• 해시는 검색과 저장에서 아주 우수한 성능을 보인다
• 해시의 핵심은 KEY, VALUE를 함께 저장하는 자료구조이다.

3. 해시의 충돌

key를 해시함수를 통해서 해시코드로 변환시키고 이 해시코드를 인덱스로 사용하여 value를 저장하는데,

이때 충돌(Collision)이 발생할 수 있다. 다음의 예시를 보자.

John Smith와 Sandra Dee라는 key가 해시함수를 통해 해시코드로 변환되었는데 우연히 같은 코드로 변환된 것이다.
해시충돌은 완벽히 피할수는 없지만 개선방법은 2가지 존재한다.

1) 충돌해결 - Separate Chaining 기법

John Smith가 들어가 있는데 그 공간에 또 Sandra Dee가 들어갈 때 Collision이 발생한다. 이 때 Sandra의 value를 기존 John의 뒤에 연결리스트를 이용해 체인처럼 이어 붙혀준다. 152번지에 John과 Sandra의 정보가 함께 존재하도록 한것이다.

* 장점

• 한정된 저장공간을 효율적으로 사용할 수 있다.
• 해시함수에 대한 의존성이 상대적으로 적다.
• 메모리 공간을 미리 잡아 놓을 필요가 없다.(그때그때 이어붙이기 때문)

* 단점

• 한 Hash에만 자료가 계속들어간다면(쏠린다면) 검색 효율이 떨어진다.(최악의 경우 O(n))
• 외부 저장공간을 사용한다. 

2) 충돌해결 - Open Addressing(개방주소법)
개방주소법은 데이터의 해시(hash)가 변경되지 않았던 Chaining과는 달리 비어있는 해시를 찾아 데이터를 저장하는 기법이다. 즉, 해시 충돌이 일어나면 다른 버킷에 데이터를 삽입한다.

따라서 개방주소법에서의 해시테이블은 1개의 해시와 1개의 값이 매칭되어 있는 형태로 유지된다.

* 장점

• 추가 저장공간이 필요없다.
• 저장할 데이터가 적을 때 더 유리하다.

* 단점

• 해시 함수의 성능에 전체 해시테이블의 성능이 좌지우지 된다.
• 데이터의 길이가 늘어나면 그에 해당하는 저장소를 마련해 두어야한다.

4. HashMap vs HashTable(파이썬에서는 Dictionary)

1) HashMap

• null을 key, value로 사용할 수 있다.
• 동기화를 지원하지 않는다.(멀티스레드가 동시에 사용할 때 문제가 발생할 수 있다) => 대신 실행속도가 빠르다.

2) HashTalbe

• key가 null이 될 수 없다.
• value가 null이 될 수 없다.
• 동기화를 지원

=>HashMap은 HashTalbe의 신버전

5. HashMap vs HashSet 

1) 정의
HashMap은 Map 인터페이스의 구현체로, HashTable과 유사한 자료구조로 데이터를 저장한다.
HashSet은 Set 인터페이스의 구현체로, 내부적으로 HashMap을 사용하기 때문에 HashTable과 유사한 자료구조로 데이터를 저장한다.

2) 데이터 저장 형태
HashMap은 Key-Value 쌍 형태로 데이터를 저장하며, Key와 Value의 mapping을 유지하고 있다.
HashSet은 객체 그 자체를 저장한다. 위에서 HashMap을 내부적으로 사용한다고 했는데,
Key 값으로는 삽입되는 객체 그 자체를, Value 값으로는 HashSet 내부 구현 코드에서 미리 선언해둔 dummy 객체를 사용한다.

3) 중복 허용 여부
HashMap은 중복 key 값을 허용하지 않지만, Value값은 허용한다.
HashSet은 객체 자체를 데이터로 저장하기 때문에 중복을 허용하지 않는다.

4) 기본적인 사용법

- HashMap

HashMap<Integer,String> map = new HashMap<>();//new에서 타입 파라미터 생략가능
map.put(1,"사과"); //값 추가
map.put(2,"바나나");
map.remove(1); //key값 1 제거
map.clear(); //모든 값 제거

//반복문을 이용한 출력
//entrySet() 활용
for (Entry<Integer, String> entry : map.entrySet()) {
    System.out.println("[Key]:" + entry.getKey() + " [Value]:" + entry.getValue());
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:바나나
//[Key]:3 [Value]:포도

//KeySet() 활용
for(Integer i : map.keySet()){ //저장된 key값 확인
    System.out.println("[Key]:" + i + " [Value]:" + map.get(i));
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:바나나
//[Key]:3 [Value]:포도

//keySet().iterator()
Iterator<Integer> keys = map.keySet().iterator();
while(keys.hasNext()){
    int key = keys.next();
    System.out.println("[Key]:" + key + " [Value]:" +  map.get(key));
}

- HashSet

HashSet<Integer> set = new HashSet<Integer>();//HashSet생성
set.add(1); //값 추가
set.add(2);
set.remove(1);//값 1 제거
set.clear();//모든 값 제거

//출력
Iterator iter = set.iterator();	// Iterator 사용
while(iter.hasNext()) {//값이 있으면 true 없으면 false
    System.out.println(iter.next());
}

//검색
System.out.println(set.contains(1)); //set내부에 값 1이 있는지 check : true

•  출처

- 본 포스팅은 인프런 김영한 강사님 [자바 ORM 표준 JPA 프로그래밍 - 기본편]강의를 바탕으로 작성되었습니다.(섹션6)

출처: https://www.inflearn.com/course/ORM-JPA-Basic/dashboard

1.  연관관계 매핑시 고려사항 3가지

• 다중성
• 단방향, 양방향
• 연관관계의 주인

1) 다중성

• 다대일 : @ManyToOne
• 일대다 : @OneToMany
• 일대일 : @OneToOne
• 다대다 : @ManyToMany

2) 단방향, 양방향

사실 방향이라는 개념이 없고 한쪽이 참조하느냐, 양쪽 다 참조하느냐에 따라 단방향, 양방향 결정

3) 연관관계의 주인

• 연관관계의 주인 : 외래 키를 관리하는 참조
• 주인의 반대편 : 외래 키에 영향을 주지 않음, 단순 조회만 가능

2. 다대일 [N:1]

가장 많이 사용하는 연관관계이다.

단방향, 양방향 모두 존재하며, 외래 키가 있는 '다'쪽이 연관관계의 주인이다.

3. 일대다 [1:N]

일대다 단방향은 '일(1)'이 연관관계의 주인이다.

일대다 단방향 매핑의 단점은 엔티티가 관리하는 외래키가 다른 테이블에 있다는 점이다.

=> 따라서 일대다 단방향 매핑보다는 다대일 양방향 매핑을 사용하자

일대다 양방향은 공식적으로 존재하지는 않는다.

그러나 읽기 전용 필드를 사용해서 양방향처럼 사용은 가능하다

ex) @JoinColumn(insertable=false, updatable=false)

=> JPA에서 이런 구조를 지원은 해주고 있으나 다대일 양방향을 사용하는 것이 더 바람직하다.

4. 일대일 [1:1]

주 테이블이나 대상 테이블 중에 외래키 선택 가능

• 주 테이블에 외래 키
  
  • 객체지향 개발자 선호
  • JPA 매핑 편리
  • 장점 : 주 테이블만 조회해도 대상 테이블에 데이터가 있는지 확인 가능
  • 단점 : 값이 없으면 외래 키에 null 허용
• 대상 테이블에 외래 키
  • 전통적인 데이터베이스 개발자 선호
  • 장점 : 주 테이블과 대상 테이블을 일대일에서 일대다 관계로 변경할 때 테이블 구조 유지
  • 단점 : 지연로딩으로 설정해도 항상 즉시 로딩됨

5. 다대다 [N:M]

@ManyToMany를 사용하고 @JoinTable로 연결 테이블을 지정한다.

실무에서 사용권장하지 않으며 N:M의 관계를 갖는 엔티티끼리는 중간에 연결 테이블용 엔티티를

추가하는 방법을 권장한다.

값이 떨어지지 않은 주식들을 모아 계산해야하기 때문에

Stack구조가 사용하기 적절하다고 생각하여 Stack구조를 이용해 문제를 풀어보았다.

1. 코드

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Stack<Integer> stack = new Stack<Integer>();
        
        for(int i=0;i<prices.length;i++){
            while(!stack.isEmpty()){
                int peek = stack.peek();
                
                //스택에 있는 값이 더 클경우 값이 떨어진 것이므로
                if(prices[peek]>prices[i]){
                    stack.pop();//스택에서 빼주고
                    answer[peek]=i-peek;//answer에 idx차이만큼 값을 저장해준다.
                }else{
                    break;//값이 안떨어진 경우 다음 i 검사하도록 break
                }
                
            }
            stack.push(i);
        }
        
        //끝까지 가격이 안떨어진 주식들은 stack안에 계속 존재하므로 answer에 값 계산해서 넣어준다.
        while(!stack.isEmpty()){
            int pop = stack.pop();
            answer[pop]=prices.length-(pop+1);
        }
        return answer;
    }
}

Stack에 prices배열값을 계속 쌓고 값이 떨어지지 않은 주식의 인덱스값만을 저장해준다.

반복문을 돌려서 스택을 peek한 값과 배열값을 비교하여 peek한 값이 더 클 경우 주식의 값이 떨어진 것이므로,

스택에서 pop하여 꺼내주고 pop한 인덱스와 현재 인덱스의 차이만큼 answer배열에 저장해준다.

중간에 값이 떨어진 주식들은 위와 같은 방법으로 answer배열에 기록해주고,

끝까지 가격이 떨어지지 않은 주식들은 스택에 쌓아놨기때문에 마지막에 반복문을 이용하여 값을 계산하여 answer배열에 기록해준다.

- 본 포스팅은 인프런 김영한 강사님 [자바 ORM 표준 JPA 프로그래밍 - 기본편]강의를 바탕으로 작성되었습니다.(섹션5)

출처: https://www.inflearn.com/course/ORM-JPA-Basic/dashboard

1. 용어 이해

• 방향(Direction) : 단방향, 양방향
• 다중성 : 다대일(N:1), 일대다(1:N), 일대일(1:1), 다대다(N:M)
• 연관관계의 주인 : 객체 양방향 연관관계는 관리 주인이 필요

2. 연관관계 매핑을 사용하는 이유

연관관계 매핑을 사용하지 않고, 외래키로 다른 객체를 조회해올 때, FK값으로 조회해와야 한다.

이 경우, 가져온 FK값으로 한번 더 DB에 접근하여 find해와야 하는 불편함이 존재한다.

또한, FK ID값으로 찾아와서 객체를 한번 더 조회하는 것은 객체지향스럽지 못하다.

따라서, 엔티티 안에 객체를 선언하여 연관관계 매핑을 사용하여 코드를 객체지향스럽고 간결하게 표현한다.

 3. 단방향 연관관계

예시로 Memeber(회원) 객체와 Team(팀) 객체가 있다고 해보자.

회원과 팀 객체는 N:1관계이다.

이 경우 FK는 회원 테이블에 존재한다.( 1:N관계일 경우 N의 관계를 가지고 있는 객체에 FK를 세팅해줘야 관리가 용이하다)

단방향 연관관계의 경우, FK를 가지고 있는 객체에 연관있는 객체를 선언해준다.

예시로 코드를 나타내면 아래와 같다.

@Entity
public class Member {
    @Id @GeneratedValue
    private Long id;
    @Column(name = "USERNAME")
    private String name;
    private int age;
    // @Column(name = "TEAM_ID")
    // private Long teamId;
    @ManyToOne
    @JoinColumn(name = "TEAM_ID")
    private Team team;
 }

Member 객체에 Team 객체를 선언해준 후, 연관관계를 작성해준다.

Member기준 Team과 N:1관계이기 때문에 ManyToOne 어노테이션을 작성해준다.

또한 관계에서 주인인 경우 @JoinColumn 어노테이션으로 어떤 컬럼 기준으로 join을 할 것인지 명시해준다.

4. 양방향 연관관계

양방향 연관관계는 연관관계를 가지고 있는 두 객체에 서로의 객체를 모두 선언해주는 것이다.

양방향 연관관계가 필요한 경우는 역방향 조회가 필요한 경우이며,

이 경우가 아닌이상 단방향 연관관계로 설정해주는 것이 최적의 방법이다.

양방향 연관관계를 세팅하는 코드는 아래와 같다.

@Entity
public class Member {
    @Id @GeneratedValue
    private Long id;
    @Column(name = "USERNAME")
    private String name;
    private int age;
    @ManyToOne
    @JoinColumn(name = "TEAM_ID")
    private Team team;
    …
}

@Entity
public class Team {
    @Id @GeneratedValue
    private Long id;
    private String name;
    @OneToMany(mappedBy = "team")
    List<Member> members = new ArrayList<Member>();
    …
}

Member객체는 단방향일 경우와 같이 작성해주고, Team객체에 반대 연관관계인 OneToMany 어노테이션을 작성해주고,

mappedBy 속성을 통해 주인이 아닌 부가적인 객체임을 표시해준다.

5. 연관관계의 주인

단방향 매핑일 경우 주인을 정해줄 필요가 없지만, 양방향 매핑일 경우 주인을 누구로 할지 정해주어야 한다.

- 양방향 매핑 규칙

• 연관관계의 주인만이 외래 키를 관리(등록, 수정)
• 주인이 아닌쪽은 읽기만 가능
• 주인은 mappedBy 속성 사용X
• 주인이 아니면 mappedBy 속성으로 주인 지정

- 그렇다면 누구를 주인으로?

• 외래 키가 있는 곳을 주인으로 정해라
• 위의 예시에서는 Member.team이 연관관계의 주인

- 양방향 연관관계 주의할 점

• 순수 객체 상태를 고려해서 항상 양쪽에 값을 설정하자
• 연관관계 편의메소드를 생성하자
• 양방향 매핑시에 무한루프를 조심하자

6. 연관관계 최종요약 정리

1. 단방향 매핑만으로도 이미 연관관계 매핑은 완료
2. 양방향 매핑은 반대 방향으로 조회기능이 추가된 것 뿐
3. 단방향 매핑을 잘 하고 양방향은 필요할 때 추가해도 됨
4. 연관관계의 주인은 외래 키의 위치를 기준으로 정해야 함

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

+4+1-2+1 = 4
+4-1+2-1 = 4

주어진 숫자로 target 자연수를 표현할 수 있는 표현의 가지수를 return하는 문제이다.

모든 경우의 수를 다 검사해봐야하므로 dfs(깊이 우선탐색)을 이용하여 문제를 풀었다.

1. 코드

class Solution {
    int[] numbers;
    int target;
    int answer;
    
    public int solution(int[] numbers, int target) {
        answer = 0;
        this.numbers = numbers;
        this.target = target;
        
        dfs(0,0);
        
        return answer;
    }
    
    void dfs(int index, int sum){
        //1.탈출 조건
        if(index==numbers.length){
            if(sum==target)answer++;
            return;
        }
        
        //2.수행 동작
        dfs(index+1, sum+numbers[index]);
        dfs(index+1, sum-numbers[index]);
    }
}

dfs 함수를 만들어서 재귀적으로 다음인덱스를 호출하면서 모든 경우의 수를 검사하도록 하였다.

해당 코드에 대한 자세한 풀이는 아래 링크를 참고하기를 바란다.

-출처 : https://www.youtube.com/watch?v=S2JDw9oNNDk

자연수 n이 주어지고, 연속된 자연수들의 합으로 표현할 수 있는 가지수를 return 하는 문제이다.

이중 for문으로 모든경우를 탐색하는 방법을 사용하였다.

1. 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        int sum = 0; 
        
        //1부터 n까지 검사
        for(int i=1;i<=n; i++){
            sum = i;
            //자기 자신이 합인 경우
            if(sum==n){
                answer++;
                break;
            }
            
            //연속한 다음수부터 더하기
            for(int j=i+1; j<=n; j++){
                sum += j;
                if(sum==n){
                    answer++;
                    break;
                }else if(sum>n){//합이 n을 넘을 경우 효율성을 위해 break
                    break;
                }
            }
        }
        return answer;
    }
}

이중 for문을 사용하였고, 첫번째 for문에서 시작점을 정하고 두번째  for문에서는 연속된 자연수의 합을 구하여야하므로

시작점의 다음 자연수부터 차례로 더하였다. 더하는 동안 n의 값과 일치하면 answer++을 해주는 방식으로 문제를 풀었다.

처음에 정확성 테스트는 다 통과하는데 효율성 테스트에서 통과하지 못해서(문제가 간단한만큼 효율성 체크 기준이 빡빡한 것 같았다)

else if문으로 sum>n을 넘는 경우 더이상 돌지 않고 바로 break로 반복문을 나오게끔 하니 효율성 테스트에도 모두 통과하였다.

()의 짝을 찾아 모든 괄호가 닫혀있으면 true를, 아니라면 false를 반환하는 문제이다.

1. 문제풀이

괄호의 짝을 찾아야 하므로, '('문자를 찾아와서 뒤의 문자 중 ')' 문자가 존재하는지 확인하는 방식으로 접근하였다.

이중 for문을 사용하였고, start, end 변수를 선언하여 짝이 지어진 '(', ')' 문자는 검사하지 않도록 제외하였다.

효율성을 위해  StringBuilder객체를 선언하여 sb 변수에 짝이 지어진 괄호는 공백으로 치환하게끔 하여

for문 다 돌고 나온 sb 문자에 공백이 아닌 값이 존재한다면 false값을 반환하도록 하였다.

2. 코드

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        StringBuilder sb = new StringBuilder(s); //효율성을 위해 StringBuilder로 선언
        int start = 0; //시작기준 인덱스
        int end = 0; //끝기준 인덱스
        
        //s 길이만큼 반복
        for(int i=0;i<s.length(); i++){
            char now = s.charAt(i); //문자하나씩 자름
            start = i;
            
            if(now=='('){
                start = i;
                //끝기준 인덱스 다음 문자부터 검사
                for(int j=end+1; j<s.length();j++){
                    char match = s.charAt(j);
                    //닫힌괄호면서, ')'의 순서가 찾은'('보다 뒤에 있는 경우
                    if(match==')'&& start<j){
                        sb.setCharAt(j,' ');//sb의 인덱스를 공백으로 치환
                        sb.setCharAt(start,' ');
                        end = j;//')'를 짝으로 사용했으므로 끝 인덱스 변경해줌
                        break;
                    }
                }
            }
        }
        
        //sb에 공백이 아닌값이 존재하면 짝없는 괄호가 존재하는것 이므로 false를 리턴
        for(int i=0;i<sb.length();i++){
            char now = sb.charAt(i);
            if(now!=' '){
                return false;
            }
        }

        return true;
    }
}

처음에 substring 함수를 사용하여 now, match 변수를 잘랐는데, 효율성 검사에서 통과하지 못하였다.

따라서 효율성을 높이기 위해 char 변수로 비교하도록 charAt 함수를 사용하고, now, match 변수 또한

char타입으로 선언해 주었다.

위와 같이 변경하니 효율성 테스트에도 통과하였다.

하지만, 위의 문제를 Stack구조를 사용하면

더 간단하게 풀 수 있다는 사실을 검색을 통해 알게되었다.

아래는 Stack 구조를 이용한 코드이다.

3. 개선된 코드

import java.util.*;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        Stack<Character> stack = new Stack<>();
        
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            
            //여는 괄호일 때
            if(c == '('){
                stack.push(c);
            }
            
            //닫는 괄호일 때
            if(c == ')'){
                if(stack.size() == 0){
                    return false;
                }
                else stack.pop();
            }
        }
        if(stack.size() != 0) answer = false;

        return answer;
    }
}

출처 : https://hyojun.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%98%AC%EB%B0%94%EB%A5%B8-%EA%B4%84%ED%98%B8-Java