6월 - syh39/ProblemSolving GitHub Wiki
괄호변환
-
난이도 : Level 2
-
풀이 여부 : Y
-
소요 시간 : 1시간
-
유형 : Recursion (재귀)
-
주의 사항: 파이썬에서 제공하는 Recursion Depth는 설정값에 따라 다르긴 하지만, default 값은 1000이기 때문에 제한사항을 잘 보고 Recursion, Iterator 중 잘 선택해야 한다. 여기서는 문자열 길이가 1000이하 이기 때문에 Recursion으로 해도 상관없음.(Recursion Depth를 500으로 잘못알고 있어서 Iterator한 방법으로 풀려다 시간이 더 걸림.)
-
풀이 방법: 기본적인 Logic 자체가 문제에 나와있기 때문에 이를 이해하고 해석하여 코딩을 한다.
#올바른 괄호 문자열
def validation(p):
stack = []
for s in p:
if s == "(":
stack.append(s)
else:
if stack == [] and s == ")":
return False
else:
stack.pop()
return stack == []
def reversed_para(p):
return "".join(["(" if s ==")" else ")" for s in p ])
def recursion(p):
if p == "":
return ""
u, v = "", ""
#균형잡힌 괄호 문자열
zero_sum = 0
#2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
for s in p:
if zero_sum == 0 and u != "":
break
if s == "(":
zero_sum += 1
elif s == ")":
zero_sum -= 1
u += s
v = p.replace(u, "", 1)
#3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
if validation(u):
return u + recursion(v)
#4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
else:
return "(" + recursion(v) + ")" + reversed_para(u)[1:-1]
def solution(p):
#1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. & 만약 p가 이미 "올바른 괄호 문자열"이라면 그대로 return 하면 됩니다.
if p == "" or validation(p):
return p
return recursion(p)
N-Queen
-
출처: 연습문제
-
난이도 : Level 2
-
풀이 여부 : N
-
소요 시간 : 2시간
-
유형 : 완전탐색
-
풀이 방법: 위에서부터 모든 부분을 확인하면서, Queen 범위에 들어오는지 체크
-
Queen 범위 : 모든 가로, 세로, 대각선 --> 가로는 생각할 필요 없으므로, 세로, 대각선만 생각 (x1, y1), (x2, y2)가 있을 때,
- 세로 범위 : y1 == y2
- 대각선 범위 : abs(y1 - y2) == abs(x1 - x2)
이 범위 안에 들 경우 Queen 범위 안에 들기 때문에 체크 안함.
-
global answer
def check(result, cur_y, x):
for (row, col) in result:
# 세로 범위 & 대각선 범위에 드는지 확인
if col == x or abs(cur_y-row) == abs(x-col):
return False
return True
def queen(n, cur_y, result):
global answer
if cur_y == n:
answer += 1
return
for x in range(n):
if check(result, cur_y, x): #important 1
result.append((cur_y, x))
queen(n, cur_y+1, result[:])
result.pop() #important 2
def solution(n):
global answer
answer = 0
queen(n, 0, [])
return answer
- 틀린 이유:
- important 1 : 이 부분은 함수로 만들지 않고 구현했었는데, 함수로 구현 하지 않으면 이중 포문이 되고, Queen 범위를 체크하는 논리 구현이 힘들었음.
- important 2 : Queen을 놓으면서 체크하고 release를 해주어야 했는데, 하지 않으니 result 리스트에 Queen들이 쌓이게 되고 원하는 결과를 못 얻음.
멀리뛰기
-
출처: 연습문제
-
난이도 : Level 2
-
풀이 여부 : Y
-
소요 시간 : 30분
-
유형 : DP
-
풀이 방법: 규칙만 찾으면 되는 문제
| 칸의 개수 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1개 | 2개 | 3개 | 5개 | 8개 |
- dp[1] = 1
- dp[2] = 2
- dp[n] = dp[n-2] + dp[n-1]
줄 서는 방법
-
출처: 연습문제
-
난이도 : Level 2
-
풀이 여부 : N
-
소요 시간 : 2시간
-
유형 : 구현
-
못 푼 이유: 효율성 때문에
- 첫번째 시도: itertools 에 있는 permutations 사용 --> 시간초과
- 두번째 시도: permutations을 사용하되, 해당 k번째에 해당하면 바로 return --> 효율성 x
-
풀이 방법: 모든 경우를 보는 것이 아니라 해당하는 k번째 순서를 바로 아는 방법. 숫자들로 분류하고, 작은 문제로 쪼개는 방식.
n=3, k=4 일때, arr = [1, 2, 3]
1 [1, 2, 3]
2 [1, 3, 2]
3 [2, 1, 3]
4 [2, 3, 1] <-- 정답
5 [3, 1, 2]
6 [3, 2, 1]
첫번째 index에 있는 숫자들은 뒤에 있는 숫자들의 경우의 수로 개수가 정해짐. [1, 2, 3] [1, 3, 2]
--> (2, 3), (3, 2) 로 1의 개수가 정해짐.
--> 3! / 3 == 2! == 2 --> 즉, 첫번째 index의 숫자들은 2개로 쪼개짐.
--> 이렇게 하는 이유는, k번째 첫번째 index를 찾기 위해
import math
'''
offset: 맨 앞으로 있는 숫자를 기준으로 나누어주는 변수
k: 찾고자 하는 index
'''
def solution(n, k):
answer = []
#초기화
arr = list(range(1, n+1))
while n != 0:
offset = math.factorial(n-1)
index = (k-1)//offset
answer.append(arr.pop(index))
k = offset if k%offset==0 else k%offset
n -= 1
return answer
파일명 정렬
-
난이도 : Level 2
-
풀이 여부 : Y
-
소요 시간 : 30분
-
유형 : 정렬
-
풀이 방법:
- 문자열 --> HEADER와 NUMBER 분리
- HEADER정렬 --> NUMBER 정렬순
def split(s):
list_str = list(s.upper())
header, number = "", "0"
# HEADER 분리
while True:
if list_str[0].isdigit():
break
header += list_str.pop(0)
# NUMBER 분리
while True:
if list_str == [] or not list_str[0].isdigit():
break
number += list_str.pop(0)
return (header, int(number), s)
def solution(files):
result = [split(f) for f in files]
# HEADER정렬 --> NUMBER 정렬순
result.sort(key=lambda x: (x[0], x[1])) # sorted(result, kay=lambda x: (x[0], x[1]))
return [r[2] for r in result] # [s for header, number, s in result]
H-Index
-
출처: 정렬
-
난이도 : Level 2
-
풀이 여부 : Y
-
소요 시간 : 40분
-
유형 : 정렬
-
풀이 방법: 그냥 읽고 풀면 되는데, 말장난 같은 문제. 어휘력 테스트 같은 문제임. 별로 안 좋은 문제 같음. 안 푸는 것을 추천
파일명 정렬
-
난이도 : Level 2
-
풀이 여부 : Y
-
소요 시간 : 40분
-
유형 : 구현
-
풀이 방법:
- 주어진 n을 k진수로 바꾼다 (conversion 함수). 단, 바뀌어진 n값에 "0"의 포함 여부를 확인해야 하므로 output 값은 String type으로 함.
- 바꿔진 n값을 windowing하면서(offset 변수) 소수가 있는지 판별 (isPrime 함수) 한다.
- 만일, 소수라면 문제에서 주어진 조건들을 확인한다. !! isPrime 함수에서 기본적인 O(n) 시간복잡도가 되도록 짜면, 시간초과가 뜬다. n을 k진수로 바꾸었을 때, 바뀌어진 n값이 10진수로 봤을 때 억단위가 될 수도 있음.
#시간복잡도: O(n)
def isPrime(target):
target = int(target)
if target < 2:
return False
for n in range(2, target):
if target % n == 0:
return False
return True
--> 이에 대한 해결 방법으로 제곱근(sqrt)나 더 효율적인 것으로 유명한 에라토스테네스의 체를 사용하면 된다. (경험상, 제곱근까지만 써도 왠만해서 다 통과됨. 백준 문제 제외)
#시간복잡도: O(n^(1/2))
import math
def isPrime(target):
target = int(target)
if target < 2:
return False
for n in range(2, int(math.sqrt(target))+1):
if target % n == 0:
return False
return True
결과
def conversion(n, k):
result = ""
while n:
result = str(n%k) + result
n = n//k
return result
def isPrime(target):
target = int(target)
if target < 2:
return False
for n in range(2, target):
if target % n == 0:
return False
return True
def solution(n, k):
answer = 0
if n < 2:
return 0
# 1. 주어진 n을 k진수로 바꾼다.
target = conversion(n, k)
for offset in range(1, len(target)+1):
idx = 0
while idx+offset <= len(target):
# 2. 바꿔진 n값을 windowing하면서(offset 변수) 소수가 있는지 판별(isPrime 함수)한다.
if "0" not in target[idx:idx+offset] and isPrime(target[idx:idx+offset]):
# 3. 만일, 소수라면 문제에서 주어진 조건들을 확인한다.
if idx == 0 and idx+offset < len(target) and target[idx+offset] == "0":
answer += 1
elif idx-1>=0 and target[idx-1] == "0" and idx+offset < len(target) and target[idx+offset] == "0":
answer += 1
elif idx-1>=0 and target[idx-1] == '0' and idx+offset == len(target):
answer += 1
elif idx == 0 and idx+offset == len(target):
answer += 1
idx += 1
return answer