-
1874 - 스택 수열알고리즘 2023. 5. 26. 19:39728x90
https://www.acmicpc.net/problem/1874
문제요약
- 첫 줄에 n (1 ≤ n ≤ 100,000)
- 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어짐
- 8 7 6 5 4 3 2 1 --> 오름차순으로 빼주면서, stack에 쌓고( push ), "+"
- 둘째줄에 입력된 값이 stack 에 가장 위에 쌓이면, 출력( pop ), "-"
- 만약 해당과정 중에서 둘째 줄에 입력한 값이 stack 마지막 인덱스가 아니라면, "no"를 출력
해당문제는
내가 출력하려는 값(둘째줄의 입력값)과 이전에 출력한 값과의 비교를 통해 쉽게 접근 가능하다.
8
4 3 6 8 7 ...
이전의 값 = 1; (초기화)
입력한 값 = 4;
라면, 이전값 < 입력한 값인 경우와 그러지 않은 경우를 나눠서 문제를 접근하면 규칙이 보인다.import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; public class Main { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); Stack<Integer> stack = new Stack<>(); int num = Integer.parseInt(bf.readLine()); int temp = 0; //4 for(int i =1; i <= num; i++){ int input = Integer.parseInt(bf.readLine());//4 if(input > temp){ for(int j=temp + 1; j <=input; j++){ stack.push(j);//1 2 3 4 sb.append("+").append("\n"); } temp = input; } else if(stack.peek() != input){ System.out.println("NO"); return; } stack.pop();//1 2 3 sb.append("-").append("\n"); } System.out.println(sb); } }
느낀점
해당 문제를 풀면서 느낀점이 있다.
모든 문제는 내가 생각한 흐름대로 풀면 답이 나올 수 있겠지만, 이렇게 되면 코드가 지져분해진다.
하지만, 내가 생각한 흐름의 분기들을 잘 생각해보면 조금 더 일반화에 가까운 코드가 구현된다는 것을 배웠다.
'알고리즘' 카테고리의 다른 글
9012 - 괄호 (0) 2023.05.26 1021 - 회전하는 큐 (0) 2023.05.26 18258 - 큐2 (0) 2023.05.24 10773 - 제로 (0) 2023.05.24 1002 - 터렛 (0) 2023.05.24