Yong's Tech Story

문제 풀이 (JAVA)

import java.util.*;
public class part5_4 {

	public static void main(String[] args) {
		// 후위식 연산(postfix)
		Scanner input = new Scanner(System.in);
		
		String a = input.nextLine();
		int answer = solution(a);
		System.out.print(answer);
	}
	private static int solution(String a) {
		int result=0;
		Stack<Integer> stack = new Stack<>();
		int sum=0;
		int num1=0 , num2=0;
		for(Character ch : a.toCharArray()) {
			if(Character.isDigit(ch) == true) {
				stack.push(Character.getNumericValue(ch));
			}else {
				if(ch == '+') {
					num1= stack.pop(); 
					num2= stack.pop();
					sum =(num2 + num1);
					stack.push(sum);
				}else if(ch == '-') {
					num1= stack.pop();
					num2= stack.pop();
					sum =(num2 - num1);
					stack.push(sum);
				}else if(ch == '*') {
					num1= stack.pop();
					num2= stack.pop();
					sum =(num2 * num1);
					stack.push(sum);
				}else if(ch == '/') {
					num1= stack.pop();
					num2= stack.pop();
					sum =(num2 / num1);
					stack.push(sum);
				}
			}
		}
		result = stack.pop();		
		return result;
	}
}

주요 핵심 포인트

1. 숫자를 만날 시 스택에 추가한다.

2. 연산식을 만날 시 스택에서 두 개의 값을 추출하여 해당 연산자로 연산 후 다시 스택에 넣는다.

3. 1-2번을 반복한다.

개선해야할 사항

1. 후위식을 스택으로 풀 수 있을 줄은 몰랐다. 후위식이 어떻게 이루어져 있는지 다시 한번 개념을 찾아 보고 나서 풀 수 있었던 문제이다. 다음부터는 후위식의 풀이식을 자연스럽게 생각하도록 해보자.

문제 풀이 (JAVA)

import java.util.*;
public class part5_3 {

	public static void main(String[] args) {
		// 크레인 인형뽑기(카카오)
		Scanner input = new Scanner(System.in);
		int N = input.nextInt();
		
		int [][] a = new int[N][N];
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				a[i][j]=input.nextInt();
			}
		}
		
		int K = input.nextInt();
		int [] b = new int[K];
		for(int i=0; i<K; i++) {
			b[i]=input.nextInt();
		}
		int answer = solution(a,N,b,K);
		
		System.out.print(answer);
	}
	private static int solution(int [][] a, int N, int [] b, int K) {
		int result = 0;
		Stack<Integer> stack = new Stack<>(); // 스택선언
		int idx=0; // 탐색할 배열 인덱스
		for(int i=0; i<K; i++) { // b의 K번째까지 반복 탐색
			idx=0; // 배열 인덱스 초기화
			// 2차원 행렬 b번째 행렬에 a의 0번째 행부터 인덱스로 순차적으로 탐색하여 0이 아닐때까지 탐색
			while(idx < N && a[idx][b[i]-1] == 0) {
				idx++;
			}
			if(idx == N) { // 인덱스가 N까지 증가되었다면 b번째 행렬은 모두 0이므로 다음 for문 처리
				continue;
			}
			// 스택에 값이 들어있다면
			if(stack.size() != 0) {
				if(a[idx][b[i]-1] == stack.peek()) { // 스택의 마지막 값과 현재 뽑은 a의 숫자가 같을 경우
					stack.pop(); // 스택에서 값을 제거
					result+=2; // 현재 뽑은 a를 추가하지 않고 결과값 +2
				}else { // 마지막 스택 값과 다르다면 값 추가
					stack.push(a[idx][b[i]-1]);	
				}
			}else { // 스택이 비어있다면 값 추가
				stack.push(a[idx][b[i]-1]);
			}
			a[idx][b[i]-1] = 0; // 뽑은 a의 행렬 값 0으로 초기화			
		}		
		
		return result;
	}
}

주요 핵심 포인트

1.  이차원행렬의 인덱스를 머리에 잘 그려놓고 입력받은 b의 인덱스 값을 이용하여 값이 존재하는지 유무를 잘 판별해야한다.

2.  값을 추가 시켜주는 일차원 배열을 스택으로 구현하여, 스택의 마지막 값과 현재 값이 같다면 현재 값은 스택에 넣지 않고, 스택의 마지막값은 제거시킴으로써 result 값은 +2를 해주었다.

3. 스택이 존재하지 않을때의 처리를 잘해주어야 하고, 인덱스가 N까지 왔다면 모든 숫자가 0임으로 continue 처리를 해주었다.

개선해야할 사항

1. 실은 이 문제를 프로그래머스에서 스택의 개념을 모를때 한번 푼적이 있다. 그때 당시에 시간이 훨씬 오래 걸려서 간신히 풀었는데, 스택을 사용함으로써 다시 문제를 푼 결과 코드가 개선이 되었다고 생각한다. 아래는 이전에 풀었던 프로그래머스 코드이다.

프로그래머스 -  이전 소스 코드

