정요섭

정요섭

Front-end 개발자가 되기 위한 코린이

  1. 알고리즘 기초1/2 자료구조

6 minute read

Stack

문제1. 단어뒤집기

단어뒤집기 9093번

1.문장이 주어졌을 때 단어를 모두 뒤집는 문제

2.단어의 순서를 바꿀 수 없고, 단어는 영어 알파벳으로만 이루어져 있다.

3.단어의 최대 길이: 20, 문장의 최대 길이: 1000

첫번째 도전

나의 생각 : 문장을 뒤집는 문제가 아니기 때문에 String reverse를 사용하면 안될것 같고, Stack을 사용하면 좋을것 같다.

public static void main(String[] args) {

	Scanner scan = new Scanner(System.in);

	int num = scan.nextInt();
	scan.nextLine();
	//Scanner.nextInt 메소드는 사용자 입력의 가장 마지막 개행문자(엔터, newline)를 제거하지 않음
	//개행문자(엔터) 전까지만 숫자로 입력 받습니다.
	//개행문자(엔터)는 다음에 호출된 Scanner.nextLine( ) 메소드의 입력으로 처리되서 문제기 발생합니다.
	//출처: https://allg.tistory.com/17 [프로그래밍 해볼까]

	while(num-->0) {

	    String s = scan.nextLine(); //scan.next()로 할경우 문장을 인지를 못함,
										//즉 i am 같은 경우 i만 변수가 받음 그래서 scan.nextLine()으로 받음
		char[] array = s.toCharArray();
		Stack<String> stack = new Stack<>();

		for(int i=0; i<array.length; i++) {

			if(array[i]==' ') {
				while(!stack.isEmpty()) {
					System.out.print(stack.pop());
				}
					System.out.print(' ');
			}else {
				stack.add(array[i]+""); //stack에는 String 값 이 들어가야하므로 ""를 더해줌
				}
			}
			while(!stack.isEmpty()) {
				System.out.print(stack.pop());
			}
		}
	}

결과 : 틀렸습니다.

이유 : 잘모르겠다…, System.out.pront(‘ ‘); 로 띄어쓰기를 구성하면 안된다는 가정을 함

두번째 도전


public static void main(String[] args) {

	Scanner scan = new Scanner(System.in);

	int num = scan.nextInt();
	scan.nextLine();
	//Scanner.nextInt 메소드는 사용자 입력의 가장 마지막 개행문자(엔터, newline)를 제거하지 않음
	//개행문자(엔터) 전까지만 숫자로 입력 받습니다.
	//개행문자(엔터)는 다음에 호출된 Scanner.nextLine( ) 메소드의 입력으로 처리되서 문제기 발생합니다.
	//출처: https://allg.tistory.com/17 [프로그래밍 해볼까]

	while(num-->0) {

		String s = scan.nextLine(); //scan.next()로 할경우 문장을 인지를 못함,
										//즉 i am 같은 경우 i만 변수가 받음 그래서 scan.nextLine()으로 받음
		char[] array = s.toCharArray();
		Stack<String> stack = new Stack<>();
		String str = "";
        	for(int i=0; i<array.length; i++) {

				if(array[i]==' ' || i==array.length) {
					while(!stack.isEmpty()) {
						str +=stack.pop(); //변수 str을 추가시킴
					}
					str +=" ";
				}else {
					stack.add(array[i]+"");
                    //stack에 Generic 타입으로 String을 넣었으므로 add안에 String을 값을 넣어주기 위해 array[i]+""를 해줌
                    //굳이 String을 쓰지 않고 Generic 타입으로 Character을 넣고 stack.add()에 array[i]만 넣어도 됨
				}
			}
			while(!stack.isEmpty()) {
				str+=stack.pop();
			}
			System.out.println(str);
		}
	}

결과 : 메모리초과.

이유 : 첫번째 도전에서 발생한 문제를 해결함, 띄어쓰기를 할따는 syso로 하면 안됨

메모리초과 문제는 왜 생기는지 모르겠으나.. , 이 문제를 해결하는 방법으로 BufferedReader, BufferedWriter을 사용함 BufferedReader, BufferedWriter는 응답시간과 출력시간이 빠르므로

세번째 도전

