백준 16637번 괄호 추가하기 코드/해설 (파이썬)

코드만 보고 싶은 분은 링크

GitHub - Rhyankwon/algorithms

 

기본적으로 문제에서 요구하는건 수식의 사이에 괄호를 넣어서 임의의 순서대로 계산시켰을 때 가장 크게 나오는 값이 얼마일지를 찾는 것이다. 그리고 여기에서  추가된 문제의 조건은 간단히 두가지가 있다.

 

첫째는, 괄호안에 괄호가 들어갈 수 없다. 다시 말하면 앞쪽 연산자를 기준으로 괄호를 치면 그 뒤 연산자를 한번은 건너 뛰고 그 다음 연산자를 기준으로-앞쪽에 괄호친 부분을 제외한 범위에서 괄호를 쳐야한다. 나는 이부분은 dfs로 구현했다.

 

둘째는, 연산자 사이에 우선순위가 없다. +, -, * 이렇게 세개의 경우만 나오는데 9+4*7 이렇게 있으면 9+4를 먼저 계산해야된다. 이부분은 그냥 슬라이싱 잘 활용하면 됨.

 

내가 풀이한 방식은 이렇다.

1. 괄호를 치는 경우를 1로 표지하고 그렇지 않은 경우를 0으로 표지한다.

2. dfs를 활용해서 반복하면서 앞쪽에 1로 표지된 경우는 0을 추가한 경우에만 dfs, 0으로 표지된 경우는 1과 0을 추가할 수 있는 경우 두개에 대해 dfs한다.

3. 모든 연산자 각각에 대해 괄호를 칠지 안 칠지 판단되면(끝까지 가면) 계산 하고 max써서 최댓값 업데이트

 

계산 방법

1. 1001이런식으로 표지되있으니깐.. 연산자 나올 때마다 1인지 0인지 확인해서 1이면 계산 한 다음 그 값을 다른 리스트에 저장. 0인 경우는 계산 없이 리스트에 저장

2. 괄호친 부분을 모두 계산하면, 윗줄에서 값들을 저장한 리스트를 이제 두번째 조건에 맞춰서 계산하면 된다. 그냥 앞에서부터 요소 3개씩 빼서 계산 다시 저장 반복하면됨.

 

나는 두번째 조건(연산자 사이에 우선순위 x)을 제대로 안 읽고 풀어서 나중에 읽어보고서는 조금 당황했다. eval써서 대충 어쩌고 풀면 될 줄 알았더니.. 그리고 개인적으로는 첫번째 조건보다 두번째 조건의 구현이 더 어려웠다. 왜냐면 처음에는 내가 eval활용을 조금 쉽게하려고 리스트로 안 풀고 문자열로 풀었었는데 그러다보니 괄호를 먼저 계산했을 때 (-2)와같은 음수가 나오는 경우에 연산자랑 숫자를 구분해서 계산을 시키기가 무척 까다로웠다. ㄹㅇ 여기에서 한 한시간 씀;; re썼다가 슬라이싱 했다가.. 시간아까워ㅠ

 

나중에 그냥 리스트로 받아서 계속 값들을 떨어트린 채로 연산 저장 연산 저장 하니까 문제를 풀 수 있었다. 원래도 이 이슈때문에 나는 리스트로 문제 푸는걸 선호하는데 괜히 문자열로 풀어보려고했다가 거의 한시간반 날림.. 두시간 이상 걸리면 다른 사람풀이 보고 푸는 나만의 규칙?이 있어서 다른사람꺼 보고 풀려고 했는데 그 사람들은 나랑 시작부터 풀이가 너무 달라서 딱 봐도 거의 맞은 내 풀이를.. 버릴 수가 없었다.ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 

 

확실히 구현..을 내가 못한다. 이건 뭐 연습하면서 늘어야지.

 

 

----------------------------------------잡담------------------------------

 

이 문제를 풀기 전에 내가 몰랐던 두가지가 있다.

 

첫째는, 이렇게 시간이 오래 걸릴 줄 몰랐다.ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 어제 미리 손코딩느낌으로 대충 논리는 생각해놨었어서, 길어야 50분정도 걸릴거라고 생각했다. 심지어 어제 머릿속으로 생각할 때는 어렵겠다는 느낌도 못 받았다. 한 5분.. 생각했나? 우왕 쉽다 이러고 있었는데 실제론 거의 두시간 반정도가 걸렸다. 괜히 문자열로 풀어봐야지 고집부리다가..

 

둘째는, 이거 삼성 A형 기출문제더라. 어째 문제가 퀄이 좋더라; 쉬워보이는데 알고보면 규칙이 교묘하게 구현하는데에 은근 머리를 써야함.... 근데 찾아보니까 A형은 두시간씩 걸려서 푸는 문제가 아님ㅋㅋㅋㅋㅋ ㅠㅠ 흑흑.. 아직 취업준비하려면 6달정도 남았으니까 공부 열심히 해야징.. 혼자 힘으로 풀긴 했으니까... 몇달 더 열심히 코딩공부하면 조금 쉽게 풀지않을까?