BAEKJOON : 17299, 1935, 1918

No. 1193

1. Problem

2. My Solution

• 첫 번째 방법
• 오큰수를 구하는 원리를 동일하게 적용해봄 (오큰수 문제 해결 알고리즘)
• 원소의 개수를 구하는 count() 함수의 시간 복잡도는 O(n)이므로 시간초과

import sys

n = int(sys.stdin.readline())
sequence = list(map(int,sys.stdin.readline().strip().split()))

result = [-1] * n
notFound = []

for i in range(n):
    
    while len(notFound) > 0 and sequence.count(sequence[notFound[-1]]) < sequence.count(sequence[i]):
       result[notFound.pop()] = sequence[i]
       
    notFound.append(i)

print(' '.join(map(str,result)))

• count() 함수를 이용하여 원소의 개수를 계산하지 않는 방법이 필요
• 계수정렬의 원리를 이용 -> 값을 인덱스로 갖는 공간에 원소의 개수를 저장함 ( O(n)의 복잡도 )
• 그 이후부터는 원소의 요소를 구하기 위해 0(1) 의 시간복잡도

import sys

n = int(sys.stdin.readline())
sequence = list(map(int,sys.stdin.readline().strip().split()))

result = [-1] * n                       # 결과 출력할 리스트
count = [ 0 for i in range(1000001)]    # 요소의 값을 인덱스로 하는 곳에 요소의 개수를 저장 (계수정렬원리)
notFound = []

for i in range(n):
    count[sequence[i]] += 1     

for i in range(n):
    
    while len(notFound) > 0 and count[sequence[notFound[-1]]] < count[sequence[i]]:
       result[notFound.pop()] = sequence[i]
       
    notFound.append(i)

print(' '.join(map(str,result)))

3. Learned

• 어느 부분에서 시간초과가 일어나는지 파악해야 함
• 해당 부분의 시간복잡도를 줄일 수 있는 접근법을 생각해야 함
• 원소의 개수를 다루는 문제에서는 계수 정렬의 원리를 이용해보자

---

No. 1935

1. Problem

2. My Solution

• 0으로 나뉘는 경우를 대비해 try-catch 문 적용
• eval 함수를 이용

import sys

n = int(sys.stdin.readline())

pos_exp = sys.stdin.readline().strip()
operand = []
stack = []

for _ in range(n):
    operand.append(int(sys.stdin.readline()))

for i in pos_exp:
    if ord('A') <= ord(i) <= ord('Z'):
        stack.append(operand[ord(i)-65])    # 피연산자면 push
    else:   
        operand2 = stack.pop()
        operand1 = stack.pop()
        try:
            stack.append(eval("operand1" + i + "operand2 "))  # 연산자면 두개를 pop 해서 연산 후 다시 push
        except:
            stack.append(0)

print(f"{stack[0]:.2f}")  

3. Learned

• eval("operand1" + i + "operand2 ") -> 정상
• eval("operand1 i operand2 ") -> 에러 (operand 변수는 제대로 가져옴)

---

No. 1918

1. Problem

A*(B+C)		  ->	ABC+*
A+B*C+D*E+G	  -> 	ABC*+DE*+G+
A*B+C+D+E*F*G+E	  ->	AB*C+D+EF*G*+E+
A+B*C*((D-E)*G)	  ->	ABC*DE-G**+

2. Others' Solutions

• 중위 표현식에서 연산자와 '(' 만 스택에 push
• 피연산자는 바로 결과 스택에 push
• 연산자 보다 스택 상단의 연산자 우선순위가 더 크거나 같은 경우에는 pop 하여 결과 스택에 push

import sys

exp = sys.stdin.readline().strip()
pos_exp = []
stack = []

for i in exp:
    if i == '(':
        stack.append(i)
    elif i == '*' or i == '/':
        while stack and (stack[-1]=='*' or stack[-1]=='/'):
            pos_exp.append(stack.pop())
        stack.append(i)
    elif i == '+' or i == '-':
        while stack and stack[-1] == stack[-1]!= '(':
            pos_exp.append(stack.pop())
        stack.append(i)
    elif i == ')':
        while stack[-1] != '(':
            pos_exp.append(stack.pop())
        stack.pop()
    else:
        pos_exp.append(i)

for i in range(len(stack)):
   pos_exp.append(stack.pop())

print(''.join(map(str,pos_exp)))

3. Learned

• 해당 문자가 알파벳인지 판단하기 위해 .isalpha() 함수 사용 가능
• 요소가 없어서 [-1] 인덱스 접근이 에러가 날 경우에는 아래와 같이 앞에 논리연산 추가

while stack and stack[-1] == stack[-1]!= '(':

• 중위 표기법 -> 후위 표기법 원리 참고 유튜브