public static void main(String[] args) throws IOException {

	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	String str = br.readLine();
	int num = Integer.parseInt(str);

	// int num = br.read(); 를 쓰면 불편한 이유 !!
	// 바로 read()메서드는 값을 읽어올 때, int 값으로 변형하여 읽어 오기 때문이다.
	// 그래서 1이라는 숫자를 read()를 통해서 읽어오면 아스키코드 문자값 '1'을 읽어오므로
	// 결국 49를 읽어 오게 됨
	// 따라서 숫자를 읽어 올때는 위의 방법처럼 readLine()으로 읽고 숫자로 변환해주는게 더 편하다

	Stack<Character> stack = new Stack<>();

	while((num--)!=0) {

		String s = br.readLine()+"\n";

		    for(char c : s.toCharArray()) {

				if(c==' '|| c== '\n') {

					while(!stack.isEmpty()) {
						bw.write(stack.pop());
					}
					bw.write(c);
				}else {
					stack.add(c);
				}
			}
		}
		bw.flush();
	}

결과 : 통과

  • 생각으로만
  • Hint 보고
  • 답 보고

문제2. 괄호

괄호 9012번

1.괄호 문자열이 주어졌을 때, 올바른 괄호 문자열인지 아닌지를 알아보는 문제

2.괄호 문자열: (와 )로만 이루어진 문자열

3.올바른 괄호 문자열: 괄호의 쌍이 올바른 문제

첫번째 도전

나의 생각: Stack에 하나씩 넣고 한 모양과 다른 모양이 서로 반대일 경우 지워버림 , 지웠음에도 Stack에 괄호가 남아있다면 NO로 출력하자

public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		int num = scan.nextInt();
		Stack<Character> stack = new Stack<>();

		while(num--> 0) {

			String s = scan.next();

			for(char c : s.toCharArray()) {

				if(c=='(') {
					stack.add(c);
				}else {
					stack.pop();
				}

			}

			if(stack.isEmpty()) {
				System.out.println("YES");
			}else {
				System.out.println("NO");
			}
		}

	}

결과 : 오류발생, java.util.EmptyStackException

이유 : stack에 아무것도 없는데 pop()을 할경우 생기는 문제

이 문제를 해결하기 위해 상당히 시간을 많이 씀..

두번째 도전

나의 생각: java.util.EmptyStackException 이 문제를 해결하기 위해 어떻게 해야할지 고민을 하던중 다양한 생각을 해보게됨.. 첫째, stack에 값이 있으면 무조건 NO 둘째, stack에 아무것도 없는데 pop()을 하면 무조건 NO

이 두 조건을 만족하기 위한 코딩을 해봄..

public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		int num = scan.nextInt();
		Stack<Character> stack = new Stack<>();
		boolean isc = true;
		while(num--> 0) {

			String s = scan.next();

			for(char c : s.toCharArray()) {

				if(c=='(') {
					stack.add(c);
				}else {

					if(!stack.isEmpty()) {
						stack.pop();
					}else {  //둘째, stack에 아무것도 없는데 pop()을 하면 무조건 NO
						isc = false;
						break;
					}
				}


			}

			if(!stack.isEmpty()) isc = false; //첫째, stack에 값이 있으면 무조건 NO

			if(isc) {
				System.out.println("YES");
			}else {
				System.out.println("NO");
			}


		}

	}

결과 : 틀렸습니다.

이유 : 출력결과는 통과인데,다른 반례에서 틀렸나본데 그 반례를 못찾겠다.. 반례를 찾음 -> 연속해서 수를 입력할경우

2

)( ->no

() ->no 가 나옴 그 이유는 stack에 (게 쌓이기 때문

그렇기 때문에 stack을 계속 초기화 시켜주어야 할 필요성을 느낌

세번쨰 도전

나의 생각: 그러다가 굳이 stack을 쓰지 않아도 될것 같은 결론을 얻게 됨..

public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		int num = scan.nextInt();
		int sum =0;
		while(num--> 0) {
			sum =0;
			String s = scan.next();

			for(char c : s.toCharArray()) {

				if(c=='(') {
					sum+=1;
				}else {
					sum+=-1;
					if(sum<0) {
						break;
					}
				}

			}

			if(sum==0) {
				System.out.println("YES");
			}else {
				System.out.println("NO");
			}
		}

	}

결과 : 틀렸습니다. 맞았습니다.

이유 : 출력결과는 통과인데,다른 반례에서 틀렸나본데 그 반례를 못찾겠다..

반례를 찾음 -> 두번재 도전과 마찬가지로 sum에 값이 계속 쌓이기 때문에 새로운 괄호를 입력할때는 sum을 초기화 시켜줘야한다.

네번쨰 도전

나의 생각 : 주어진 답에는 함수로 만들어서 사용함.

 public static String isValid(String s) {
        int n = s.length();
        int cnt = 0;
        for (int i=0; i<n; i++) {
            if (s.charAt(i) == '(') {
                cnt += 1;
            } else {
                cnt -= 1;
            }
            if (cnt < 0) {
                return "NO";
            }
        }
        if (cnt == 0) {
            return "YES";
        } else {
            return "NO";
        }
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n-- > 0) {
            System.out.println(isValid(sc.next()));
        }
    }

