LeetCode 코테 대비

영슈·2023년 9월 22일

이번에 넛지헬스케어 서류 통과를 하며 , 코테를 1시간 가량 진행하게 되었다.
따라서 , LeetCode 내 카테고리에서 문제를 하나씩 선정해서 풀고 있다.

Leetcode 3. Longest Substring Without Repeating Characters

문제 링크

https://leetcode.com/problems/longest-substring-without-repeating-characters/

문제 해석

문자열 s 가 주어짐
중복된 문자 없이 구성된 가장 긴 문자열 길이 리턴

문제 해결

dp 를 활용해서 해결하자!
i 번째 요소가 범위 안에 없을시에는 그전 i +1
있을시에는 몇번째 index 에 존재하는지 확인후 i - index

슈도 코드

dp = []
for i in range(1,s)
	if s[i] in s[i-dp[i-1 ~ i]:
		index = dp[i-1] 부터 s[i] 검색
		dp[i] = i - index
		continue
	dp[i] = dp[i-1]+1
return max(dp[i])

결과

사담

sliding window 카테고리 였으나 , 그냥 dp 연습해보고 싶어서 생각하고 풀었다.
dp 를 활용한 만큼 메모리는 낮은 퍼센트

Leetcode 6. Zigzag Conversion

문제 링크

https://leetcode.com/problems/zigzag-conversion/submissions/?envType=study-plan-v2&envId=top-interview-150

문제 해석

지그재그 패턴으로 변환하는 문자열 제공
지그재그 할 높이 제공 numRows

문제 해결

패턴을 파악하자!
두가지 경우로 나누어서 계산하자 ! ( numRows -1 까지 인 경우 , 대각선 인 경우 )
문자열마다 저장 후 , 한 문자열에 다 합쳐서 리턴

PAYPALISHIRING , 3 =>
P A H N
A P L S I I G
Y I R

0 4 8 [0]
1 3 5 7 [1]
2 6 [2]
0 1 ( (i/num)%2 == 0 ) <-> 2 3 ( (i/num) % 2 == 1 )

슈도 코드

ary = [""] * ( numRows +1 )
for i in range(s.length):
	if int(i/num)%2==0:
		ary[i % num] += s[i]
	elses:
		ary[num-i%num] +=s[i]

for element in ary:
	answer += element
return answer

결과

사담

문자열 활용 문제
단순한 문제

Leetcode 11. Container With Most Water

문제 링크

https://leetcode.com/problems/container-with-most-water/

문제 해석

높이 배열이 주어짐
두 가지 endpoint 를 통해 , 담을수 있는 최대의 물 양 리턴

문제 해결

왼쪽과 오른쪽 중 작은값 과 그 사이 갯수를 곱하면 정답
더 작은 쪽을 땡김
가장 큰 값을 저장하고 있어서 리턴

슈도 코드

n = 처음
v = 끝
max_num = 0
while n!=v
	min_num = height[v] 랑 height[n] 중 비교
	if 최대 < min_num * (v-n)
		max_num = min_num *(v-n)
	if height[n] 이 height[v] 보다 작다면
		n+=1
	else
		v-=1
return max_num

결과

사담

처음 헷갈려서 , 다르게 풀었으나 결과 값 보고 바로 해결
투 포인터로 계속 큰 값을 추구하는게 해결

Leetcode 322. Coin Change

문제 링크

https://leetcode.com/problems/coin-change/description/?envType=study-plan-v2&envId=top-interview-150

문제 해석

1개~12개의 coins 배열
coins 를 조합해서 만들어 내야하는 amount
amount 를 만드는 최소한의 coin 개수를 리턴

문제 해결

D.P 로 점차 증가시켜 나가자 ( amount 가 0부터 10000 까지 매우 작으므로 )
기존 값과 현재 coin 으로 만들수 있는 값을 비교해서 작은 것을 선택하자

슈도 코드

dp_ary = [0] * amount+1
for i in range(1,amount+1)
	for coin in coins
		if i-coin<0
			continue
		if dp_ary[i]==0 and dp_ary[i-coin]!=0
			dp_ary[i] = dp_ary[i-coin]+1
			continue
		if dp_ary[i] > dp_ary[i-coin] +1
			dp_ary[i] = dp_ary[i-coin] +1
return dp_ary[amoint]

결과

=> 해당 문제에서 정답은 20 을 요구하나 , 9를 반환

초기 ary 의 값을 0 이 아닌 최대값으로 수정하자

사담

물론 당연히 최대값을 선언한 후 , 조건문을 비교하면 더 쉽게 되지만 첫번째 로직도 이론 상으론 완벽하다고 생각되는데 왜 오답을 출력하는지 잘 모르겠다.
문제의 케이스를 잘 생각해서 , 최소값을 구할 때 는 미리 최대값을 넣어놓고 최대값을 구할 때는 미리 최소 값을 넣어놓는게 더 쉽게 풀 수 있는거 같다.