[2주차][20221122] 알고리즘 문제 풀이

오늘도 알고리즘 문제풀이를 진행했다.

22번 ~ 30번까지 풀이를 완료했다.

중간에 모의고사 문제도 풀고 왔는데, 어제 밤에 풀고 잔 21번 소수만들기 문제에서 구현했던 터라 쉽게 풀 수 있었다.

 

아래는 문제 풀이 포스팅 링크다.

• [22번] [중급] 숫자 문자열과 영단어
• [23번][중급] 시저암호
• [24번][중급] 신규 아이디 추천
• [25번][중급] 약수의 개수와 덧셈
• [26번][중급] 약수의 합
• [27번][중급] 예산
• [28번][중급] 최대공약수와 최소공배수
• [29번][중급] K번째 수
• [30번][중급] 나머지가 1이 되는 수 찾기
• [31번][중급] 소수 찾기

 

TIL

• 오늘으 최대한 많은 문제를 풀어보려고 노력했고, 목표한 번호인 30번까을 초과하여 풀었다. 

• 풀면서 특히 재미 있었던 문제는 31번 소수 찾기 문제였다. 나는 이 문제에서 최대한 효율적으로 풀어보고자 머리를 써봤다. 
  • 2 ~ n 까지의 정수 중에 소수가 몇개 있는지 찾는 문제였다.
  • 나는 모든 숫자에 대해서 2 ~ n-1 값을 루프로 돌면서 검증하는 것은 속도 면에서 비효율 적이라고 생각했고, 2 ~부터 검증을 진행하면서 prime 배열에 넣어 놓은 값으로 검증을 진행한다면 훨씬 효율적이라고 생각했다.
    • 예를 들어, 입력받은 n : 100000이고, 현재까지 2 ~ 100까지 검증을 진행한 상황이라고 가정해보자.
    • 만약, 정석대로 2 ~ n-1 값 사이의 모든 정수로 101이 소수인지 판별하는 상황과, 이미 2~ 100까지 검증을 진행하며 배열에 쌓여 있는 소수 값으로만 검증을 진행하는 것은 시간복잡도 면에서 후자가 아주 효율적일 것이라고 생각했다.

 

• • 그리고 실제로 열심히 내가 생각한 바를 구현하기 위해 1시간 정도 시간을 들여 구현을 완료하였다. 그리고 나서 원론대로 간단하게도 구현을 해봤다. 같은 숫자를 넣고 실험해 본 결과, 100,000 정도 크기의 수를 넣으니 두 함수의 처리 속도가 꽤 차이났다. 재밌게도, 승자는 간단하게 원론적으로 구현한 후자!
    • 이유는, 실제로 구현을 하다 보니, n 값이 소수임을 판별할 때, 2와 n의 제곱근 사이의 정수로 판별을 하기 때문에, 생각했던 것보다 검증을 하기 위해 나눗셈을 하는 횟수가 줄어들었던 것이다!ㅋㅋㅋ
    • 자세한 내용은 포스팅을..!!ㅋㅋㅋㅋ

 

• 29번 K번째 수에서는 subArr를 만들기 위해 split 함수를 사용했는데, 이게 원본을 같이 잘라먹어서 제대로 값을 리턴하지 않았다. 해결은 원본  array를 스트링으로 변환해 준 뒤 temp 변수에 담아 temp를 split()을 사용해 다시 배열로 만들어 해결하였음
• 이 외에도, localeCompare() 등 공부해야 할 메서드가 너무나 많다.
• 특히, 오늘 느낀 점은, 프로그래머스 문제를 풀다보니, 연습문제 레벨에서는 자바스크립트의 내장함수를 경험하고 그것들을 필요에 따라 자유자제로 요리하는 법을 공부시키려고 하는 것 같았다.