1. 후위 표기법 (Postfix Notation)

• 일반적으로 수식을 표기할 때 사용하는 방식은 중위 표기법 이다.
• 후위 표기법은 피연산자를 먼저 표시하고 연산자를 나중에 표시하는 방법이다.
• 예) 1+3 -> 13+

1.1 후위 표기법 계산

• 스택을 이용한다.
  1 피연산자를 스택에 push한다.
  2 연산자를 만나면 스택에서 피연산자 두개를 꺼내서 계산한다.
  3 계산한 결과를 다시 스택에 넣는다.
• 15+23+4-* 를 예를 들면 아래 표와 같은 형태가 된다.

연산자/피연산자	스택
1	1
5	1, 5
+	6
2	6, 2
3	6, 2, 3
+	6, 5
4	6, 5, 4
-	6, 1
*	6

1.2 후위 표기법 문제

문제1. 백준 문제 : 후위표기식2

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt(); // 피연산자의 개수
	String postfix = sc.next();
	double[] operand = new double[n];
	for (int i = 0; i < n; i++) {
		operand[i] = sc.nextDouble();
	}
	Stack<Double> s = new Stack<Double>();
	for (char c : postfix.toCharArray()) {
		if (c >= 'A' && c <= 'Z') { // 대문자열로만 이루어짐
			s.push(operand[(int) (c - 'A')]);
		} else {
			double num1 = s.pop();
			double num2 = s.pop();
			switch (c) {
			case '+':
				s.push(num2 + num1);
				break;
			case '-':
				s.push(num2 - num1);
				break;
			case '*':
				s.push(num2 * num1);
				break;
			case '/':
				s.push(num2 / num1);
				break;
			}
		}
	}
	System.out.printf("%.2f\n", s.pop());
}

문제2. 백준 문제 : 후위표기식

• 차량기지 알고리즘 (Shunting-yard Algorithm)
  중위 표기법으로 표현된 식을 후위 표기법으로 변환하는 알고리즘
• 생각보다 생각할 것이 많은 문제이다.
• '+' '-' '*' '/' '(' ')' 각각 우선순위를 생각하여 구현해야한다.
• 현재 연산자의 우선순위가 스택의 가장 위에 있는 연산자의 우선순위보다 작거나 같으면,
  스택에 존재하는 연산자를 결과에 추가한다.
• 괄호가 있는 식은 여는 괄호는 스택에 넣고,
  닫는 괄호가 나오면 앞서 넣은 여는 괄호가 나올때까지 스택에서 연산자를 꺼낸다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	String str = sc.next();
	Stack<Character> s = new Stack<Character>();
	StringBuilder sb = new StringBuilder();
	for (char c : str.toCharArray()) {
		int p = priority(c);
		switch(c) {
		case '+': case '-': case '*': case '/':
			while(!s.isEmpty() && priority(s.peek()) >= p) {
				sb.append(s.pop());
			}
			s.push(c);
			break;
		case '(':
			s.push(c);
			break;
		case ')':
			while(!s.isEmpty() && s.peek() != '(') {
				sb.append(s.pop());
			}
			s.pop();
			break;
		default:
			sb.append(c);
		}
	}
	while(!s.isEmpty()) {
		sb.append(s.pop());
	}
	System.out.println(sb);
	}
public static int priority(char c) {
	switch(c) {
	case '*': case '/':
		return 2;
	case '+': case '-':
		return 1;
	case '(': case ')':
		return 0;
	default:
		return -1;
	}
}

2. 문자열 문제

2.1 문제 1. 백준 문제 : 알파벳 개수

• 주어진 문자열의 알파벳 소문자가 몇 개 포함되어 있는지 구하는 문제

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	String str = sc.nextLine();
	int[] result = new int[26];
	for (int i = 0; i < str.length(); i++) {
		result[str.charAt(i) - 'a'] += 1;
	}
	for (int i = 0; i < result.length; i++) {
		System.out.print(result[i] + " ");
	}
	sc.close();
}

2.2 문제 2. 백준 문제 : 알파벳 찾기

• 알파벳 소문자로 이루어진 문자열에서 각 알파벳이 몇번째에서 처음으로 등장하는지를 구하는 문제
• 문제 1번과 비슷한 유형이다.
• 해당 알파벳이 이전에 나왔는지 아닌지를 확인하고 인덱스 값을 넣어주면 된다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	String str = sc.nextLine();
	int[] result = new int[26];
	for (int i = 0; i < result.length; i++) {
		result[i] = -1;
	}
	for (int i = 0; i < str.length(); i++) {
		int c = str.charAt(i) - 'a';
		if (result[c] == -1) {
			result[c] = i;
		}
	}
	for (int i = 0; i < result.length; i++) {
		System.out.print(result[i] + " ");
	}
	sc.close();
}

