자료구조 빈출 스타일

- : 못푼 것들

 

- 3111이 원래대로는 여기에 해당하는데 어떻게 넣어야 할지를 모르겠... 

최강 자료는 참고로 이거: https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=chogahui05&logNo=221341506848 

 

- 이것의 유제 9935: https://www.acmicpc.net/problem/9935

둘다 유명한 문제다. 9935의 경우 풀이법 좀 생각해보다가 생각 맞는지 풀이법 본 뒤 코드로 구현했는데 계속 시간 초과. 엄청 사소한 부분들에서 줄여야 하는 것 같아서 줄여도 또. 결국 다른 풀이들 보고 공부함. 이때 기존 내 풀이에서 stack.pop 말고, 배열 슬라이싱(queue 자료형 쓰는게 아니고 리스트 쓴다는게 핵심이다, queue 는 아무것도 안먹힘. 리스트를 써야 del도 할수있고, 슬라이싱도 동시에 쓸 수 있음. 글고 list[-m:] 에서 m의 길이만큼 슬라이싱하되 맨 뒤에서부터 한다는...? 뜻으로 해석 되는데 완전 확실친 않음-> 찾아봈는데 맞음) 이 더 시간 적게 나오려나 싶긴 했는데 진짜 그렇더라고..다만 join 이 매번 들어가는 부분은 의외였다 join이 잡아먹는 시간도 크다고 알고 있었어서. 아무리 그래도 알파벳 하나하나 비교하는 for 문 로직 하나 더있는것보단 나았겠지. 이미 데이터 크기에서 O(N) 이어야 한단 사실을 눈치챘어야 했고... 그래도 join 이 근본적으론 for 돌리는거랑 같기 때문에 차이가 없을줄로 알았지 난... 그리고 난 좀 쓸데없이 flag 같은거 넣는 등 로직이 복잡함. 그 복잡성을 단순하게 만들어야 한다는 사실을 알았음에도 이에 실패해서 풀이를 본거다.

 

9935_2 풀이 공부해보면 투포인터 방식 풀이고, 이런 발상이 리트코드에 겁나 자주 나오는... 꼭 여러번 공부해야...

 

 

라인 핀테크 2021 1번

 

- 그리고는 엄청난 강적을 만나버렸는데... 그것은 리트코드 2116 https://leetcode.com/problems/check-if-a-parentheses-string-can-be-valid/

아직도 풀이 이해 안됨. 리트코드에 당사자가 써놓은 설명 봐도 이해 안됨. 일단 여기서의 parentheses 가 뭔지를 모르겠음. 이를테면 이 풀이 당사자 글의 댓글에 사람들이 발상 이해 도움 주는 글 달아둔거 보면 ["))((", "0011"] 이런 경우가 예시로 나오는데, 이게 결론적으로 parentheses가 된단건지 아니란건지 모르겠음...

아 이거 좀 이해했다. 일단 ["))((", "0011"] 얘는 패런티시스가 아닌데(false) True로 떠서 문제고, 그래서 반대 케이스를 해줘야 한다는 말임.

글고 orphan = 고아로, 고아 ( 와 고아 ) 개수를 체크한다는 의미를 기억할 것.

그리고 bal가 음수가 되는 경우를 생각해보셈. 이게 맨 앞에서부터 순차 순회하면서 이 값이 수시로 변한단 사실을 상기해보면, 그냥 음수가 되는게 아니고 앞의 것들은 얼추 짝이 다 맞아 졌는데 순간적으로 짝이 안맞게 된 그 순간에 음수가 될 것이란 말임.

그러면 원본 풀이 보면 "If the balance goes negative, we check if we have enough wild characters to compensate"란 말이 있잖아? 이 와일드도 초반부터 끝나게 된게 아니라면 맨 앞에서부터 카운트 된게 분명 있을 것이기 때문에 이미 이 숫자에 순서의 의미를 포함하고 있는 상태인 것임. 그래서 wild 를 양수로 직접 카운트 해도 되는 것이었고.

 

그럼 역순 문자열을 검사하는 이유는? 반례를 생각하는 능력인듯. 이건 로직 자체를 짜는 재능이 아니라 반례를 생각하는 능력..

 

아무튼 수시로 꼭 다시 풀어볼 것

*유사 문제: 2020 카카오 기출 괄호 변환 https://programmers.co.kr/learn/courses/30/lessons/60058

이 문제의 최고 투표수 풀이가 2116의 최고 투표수 풀이와 동일한 방법을 사용한다. 이 문제에 대한 회고는 재귀 코너에 해둠

 

 

<우선순위 큐 문제 *모음: https://everenew.tistory.com/107 >

- 백준 1655: https://www.acmicpc.net/problem/1655

힙, 우선순위 큐 활용 문제를 풀어본 기억이 거의 없어서 부러 관련 문제 모음을 찾아 푼것임. 첨에 생각 좀 해보다가 이건 리트코드 테스트서 본적 있는 문제기도 해서 그냥 풀이 공부하는게 더 효율적이겠다 싶어서 풀이 보고 공부함. 복습하라

 

- 백준 13345: 역시 모음 문제. 답 보고 공부했는데 1655보다 어려웠

 

- 17612: https://www.acmicpc.net/problem/17612

큐 개념이 많이 익은 상태라 풀수는 잇었음...근데 문제는 뭐였냐면 문제를 내맘대로 해석했단 것이었고 그걸 차치해도 명백한 상황 설명이 없어서 그걸 예제 등을 통해 유추하던 아니면 상식적으로 이럴거라 생각하던 하는걸 눈치채지 못했단것임

첨에 문제에 그런말이 없었지만 그냥 시간의 흐름대로, 1초 시간이 흐르는 동안 각 계산대의 물건들은 계산이 되고 손님은 1초 당 1명 들어오는 식인줄 알았음. 근데 그게 아니고 모든 사람 다 들어온 담에 계산 한번에 시작하는거더라고 예제갖고 종이에다 직접 하면서 따져보니까... 그래서 답 코드는 훨씬 더 간단한 거였음