결과 : 맞았습니다.

  • 생각으로만
  • Hint 보고
  • 답 보고

문제3. 스택수열

문제를 잘 이해 못하겠음..

문제4. 에디터

에디터 1406번

1.커서: 문장의 맨 앞, 맨 뒤, 문장 중간 임의의 곳에 위치할 수 있다.

2.L: 커서를 왼쪽으로 한 칸 옮김

3.D: 커서를 오른쪽으로 한 칸 옮김

4.B: 커서 왼쪽에 있는 문자를 삭제함

5.P $: $라는 문자를 커서 오른쪽에 추가함. 커서는 $에 위치함

첫번째 도전

나의생각: String으로 풀경우 시간이 너무 오래걸린다는 판단을 하였다. 자리이동을 시켜야 하기 때문에 그래서 Hint를 보고 Stack을 이용해서 풀려고 했는데, 잘 모르겠다. 그래서 답을 보고 이해하는 방법을 선택했다.

package 연습하기;

import java.util.Scanner;
import java.util.Stack;

public class 에디터 {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		String s = scan.next();
		int num = scan.nextInt();

		scan.nextLine();

		Stack<Character>stack1 = new Stack<>();
		Stack<Character>stack2 = new Stack<>();

		for(char c : s.toCharArray()) {
			stack1.add(c);
		}

		while(num-->0) {

			String input = scan.nextLine();

			if(input.charAt(0) == 'P') {
				char c = input.charAt(2);
				stack1.add(c);
			}

			if(input.charAt(0) == 'L') { //input == "L" 이거는 왜 안돼는거지 ?
				if(!stack1.isEmpty()) {
					stack2.add(stack1.pop());
				}

			}

			if(input.charAt(0) == 'D') {
				if(!stack2.isEmpty()) {
					stack1.add(stack2.pop());
				}
			}

			if(input.charAt(0) == 'B') {
				if(!stack1.isEmpty()) {
					stack1.pop();
				}
			}

		}

		while(!stack1.isEmpty()) {
			stack2.add(stack1.pop());
		}

		while(!stack2.isEmpty()) {
			System.out.print(stack2.pop());
		}

	}

}

결과 : 틀렸습니다.

이유 : 시간초과…

두번째 도전

나의생각 : 시간 초과가 발생했으니 Scanner 말고 BufferReader을 사용해보자 !!

public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String s = br.readLine();
		int num = Integer.parseInt(br.readLine());

		Stack<Character>stack1 = new Stack<>();
		Stack<Character>stack2 = new Stack<>();

		for(char c : s.toCharArray()) {
			stack1.add(c);
		}

		while(num-->0) {

			String input = br.readLine();

			if(input.charAt(0) == 'P') {
				char c = input.charAt(2);
				stack1.add(c);
			}

			if(input.charAt(0) == 'L') { //input == "L" 이거는 왜 안돼는거지 ?
				if(!stack1.isEmpty()) {
					stack2.add(stack1.pop());
				}

			}

			if(input.charAt(0) == 'D') {
				if(!stack2.isEmpty()) {
					stack1.add(stack2.pop());
				}
			}

			if(input.charAt(0) == 'B') {
				if(!stack1.isEmpty()) {
					stack1.pop();
				}
			}

		}

		while(!stack1.isEmpty()) {
			stack2.add(stack1.pop());
		}

		while(!stack2.isEmpty()) {
			System.out.print(stack2.pop());
		}

	}

결과 : 맞았습니다.

  • 생각으로만
  • Hint 보고
  • 답 보고

Leave a comment

You may also enjoy