자바스크립트 알고리즘 문제 정리
강의에서 공부했던 문제들을 정리해보며 꼭 다시 풀 문제들을 선별하는 과정을 가지려고 한다. 이 문제들을 무기로 문제풀이를 진행할 것이다.
★ : 조금이라도 생소한 것이 있었던 문제
★★ : 풀 수는 있었으나 새로운 접근을 배워야 하는 문제
★★★ : 꼭 여러번 풀어서 내 것으로 만들어야 할 문제
섹션1 : 기본 문제 풀이
1. 세 수 중 최소값
그냥 최소값을 구하는 간단한 알고리즘
두 가지 방법으로 간단하게 풀 수 있다.
if문3 번Math.min
2. 삼각형 판별하기
max 값을 찾아 나머지 두 개의 합 보다 짧음을 보이면 된다
3. 연필 개수 (★)
C++로 풀 때에는 알아서 소수점 버림이 됐지만 자바스크립트에서는 되지 않아서 당황했던 문제
Math.ceil(N / 2)로 간단히 풀 수 있으나,
Math.ceil메서드가 좀 낯설었다.
4. 1부터 N까지 합 출력하기
그냥 1~n 반복문 돌리면 됨
5. 최솟값 구하기 (★)
그냥 최솟값 알고리즘임. 하지만 여기서도 배울 점이 있었다.
min = Number.MAX_SAFE_INTEGER으로 놓고 쓰는 방법Math.min()메서드 사용 시, 전개 연산자 사용하기
6. 홀수
이 문제에서는 최소값을 구할 때,
min = Number.MAX_SAFE_INTEGER을 사용할 수 없는 문제였다. (배열의 첫 번째 수가 홀수라는 것을 장담할 수 없기 때문)이 경우에는 그냥 첫 원소를
min으로 놓는 수밖에 없다
7. 10부제
그냥 6번 문제와 거의 동일하다고 볼 수 있다.
8. 일곱 난쟁이 (★★)
splice는 뒤에서 부터!!
두 합 = 총합 - 100 이 되는 2개를 이중 for문으로 찾아서
splice해서 풀면 되는 간단한 문제였는데, 중간에 애를 좀 먹었다.
splice를 앞에서 부터 하면 뒤의 원소의 index가 변한다는 것!따라서
splice는 뒤에서 부터 진행해 주어야 한다!!
9. A를 #으로 (★★)
방법1)
for문,if문으로 answer 문자열에 추가
지금 와서야 javascript의 문자열은 *index로 특정 문자만 바꿀 수 없다는 것을 알았다;;;;
방법2)
replace메서드 사용하기
정규식의 경우 Case by Case로 조금씩 학습해 나가야 겠다.
replace(/A/g, '#')의 경우 모든(g) 'A'를 '#'으로 replace!
10. 문자 찾기 (★★)
방법1)
for문사용하기 (무지성 풀이)
방법2)
split메서드 사용하기 (★★)
:split(t)로 t를 기준으로 나누고 1을 빼 주는 idea
t가 맨 마지막에 있더라도 마지막에 빈 문자열 ''가 추가되므로 예외없이 사용할 수 있다.
11. 대문자 찾기 (★)
toUpperCase를 사용하여 비교
12. 대문자로 통일 (★★)
방법1)
toUpperCase사용하기 (무지성 풀이)
방법2) ASCII 코드 (★★)
해당 문자가'a'.charCodeAt()과'z'.charCodeAt()값 사이에 있으면,
String.fromCharCode()를 사용하여 대문자로 변환해 준다
13. 대소문자 변환 (★)
12번 혹은 13번에서 배운 내용을 사용하여 풀 수 있다.
14. 가장 긴 문자열
length 메서드를 활용할 수 있는지 묻는 문제.
그 외에는 그냥 최대값 찾기 문제와 동일하다.
15. 가운데 문자 출력 (★)
- javascript에서는 자동으로 정수로 형변환을 해주지 않음을 상기해야 한다.
Math.floor을 이용하여 소수점 이하는 버림을 해 주어야 한다.slice메서드와subString메서드에 대해 한 번 짚고 넘어갈 수 있는 문제이다 (짝수형의 경우)
-> slice의 경우 start 인덱스를 넣어주지 않으면 자동으로 0이 되고, 음수 인덱스를 사용할 수 있다.
16. 중복문자제거 (★★★)
방법1) (내풀이) 배열,
includes
: 배열arr에 해당 문자가 없으면(includes메서드)arr에push후answer에 더해줌
방법2)
indexOf메서드 사용 (★★★)
:indexOf메서드는 첫 번째 원소만 반환하므로,indexOf메서드가 반환하는 값이 아니면 두 번째 이상 등장한 것임
17. 중복 단어 제거 (★★★)
방법1) (내풀이) 배열,
includes
: 16번의 방법과 동일하게 풀었음.
방법2)
filter메서드와indexOf메서드 사용 (★★★)
:filter메서드를 요긴하게 쓸 수 있는 것 같다.
이 문제의 코드를 그냥 외워버리자!
섹션2 : 1, 2차원 배열 탐색
1. 큰 수 출력하기
그냥 반복문 돌리면서 조건에 맞는 원소만
answer배열에 추가
2. 보이는 학생
그냥
max변수 놓고 풀면 된다. 크게 특별할 것은 없었음
3. 가위바위보
그냥 가위바위보 문제. 특별한건 없음
4.점수 계산 (★★)
: flag 변수 쓸 필요도 없었음...
방법1) (내풀이) flag 변수 사용하여 풀기
방법2) 다시 풀어보자...
5. 등수구하기 (★★)
방법1)
sort메소드 사용
방법2) 이중
for문사용하기 (★★)
6. 격자판 최대합 (★)
이중 for문 한 번에 풀 수 있었음.
7. 봉우리 (★)
flag변수를 써야하는 상황이면 과감하게 쓰자!
고민하지 말고...
섹션3 : 문자열 탐색
1. 회문문자열
방법1) 문자열 메소드 사용하여
split('').reverse().join('')하여 풀기
방법2) index를 이용하여 앞뒤로 짝지어서 풀기
2. 유효한 팰린드롬 (★★)
1번 문제와 동일하게 풀 수 있으나,
replace에 대하여 좀 알아야 할 것 같다!
이 문제의 경우/[^a-z]/g였음!정규식은 날잡고 하루 정리하는 시간을 가져야 할 것 같다.
3. 숫자만 추출 (★★)
: isNaN() 함수
isNaN(x)했을 때false가 나오는 x만 answer에 넣어주면 된다.
4. 가장 짧은 문자거리 (★★★)
방법1) (내풀이) 그냥 이중 for문 돌려서 절대값으로 풀었음 (N^2) (★)
->Math.abs()사용
방법2) 왼쪽으로 한 번, 오른쪽으로 한 번 (N) (★★★)
->dist변수를 t를 만나면 0으로 리셋, 그리고 한 칸마다 1씩 증가
5. 문자열 압축 (★★)
배열의 인덱스를 벗어나는 것을 두려워 하지 말라!
섹션4 : 완전 탐색(브루트 포스)
1. 자릿수의 합 (★)
방법1) 10으로 나눈 나머지로 풀기
방법2)
toString().split('').reduce()사용 (★)
2. 뒤집은 소수 (★★)
: 숫자를 뒤집는 방법에 따라 달라진다.
(★★) 소수 판별 알고리즘 : Math.sqrt() 사용!
방법1)
string내장 메소드 사용
방법2) 10으로 나눈 나머지를 10으로 곱해 더하기!
3. 멘토링 (★★)
'언제 브루트 포스를 쓸 것인가'에 대한 판단이 중요한 것 같다.
뭔가 쌈빡한 풀이가 있을 것 같지만, 입력의 크기를 보고 냅다 돌리는 것이 중요한 것 같다.풀이에서는 for문을 4번 돌렸지만, 나는 순서 검증의 과정에서는 그냥
includes메소드를 사용하여 3번만 돌렸다.
4. 졸업 선물 (★★★)
: 목표치에서 빼 나가는 idea!
예산이 정해진 상황의 경우에는,
sum을 0에서 더해나가는 것보다, 목표치에서 빼나가는 것이 더 효율적일 수도 있음을 배웠다.
5. K번째 큰 수 (★★)
Set으로 중복을 제거하는 방법을 배웠다.
섹션5 : 효율성 (투 포인터 알고리즘 ,슬라이딩 윈도우, 해쉬)
1. 두 배열 합치기 (★★)
: 전형적인 투 포인터 문제인듯.
다만 한 배열이 다 끝났을 때 후처리를 어떻게 해 줄지가 문제임.
내 풀이) 나머지 배열을
slice로 떼다가 넣어줌
Solution 풀이) 각각
while돌려서 끝까지 push 해줌 (★★)
2. 공통원소 구하기 (★)
1번 문제와 동일하게 풀 수 있으나 하나의 배열이 먼저 끝에 다다른 경우를 고려할 필요가 없어서 훨씬 쉬운 문제였다.
3. 연속 부분수열 (★★★)
: 코드를 보고 한참 보다가... 아이디어를 보고 박수를 쳤음
오른쪽 포인터를 왼쪽 포인터가 따라오게끔 하는 아이디어... (★★★)
4. 연속 부분수열 2 (★★★)
: 아직도 익숙하지 않나보다 ㅠㅠ 반드시 여러번 풀고 내 것으로 체화시키자!
마찬가지로 오른쪽 포인터를 왼쪽 포인터가 따라오게끔 하는 아이디어... (★★★)
5. 최대 매출
그냥 전형적인 슬라이딩 윈도우알고리즘 문제 같다.
6. 학급 회장(해쉬), 7. 아나그램 (★★★)
charCodeAt과fromCharCode를 이용하여 풀었으나,
Map을 활용하는 방법을 알아두도록 하자!
8. 모든 아나그램 (★★★)
6, 7번 문제의 심화 버전 문제이다.
compareMaps를 구현하는 방법을 잘 알아두자!
여기서 슬라이딩 윈도우의 핵심 포인트는 앞에거 한 칸 더해주고 뒤에거 한 칸 빼는 것!
섹션5 : 자료구조(스택, 큐)
1. 올바른 괄호
지금까지 계속 배열로 풀었지만, 굳이 그럴 필요가 있나 싶어 그냥
stack = 0으로 놓고 풀었다.
2. 괄호문자 제거
마찬가지로 배열을 사용하지 않고,
stack = 0으로 놓고 풀었더니 무난히 풀 수 있었다. 뭔가 문제를 안풀면서 사고력이 올라간 것 같다..
3.