import java.util.*;
class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        List<Integer> list = new ArrayList<Integer>();
        for(int i=0; i<moves.length; i++){
            int w=0;
            int h=moves[i]-1;
            if(list.size()>1){
                // 리스트의 사이즈가 2개이상이고 마지막 값과 마지막 전 값이 같다면
                while(list.get(list.size()-2)==list.get(list.size()-1)){
                    list.remove(list.size()-1); //마지막 값 제거
                    list.remove(list.size()-1); //제거된 리스트의 마지막 값 제거
                    answer+=2; // 결과 +2
                    if(list.size()<2){ // 사이즈 오류 방지--크기가 2보다 작다면 멈춰라.
                        break;
                    }
                }
            }
            while(board[w][h] ==0){ // 값이 0이라면 찾을 행 증가
                w++;
                if(w==board.length-1){ // 마지막 행도 0이라면 반복 증가 멈춰라.
                    break;
                }
            }
            
            if(w==board.length-1 && board[w][h]==0){ // 마지막이 0이라면 스킵
                continue;
            }
            if(board[w][h] != -1){  // 0이 아니라면 값이 있으므로
                list.add(board[w][h]);
                System.out.println(list);
                board[w][h]=-1;  // 값 저장 후 -1로 변환 후 스킵
                continue;
            }
            if(board[w][h] == -1){  // -1은 사용된 값으로 -1이 나온다면
                while(board[w][h] == -1){  // -1이 아닐때까지 반복 증가
                    w++;
                    if(w==board.length){  // 다음 행이 마지막 행이라면 멈춰라.
                        break;
                    }
                    if(board[w][h] != -1){ // 마지막행이 아니라면 뽑아야 될 값
                        list.add(board[w][h]);
                        board[w][h]=-1; // 리스트 저장 후 스킵
                        break;
                    }
                }
            }
        }
        return answer;
    }
}

이때는 리스트의 개념만 알고 있어 힘들게 풀었다. 스택의 개념을 공부하고 풀어 보니, 이전에 풀었던 코드의 1/2 라인 수로 쉽게 풀 수 있었다. 알고리즘을 공부하는 이유를 오늘에서 좀 더 체감하고 간다. 앞으로도 더 성장하자.

문제 풀이 (JAVA)

import java.util.*;
public class part5_1 {

	public static void main(String[] args) {
		// 올바른 괄호
		Scanner input = new Scanner(System.in);
		
		String str = input.nextLine();
		
		String answer = solution(str);
		System.out.print(answer);

	}
	private static String solution(String str) {
		String result="YES";
		
		Stack<Character> stack = new Stack<>();
		
		for(Character ch : str.toCharArray()) {
			if(ch=='(') {
				stack.push(ch);
			}else if(ch==')') {
				// 스택에 값이 없을때를 처리한다.(처리 안할시 런타임오류)
				if(stack.isEmpty()==true) {
					result="NO";
					break;
				}
				stack.pop();
			}
		}
		// 최종적으로 처리했으나 값이 남아있다면 괄호가 맞지 않음
		if( stack.isEmpty() != true) {
			result="NO";
		}			
		return result;
	}
}

주요 핵심 포인트

1. 괄호 문제가 스택의 가장 기초적인 문제라고 한다. '(' 이 들어올시 stack에 넣고 ')'가 들어올시 스택에서 제거한다. 이를 이용하여 응용할시 쌍의 개수를 찾는 다른 문제 또한 적용하면 좋겠다.

2.  pop()을 할때 '(' 가 없을수도 있으므로 스택에 값이 없을시 런타임에러가 나므로 주의해주어야 한다.

3. 최종적으로 처리하여 스택이 남아있다는 것은 '(' 의 개수가 더 많은 것이므로 올바른 괄호가 아니다. 

개선해야할 사항

1.  스택 함수 선언 및 사용 방법을 런타임 에러가 나지 않도록 주의해서 코딩해야겠다.

문제 풀이 (JAVA)

import java.util.*;
public class part4_5 {

	public static void main(String[] args){
		// K번째 큰 수
		Scanner input = new Scanner(System.in);
		
		int N = input.nextInt();
		int K = input.nextInt();
		
		int [] a = new int[N];
		
		for(int i=0; i<N; i++) {
			a[i] = input.nextInt();
		}
		int answer = solution(a,N,K);
		System.out.print(answer);
		
	}
	private static int solution(int [] a , int N, int K) {
		int result = -1;
		int sum=0;
		TreeSet<Integer> set = new TreeSet<>(Collections.reverseOrder());
		for(int i=0; i<N-2; i++) {
			for(int j=i+1; j<N-1; j++) {
				for(int k=j+1; k<N; k++) {
					sum = a[i] + a[j] + a[k];
					set.add(sum);
				}
			}
		}
		int cnt=0;
		for(int x : set) {
			cnt++;
			if(cnt==K) {
				result = x;
				break;
			}
		}	
		return result;
	}
}

TreeSet 주요 함수 정리

set.add(val) : 중복되지 않는 val 값을 set에 저장한다.

new TreeSet<>(Collections.reverseOrder()) : 값을 저장시 내림차순 정렬한다. 기본적으로는 오름차순으로 저장한다.

set.first() : set에 저장된 첫번째 값을 가져온다.

set.last() : set에 저장된 마지막 값을 가져온다.

set.size() : set의 사이즈를 반환한다.

for( int x : set) {} : for문을 사용하여 set 값을 가져온다.

주요 핵심 포인트

1. TreeSet의 내림차순 정렬을 이용하여 저장시 내림차순으로 저장되도록 하였다.

2. TreeSet은 중복값을 허용하지 않으므로 동일한 값이 들어올시 저장하지 않는다.

개선해야할 사항

1. 문제의 N 값이 100까지인것을 생각하여 투포인터와 슬라이딩윈도우를 쓸지, for문을 쓸지 잘 결정하는 것이 문제의 핵심포인트인듯 하다. 다음부터는 효율성을 고려하는 문제인지, 단순히 for문 로직을 구현하는 문제인지 빠르게 파악하도록 하자.