알게 된 점
- 괄호 문제는 -> 대부분 stack을 이용한다.
- 원형 문제는 -> queue를 사용한다.
- Java queue 메소드
Queue<Integer>queue=new LinkedList<>(); queue.peek() // 제거를 안하고 맨 처음 값 queue.poll() // 제거하고 맨 처음 값 queue.add(3) // 값을넣어준다. // 보통 while문과 같이 사용 while (!queue.isEmpty()) { // 사용 }
문제 1 (꼭 다시 풀어보기)
이슈
- 문제를 대입하여 stack을 어떻게 사용할지 모름
- 분기점을 나누어서 간단하게 생각하는 방법이 필요
- 괄호 문제는 Stack 문제라고 생각하고 접근
- 인덱스 접근할때 바로 뒤에꺼를 보려고 하는 방법은 인덱스의 사이즈를 넘기 때문에, 바로 앞에(인덱스)를 보려고 하자
해결 방법
if ‘(‘이면 stack에 push
else ‘)’이면 pop을 하고
if ) 레이저면 **[앞에 인덱스가 '('면 레이저]** -> stack 안에 ‘(‘ 개수를 count하고 answer+count 한다.
else ) 닫는 괄호이기 때문에 stack에 있는 것 1개를 빼주고 answer+1을 더해준다. 코드
public int solution(String str) {
int answer=0;
Stack<Character>stack=new Stack<>();
// String -> char[]
char arr[]=str.toCharArray();
for (int i=0;i<arr.length;i++) {
char s=arr[i];
if (s=='(') {
stack.push(s);
}
// 닫는 괄호
else {
// 레이저냐?
char prev=arr[i-1];
if (prev=='(') {
stack.pop();
answer+=stack.size();
}
else { // 마지막 막대기냐?
stack.pop(); // 닫아야 하기 때문에 pop 해주고 answer에는 1을 더해준다.
answer+=1;
}
}
}
System.out.println(answer);
return answer;
}문제 2 (꼭 다시 풀어보기)
이슈
- 원형 문제 -> Queue를 사용한다.
- 이때 핵심은 원형은 뽑은 값을 다시 뒤에 이어 붙여서 원형으로 만드는 것이다! 따라서 Queue를 사용
코드
import java.util.*;
public int solution(int n, int m) {
int answer=0;
Queue<Integer>queue=new LinkedList<>();
for (int i=1;i<=n;i++) {
queue.add(i);
}
while (!queue.isEmpty()) {
// m-1개 뽑아서 뒤에 넣는다. // index역할을 대신한다.
for (int i=0;i<m-1;i++) {
queue.offer(queue.poll());
}
// 마지막 꺼는 빼고 없애준다.
queue.poll();
// 만약 1개만 남았으면 종료 ->
if (queue.size()==1) {
answer=queue.poll();
}
}
System.out.println(answer);
return answer;
}문제 3
이슈
- queue는 index 접근이 불가능
- 따라서 queue의 for문을 돌때는 for Each를 사용하자
- 자바의 객체지향을 활용하여 queue안에 2개 이상의 인자값을 넣고 싶을때는 class를 만들어서 사용
해결방법
- patient 클래스 만들기 (idx, value)
- Queue안에 patient 인자값 넣기
- Queue에서 뽑은 값과 for문을 돌면서 answer++ 증가하기
코드
class Patient {
int idx;
int value;
public Patient(int idx, int value) {
this.idx = idx;
this.value = value;
}
public int getIdx() {
return idx;
}
public void setIdx(int idx) {
this.idx = idx;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
} public int solution(int n, int idx, int[]arr) {
int answer=0;
// Queue에 저장할때 idx하고 그 값을 저장하자
Queue<Patient>queue=new LinkedList<>();
for (int i=0;i<arr.length;i++) {
Patient patient=new Patient(i,arr[i]);
queue.offer(patient);
}
while (!queue.isEmpty()) {
Patient patient=queue.poll();
int idxx=patient.getIdx();
int values=patient.getValue();
// 다시 for문 돌아서 만약 큰게 있으면
boolean check=true;
int next_idx=0;
int next_value=0;
for (Patient p1:queue) {
next_idx=p1.getIdx();
next_value=p1.getValue();
if (values<next_value) {
check=false;
queue.add(patient);
break;
}
}
// 출력
if (check) {
answer++;
if (idx==idxx) {
break;
}
}
}
System.out.println(answer);
return answer;
}
BackEnd Developer