[LeetCode/리트코드] 3Sum

leetcode 의 3sum 문제는 많은 깨달음을 얻게 한 문제 중 하나이다. 

처음에 문제를 보자마자 투포인터 방법으로 풀면 된다고 느꼈지만, 사실 투포인터 문제를 직접 풀어본적이 없었고 그래서 hashset 으로 접근을 하였다. 

그런데, hashset 으로 접근을 하게 되면, 결국 완전탐색으로 모든 수를 탐색하면서 중복을 제거해나가는 방식이 되기 때문에 효율성이 떨어진다. 

또한 처음에 hashset으로 풀이를 했을 때 얕은복사를 하는 바람에 마지막에 listIn.clear() 를 하면서 출력 리스트에 있는 값이 덩달아 날아가게 되는 문제도 겪었다. 마치 DFS 문제를 풀 때, 재귀호출하는 부분에서 값의 변형이 일어난 후에 재귀호출을 하면 출력이 이상하게 나오는 것과 비슷하다는 느낌을 받았다. 예전 어떤(직접적으로 어디 코딩테스트인지는 말하지 않겠다) 코딩테스트 마지막 문제에서 DFS로 접근하여 빠르게 푼 후 매개변수로 넘기는 변수 값의 변화를 고려하지 못하여 문제를 틀리고 코테에 낙마하였던 사건이 떠올랐다. 결국 똑같은 실수 또 하는구나 싶었다(겉으로는 웃었지만 속은 타들어갔다..). 

연습에서 70의 실력이면 실전에서는 30밖에 나오지 않는다고 느꼈고, 실전에서 100을 받기 위해서는 연습 때 120을 만들어야 함을 절실히 느꼈다. 예전에 수능수학 1등급을 받기 위해서 달렸던 과정이 주마등처럼 스쳐지나갔다.... 결국 알고리즘도 수학이라는 것을 느끼면서 더 열심히 해야겠다는 생각밖에는 들지 않았다. 

정확히 알지 못하면 아는게 아니다. 

 

얕은복사의 함정

 

listIn을 날릴때 이걸 담고있는 해시셋도 날아갈 줄 몰랐고, 그래서 출력은 계속해서 공백이 나왔다. 

텅..

HashSet 을 사용한 풀이

 

정말 억울했던 것은 바로 아래코드에 범벅되어있는 println 출력부분인데, 이 부분때문에 채점 시에 output limit exceeded 가 떠서 점수가 75점이나 깎이는 놀라운 경험을 하였다😂🤣

 

 

눈디버깅을 위한 println 의 저주..ㅋㅋㅋ 제출시에는 반드시 주석처리하자

 

HashSet 을 사용한 풀이 - 좀 더 개선

 

아예 지역변수 개념으로 안쪽에 new 선언을 해버리면 clear 도 필요가 없다... 평소에 이런식으로 코드를 짜려고 노력해야겠다. 

테케 2개는 역시나 시간초과 때문에 틀리다고 나왔다.

2개는 역시 시간초과

투포인터 변형 풀이

 

성공

 

지나가다가 1개를 들으면, 반드시 그 날 그걸 마스터해야 할 것 같다. 그렇지 않고 한귀로 흘려듣고 대충 알고있게 되면 그런것들이 쌓이고 쌓여서 제대로 사용하지 못하고 흐지부지 됨을 알았다. 가끔 어떤 일이 생기고 실수를 하거나 약간 아쉬움이 남을 때, '아 왜 이게 생각이 안났지? 이걸 왜 이렇게 풀었지?' 이런다. 결국 노력부족임을 알았다. 왜냐하면, 실전에서는 내가 대충아는 10개와 제대로 아는 10개 중에서 각각 1개씩 나오기 때문이다. 이 간극을 줄이기 위해서는 연습할 때 최대한 대충아는 갯수를 줄이고 제대로 아는 갯수를 늘려야 한다.