2.3 문제 3. 백준 문제 : 문자열 분석

• 문자열 N개에 포함되어 있는 소문자, 대문자, 숫자, 공백의 개수를 구하는 문제이다.
• hasNextLine() 를 사용하여 한줄씩 구하면 된다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	while (sc.hasNextLine()) {
		int n1 = 0, n2 = 0, n3 = 0, n4 = 0;
		String str = sc.nextLine();
		for (char c : str.toCharArray()) {
			if (c >= 'a' && c <= 'z') {
				n1 += 1;
			} else if (c >= 'A' && c <= 'Z') {
				n2 += 1;
			} else if (c >= '0' && c <= '9') {
				n3 += 1;
			} else if (c == ' ') {
				n4 += 1;
			}
		}
		System.out.println(n1 + " " + n2 + " " + n3 + " " + n4);
	}
}

2.4 문제 4. 백준 문제 : 단어 길이 재기

• c++의 경우 strlen()의 시간복잡도는 $O(N)$이다. 그래서 아래와 같은 코드로 작성할 경우 시간복잡도는 $O(N^2)$이 된다.

for (int i=0; i<strlen(s); i++) {}

• 따라서 아래와 같은 코드로 작성하는 것이 좋다.

int length = strlen(str);
for(int i=0; i<length; i++) {}

• 자바에서는 안전성의 문제로 두번째 코드로 작성하는 것이 좋다고 한다.

문제 4의 답

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	String str = sc.nextLine();
	System.out.println(str.length());
}

2.5 문제 5. 백준 문제 : ROT13

• 주어진 문자열을 ROT13으로 암호화하는 문제이다.
• 예를들면 'a' 는 'a'부터 13번째 떨어진 알파벳은 'n'이 된다.
• 하지만 +13 을 했을 때 'Z' 또는 'z'를 넘어가는 경우가 존재한다.
• 처음에는 넘어갈 때 -27를 했으나 좀 더 생각해봤고, 좀 더 생각해보면 'N' 또는 'n' 부터는 -13을 하면 원하는 알파벳이 나오게 된다.
• 즉, a~m 까지는 +13 을 하고 n~z까지는 -13을 하면 ROT13암호화가 되는 것이다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	String str = sc.nextLine();
	StringBuilder sb = new StringBuilder();
	for(char c : str.toCharArray()) {
		if(c >= 'A' && c <= 'M') {
			c+=13;
		}else if(c >= 'N' && c <= 'Z') {
			c-=13;
		}else if(c >= 'a' && c <= 'm') {
			c+=13;
		}else if(c >= 'n' && c <= 'z') {
			c-=13;
		}
		sb.append(c);
	}
	System.out.println(sb);
}

2.6 문제 6. 백준 문제 : 네 수

• 주어진 4개의 수(A, B, C, D)에서 A와 B를 이어 붙이고, C와 D를 이어 붙여 나온 결과들의 합을 구하는 문제이다.
• 간단한 문제로 보이지만 단순히 문자열을 붙여 int형으로 결과를 출력했지만 런타임에러가 발생하였다.
• 이유를 찾아보면 문제의 조건에서 (1 ≤ A, B, C, D ≤ 1,000,000)라고 되어 있는데, 각 주어진 수가 최대 1,000,000 즉 $10^8$ 이면 int형의 범위를 넘어가게 되는 것이다.
• 따라서 반환형을 long 형으로 출력해야한다.
• Long.parseLong(String) 를 사용하면 된다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	String[] str = sc.nextLine().split(" ");
	long num1 = Long.parseLong(str[0]+str[1]);
	long num2 = Long.parseLong(str[2]+str[3]);
	System.out.println(num1 + num2);
}

2.7 문제 7. 백준 문제 : 접미사 배열

• 주어진 문자열의 나올수 있는 접미사들을 출력하는 문제이다.
• 예를들면, baekjoon이면, baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 로 총 8가지가 나온다. 이를 사전순으로 정렬하면 된다.
• String의 substring()을 사용하여 접미사 단위로 구분할 수 있다.
• 또한 사전순으로 정렬하기 위해 Arrays.sort()를 사용하면 오름차순 순으로 정렬이 된다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	String str = sc.next();
	int len = str.length();
	String[] strArray = new String[len];
	for(int i=0;i<len; i++) {
		strArray[i] = str.substring(i);
	}
	Arrays.sort(strArray);
	for(String s : strArray) {
		System.out.println(s);
	}
}

참고

백준 알고리즘 기초 강의를 듣고 공부하기 위해 정리한 것입니다.