04.06 오늘의 알고리즘 문제(1874: 스택 수열)

안녕하세요! 두번째로 찾아뵙는 오늘의 알고리즘 시간(?) 입니다 ㅋㅋㅋㅋ

 

알고리즘 문제를 처음 풀어보면서

 

평소에 제대로 이해 못하고 있던 코드에 대해서도

 

좀 더 자세히 알 수있는 좋은 시간이 아닌가 싶네요 ㅋㅋㅋ(아 어렵습니다 어려워요!)

 

제가 푼 오늘의 문제는 자료구조1에 있는 1874번 [스택 수열] 입니다!

 

<문제>

당최 이게 뭔 소리여.....;;

그나마 스택 문제를 많이 풀어봐서 바로 눈에 보이길래 문제를 클릭 했는데...

 

처음에 문제 이해 하는데만 한 30분은 넘게 걸린거 같네요....;;

 

제가 이해 한 것을 바탕으로 문제를 설명 드려보자면...

 

제가 입력한 값이 예를 들어서 8이라면 [1,2,3,4,5,6,7,8]이라는 수가 오름차순으로 생성됩니다.

 

Stack에는 add(push)와 pop이라는 메소드가 있는데요.

 

add(push)는 말 그대로 내가 입력한 수를 스택에 그대로 쌓는것이고

 

pop은 add(push)를 통해서 들어간 값 중에 가장 마지막에 들어간 값이 빠지게 되는 것입니다.

 

그러니 예를 들어서 만약에 제가 5를 출력하고 싶다고 한다면

 

1부터 차례대로 push, push, push, push, push, push, pop이므로 +,+,+,+,+,+,- 가 되겠죠?

 

생각보다 문제에서 요구하는 코드들은

 

전체적으로 제가 알고 있던 것들이라 풀이가 용이 했습니다.

 

자, 설명은 이쯤하고 위에서 설명 드린 걸 바탕으로 짠 코드가 바로 아래의 코드입니다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Stack;

public class Algo1874 {

	public static void main(String[] args) throws Exception {
		BufferedReader BuffR=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter BuffW=new BufferedWriter(new OutputStreamWriter(System.out));
		Stack stack= new Stack();// 정렬된 숫자 넣는 스택
		ArrayList Plma=new ArrayList();//+,- 넣는 곳
		int index=0;// 숫자 배열의 위치만 잡아 주는 변수
		int Input=Integer.parseInt(BuffR.readLine());
		int [] InputArr=new int[Input];//입력한 숫자 크기의 배열 생성
		for(int i=0; i<Input; i++) {
			InputArr[i]=Integer.parseInt(BuffR.readLine());
		}
		for(int i=1; i<=Input; i++) {
			stack.add(i);//스택에 1부터 입력한 숫자까지의 수를 넣음
			Plma.add('+'); // 리스트에 +를 전부 집어 넣는다.
			while(!stack.isEmpty() && InputArr[index]==(int)stack.peek()) {
            //스택이 비어있지 않고 스택 마지막 값이 숫자 배열의 값과 같을 경우
				index++; //인덱스 값을 하나 증가 시키고
				stack.pop();//스택의 마지막 값이 빠짐
				Plma.add('-');//+,-를 결정하는 List에 - 집어넣음
			}
			
		}
		if(!stack.isEmpty()) {// 스택이 비어있지 않으면 '수열을 만들지 못했다'는 의미
			BuffW.write("NO");
		}else {
			for(int i=0;i<Plma.size(); i++) {
				BuffW.write(Plma.get(i)+""+"\n");
			}
		}

		BuffR.close();
		BuffW.flush();
	}

}

※어차피 스택에서 add랑 push는 같은 명령이기 때문에 저는 add를 사용했습니다!

 

+를 넣을때는 단순히 수를 넣으면서 List에 쌓아버리면 되니깐 상관이 없었는데

 

-를 넣을 때 스택의 마지막 값이랑 배열에 들어간 값을 어떻게 비교할까에 대해서 고민을 좀 많이 했습니다.

 

그런데 구글링을 하다가 스택에 peek라는 스택의 마지막 값을 뽑아주는 메소드가 있다고 하더라구요.

 

생각해보니 이 메소드도 예전에 기초문제 풀면서 썼던건데 까먹고 있었습니다.

 

오늘도 느끼는 복습의 중요성.................ㅜ.ㅜ

 

입출력 역시 문제에서 요구한 대로 정상적으로 출력이 된다.

 

오늘은 다행히도 원트 컷!

 

오늘은 그래도 천만다행히 첫 제출에 바로 정답 처리가 되었습니다!

 

확실히 BufferedReader랑 BufferedWriter 쓰는 습관을 들이니 실행 시간이 많이 단축 되는게 느껴지네요 ㅋㅋ

 

하지만 오늘 문제....분석 하는 과정에서 이해가 안됬던 코드들도 있었고 하니 달아놓은 주석들을 보면서

 

조금 더 세세하게 분석해서 이해하는 과정이 필요하지 않나 싶습니다....

 

그럼 오늘의 알고리즘은 여기서 마치도록 하겠습니다! 모두들 맛점!!