어제나 오늘이나 계속 가방을 못챙기고 있다. 헤드셋을 끼고 지갑과 핸드폰을 든 채 걸어오다보니 플래너를 계속 못챙겨옴 으으
오늘도 이번 달 지각 한번도 안했는데 월말이니까 1시에 가볼까 하는 생각을 억누르고 어떻게든 왔으니 그래도 산은 하나 넘었다고 생각해야지
오늘의 계획
무튼 그런이유로 지금은 체크리스트로 쓰고 집가서 옮겨적을거임
- PS 2문제 풀기
- 강의 다시보기
- B형 특강 저번주꺼 복습
- TIL 작성 마무리
- CS - 요약집
- 정처기 - Git 정리
- Spring - 강의 들으며 공책에 정리
- 인사이트 정리 (멘토링, 취업특강, ...)
음 오늘도 큰 꿈이네
PS 2문제 풀기
괄호 회전하기
입력으로 받은 괄호를 회전했을 때 올바른 괄호가 되는 경우의 수를 출력하는 문제.
입출력 예 2개로 판단해보면 아래와 같이 볼 수 있다.
이렇게 보았을 때 특징을 뽑아낼 수 있는데,
괄호의 분리는 {닫힌괄호} 뒤에 {열린괄호}가 올 때 가능하다
라는 점이다.
이 기준만을 가지고 코딩하면 위의 두 경우는 해결이 가능한데, 올바른 괄호가 큰 괄호 안에 포함되어 있다면 생각이 어려워진다.
회전을 가능한 만큼 해본다 한들, 가장 큰 괄호가 이를 묶고 있어서 사실상 단 한번의 경우인 [[](){}] 만 가능하다.
그러면 올바른 괄호를 다 찾아서 특정 문자 C 로 스택에 넣어둔 다음 대칭이 되는가를 찾을 수도 있을 것.
만약 올바른 괄호가 붙어있지 않더라도 각자 쌍이 생길 것임.
우선 이정도 생각이 드는데 이를 손코딩으로 써보자
/*
{열린괄호}를 만나면
일단 스택에 넣기
{닫힌괄호}를 만나면
스택에서 {열린괄호}를 찾기
{열린괄호}를 찾으면
특정문자 `C`로 치환 후 pointer 감소
*/생각으로는 구현이 간단한데 이를 코드로 풀어쓰려니 어떻게 잡아야할지 고민이됨.
C를 기점으로 감싸는 올바른 괄호가 있다면 더 큰 범위를 C로 취급해야 올바른 결과를 얻을 터.. 이를 코드로 어떻게 표현해야할지 도통 모르겠음.
그냥 간단하게 stack에 C이면 지나가고 괄호면 맞는걸 봐도 괜찮은가 흠
우선 다시 정리해보면,
- 같은 종류의 괄호가 열리고 닫히는데 안에 아무것도 없거나
C만 있다면 올바른 괄호이므로C로 묶는다. {닫힌}-{열린}구성은 다른 괄호이니 분리한다.- 단, 올바른 괄호를
C로 묶었다는 전제하에 다른 괄호에서 C만 포함한다면 그 경우는 분리가 불가능한 괄호라는 의미이므로 다시C로 묶는다.
인듯하다.
구현이 아직 머리가 아파서 점심먹고 다시 코드로 풀어봐야겠음.
...
구현이 어려워서 간단한 로직(이지만 효율성은 좀 버린..)으로 풀어봤음.
그런데 이 문제를 나같은 생각을 한 사람이 없었다..
왜 그대로 구현한거지 싶긴한데,
하긴 s의 길이가 1000이하이면 가능하겠네
n^2 배열 자르기
가장 쉽게 구현하려면 2차원 배열에 다 전처리 해둔다음 left와 right를 나누기연산과 나머지연산으로 반복문만 돌리면 풀수 있겠지만...
실제 코테가 아니다보니 가장 효율적으로 구현하고 싶은 생각이 샘솟기도 하고, 무엇보다 입력값에서부터 N^2을 할 수 없다는게 보임.
효율적으로 하려면 전처리를 하지 않고 구하는건데, 아니나 다를까 벌써머리가 어지러움 ㅎㅎㅎㅎ
...
생각보다 쉽게 구현이 가능했다.
문제를 행 기준으로 보지말고 표 기준으로 보면 한 칸에 들어간 값은 행과 열 인덱스 중 큰값+1과 같았다.
이를 활용해서 풀어보면 아래와 같음.
오늘 풀어본 두 문제 다 삽질을 했는데, 좀 더 시간복잡도 분석을 하고 가능한 범위이면 바로 구현하는 것도 연습을 해봐야할 듯 싶다. 효율적으로 구현하려다 못하는 것보단 덜 효율적으로 구현하는게 더 낫지.
강의 다시보기
Spring을 할까 하다가 Vue.js를 복습하고 git에 정리를 진행했음.
low level 프론트만 하다가 프레임워크를 다루니 재밌긴하지만 아직은 다소 어렵다.
모던자바스크립트인액션을 결국 읽어야하나..
