문제 https://programmers.co.kr/learn/courses/30/lessons/42585
[쇠막대기]
- 문제 재정의:
인접한 ()는 레이저, 여는 괄호( 와 닫는 괄호)로 쇠막대기 input 받음
긴 쇠막대기 위에만 올릴 수 있음
각 쇠막대기 자르는 레이저 적어도 하나 존재
레이저는 쇠막대기의 양 끝점 절대로 겹치지 x
쇠막대기는 다른 막대기들의 끝점과 겹치지 않게 올려야 함
- 생각한 것:
- input받은 괄호를 분석해 구분하여 데이터 저장해놓는 것이 우선
- 스택으로 구현. (스택으로 후위 계산식 계산하는 코드 생각이 남. 이걸 참고 해야겠다고 생각. )
- 스택에 일단 차례대로 집어 넣는다. 근데 이때 )괄호를 만나면 pop 해주고,
인접한 괄호라면 레이저 정보 업데이트, 그리고 count +2를 해준다.
쇠막대기를 가리키는 )괄호라면 pop해주고 count 값을 쇠막대기의 길이로 저장해둔다. 또 count +2를 해준다. 반복.
이걸 스택에 (가 없을 때까지 반복한다.
- 레이저와 쇠막대기가 겹치는지도 알고 잇어야 정답 return 가능
레이저와 쇠막대기의 위치 정보를 또 저장해두어야 함
매열을 쓰면 더 쉬울까? (인덱스로 알 수 있으니?)
- 쇠막대기가 몇 등분 되는지도 알아야 함
파악 한 위치 정보로 등분 계산
위에서 구상한 것을 바탕으로 코드를 짬
근데 생각해야할 것들이 더 많아서 코드 짜면서 그때그때 추가해주었다
EX) 필요없는 레이저, 막대기별 통과하느 레이저 계산 방법, 생각보다 스택이 더 많이 필요했다는점
그래서 코드 주석 열심히 달았다 ㅎㅎ^^__^^
- 코드:
//이클립스 코드
//BufferedReader 사용
package till;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//괄호들을 string형 변수에 저장
String arrangement = br.readLine();
solution(arrangement);
}
public static int solution(String arrangement) {
return Lazor_Stick(arrangement);
}
public static int Lazor_Stick(String x) { //괄호 분석, 레이저와 쇠막대기 도출
int lazor=0;
int peeking=0;
//쪼개서 배열에 저장 -> split 사용하려고 배열에 저장후 스택에 저장. 매우 비효율적. 어떻게 바꿀지 생각하기
String[] temp;
temp=x.split("");
int num=temp.length;//괄호들 총 몇개
Stack input= new Stack();//괄호를 저장하는 스택
Stack stick_length=new Stack();//쇠막대기가 시작되는 index번호를 저장하는 스택
boolean[] lazor_index=new boolean[num];
Arrays.fill(lazor_index,false);//기본값을 false로 초기화. 유효한 레이저가 있는 index에는 true가 들어가게 할 것임.
Stack lazor_stack=new Stack();
int check=0;
//레이저 기록하기
for(int i=0;i<num;i++){
if(temp[i].equals("(")){//여는 괄호를 만나면 input
input.push(temp[i]);
stick_length.push(i);//막대기가 시작되는 index번호 저장. 나중에 막대 길이 계산하기 위해 필요함
check=i;//여는 괄호 다음에 바로 다음 괄호가 나오면 레이저 임을 인식하기 위한 변수 check
}
if(temp[i].equals(")")){
if(check+1==i){ //만약 여는 괄호 다음에 바로 다음 괄호가 나오면 레이저임
if(input.size()>1){//여는 괄호들 사이에 닫는 괄호가 나온거라면 유효한 레이저임.
lazor++;//유효한 레이저 수 ++
System.out.println("유효한 레이저들의 닫는 괄호 인덱스 번호"+i);//유효한 레이저들의 닫는 괄호 인덱스 번호
lazor_index[i]=true;
}
input.pop();//레이저를 뜻하는 괄호 쌍을 pop함
stick_length.pop();//레이저를 뜻하므로 쇠막대기 정보를 넣는 이 스택에서 pop
}
else {//한 쇠막대기가 끝나는 괄호라면
peeking=(int) stick_length.peek(); //쇠막대기가 시작된 인덱스 번호를 peek함
System.out.println(peeking+"과 "+i+" 사이에 있는 레이저 수는: "+lazor);
stick_length.pop(); //다 구한 길이 정보는 pop
int sarah=0;
for(int j=peeking;j<=i;j++){//막대의 시작과 끝 사이에
if(lazor_index[j]==true){//true인 애가 있으면(레이저가 있으면)
sarah++;//++해주고
}
}
lazor_stack.push(sarah+1);//막대별 겹쳐져 있는 레이저 갯수를 스택에 넣는다.
}
}
}
System.out.println(lazor_stack);
//레이저가 분해한 막대 갯수는->레이저갯수+1 해주면 됨.+1은 위에서 미리 함.
int sums=0;
while(!lazor_stack.empty()){
sums+=(int) lazor_stack.peek();
lazor_stack.pop();
}
System.out.println(sums);
return sums;
}
}&
//프로그래머스 코드
import java.util.Arrays;
import java.util.Stack;
class Solution {
public int solution(String arrangement) {
return Lazor_Stick(arrangement);
}
public static int Lazor_Stick(String x) { //괄호 분석, 레이저와 쇠막대기 도출
int lazor=0;
int peeking=0;
//쪼개서 배열에 저장 -> split 사용하려고 배열에 저장후 스택에 저장. 매우 비효율적. 어떻게 바꿀지 생각하기
String[] temp;
temp=x.split("");
int num=temp.length;//괄호들 총 몇개
Stack input= new Stack();//괄호를 저장하는 스택
Stack stick_length=new Stack();//쇠막대기가 시작되는 index번호를 저장하는 스택
boolean[] lazor_index=new boolean[num];
Arrays.fill(lazor_index,false);//기본값을 false로 초기화. 유효한 레이저가 있는 index에는 true가 들어가게 할 것임.
Stack lazor_stack=new Stack();
int check=0;
//레이저 기록하기
for(int i=0;i<num;i++){
if(temp[i].equals("(")){//여는 괄호를 만나면 input
input.push(temp[i]);
stick_length.push(i);//막대기가 시작되는 index번호 저장. 나중에 막대 길이 계산하기 위해 필요함
check=i;//여는 괄호 다음에 바로 다음 괄호가 나오면 레이저 임을 인식하기 위한 변수 check
}
if(temp[i].equals(")")){
if(check+1==i){ //만약 여는 괄호 다음에 바로 다음 괄호가 나오면 레이저임
if(input.size()>1){//여는 괄호들 사이에 닫는 괄호가 나온거라면 유효한 레이저임.
lazor++;//유효한 레이저 수 ++
lazor_index[i]=true;
}
input.pop();//레이저를 뜻하는 괄호 쌍을 pop함
stick_length.pop();//레이저를 뜻하므로 쇠막대기 정보를 넣는 이 스택에서 pop
}
else {//한 쇠막대기가 끝나는 괄호라면
peeking=(int) stick_length.peek(); //쇠막대기가 시작된 인덱스 번호를 peek함
stick_length.pop(); //다 구한 길이 정보는 pop
int sarah=0;
for(int j=peeking;j<=i;j++){//막대의 시작과 끝 사이에
if(lazor_index[j]==true){//true인 애가 있으면(레이저가 있으면)
sarah++;//++해주고
}
}
lazor_stack.push(sarah+1);//막대별 겹쳐져 있는 레이저 갯수를 스택에 넣는다.
}
}
}
System.out.println(lazor_stack);
//레이저가 분해한 막대 갯수는->레이저갯수+1 해주면 됨.+1은 위에서 미리 함.
int sums=0;
while(!lazor_stack.empty()){
sums+=(int) lazor_stack.peek();
lazor_stack.pop();
}
return sums;
}
}
Comments