Programmers LV1을 끝내고 LV2 문제들을 풀고 있다. 12월이 다가오니 날씨가 영하권이 되버렸다. 날도 추워진 만큼 다들 감기 조심하시길🐶
월화수 3일 간 약 20문제 정도 푼 것 같다..
LV2 문제들을 풀어보니 자료구조에 대한 이해를 요하는 문제, 수학적인 사고력?과 기본적인 알고리즘(BFS, DFS) 등을 요구하는 문제들도 있는 것 같다.(내가 푼 방식이 그럴 수도)
<문제 풀이>
JadenCase 문자열 만들기
문제 설명
JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 단, 첫 문자가 알파벳이 아닐 때에는 이어지는 알파벳은 소문자로 쓰면 됩니다. (첫 번째 입출력 예 참고)
문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요.
- 제한 조건
s는 길이 1 이상 200 이하인 문자열입니다.
s는 알파벳과 숫자, 공백문자(" ")로 이루어져 있습니다.
숫자는 단어의 첫 문자로만 나옵니다.
숫자로만 이루어진 단어는 없습니다.
공백문자가 연속해서 나올 수 있습니다.
def solution(s):
word = ''
answer = ''
for i in range(len(s)):
if s[i] == ' ':
answer += word + ' '
word = ''
else:
if word == '':
if s[i] not in '1234567890':
word += s[i].upper()
else:
word += s[i]
else:
word += s[i].lower()
if word != '':
answer += word
return answer< 풀이 과정 >
초기엔 단순히 주어진 s문자열을 split()하여 해결하려했으나, 공백이 연속인 문제를 해결하는 방법을 찾지 못하였다. 따라서, for문을 이용하여 s문자열 내 모든 문자를 탐색하는 완전탐색 방법을 이용하였다.
- 최종 정답인 answer 문자열과 중간 점검을 해주는 word 문자열을 생성.
- 공백이 연속해서 나올 수 있다는 점을 감안하여 공백인 경우 word 문자열 + 공백으로 해결
- 공백이 아닌 경우, word가 비어있는 문자열이라면, 첫 글자가 숫자인 경우와 아닌 경우로 구분해주고, word에 첫 글자가 추가된 이후 이외의 글자들은 소문자로 추가하여 준다.
- word가 비어있는 문자열이 아니라면, answer로 출력
올바른 괄호
문제 설명
괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어
"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
- 제한사항
문자열 s의 길이 : 100,000 이하의 자연수
문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.
def solution(s):
stack = []
for i in s:
if i == '(':
stack.append(i)
else:
if stack:
stack.pop()
else:
return False
if stack:
return False
return Truequeue 자료구조를 통해 학습했던 pop()을 활용하여 해결!
< 풀이 과정 >
1. 스택 자료구조를 이용하여 풀이
2. () 형태로 문자열이 구성되어있고, )()(의 경우는 올바르지 않은 괄호이기에 주어진 문자열 내 '('가 있다면 스택에 추가해주고, ')'가 들어오는 순간 '('를 제거하는 방식으로 처리
3. 따라서 스택 내 '(' 문자가 존재한다면 False, 문자가 존재하지 않는 경우라면 True 처리
다음 큰 숫자
def solution(n):
one_cnt = bin(n).count('1')
while True:
n += 1
if one_cnt == bin(n).count('1'):
break
return n< 풀이 과정 >
- 우선 주어진 n의 2진 변환 후의 1의 개수를 세어준다
- while 문으로 n에 1씩 더해가면서 n의 이진변환 개수와 앞에서 세어논 개수가 같으면 중단하고 n을 리턴한다.
이진 변환 반복하기
문제 설명
0과 1로 이루어진 어떤 문자열 x에 대한 이진 변환을 다음과 같이 정의합니다.
x의 모든 0을 제거합니다.
x의 길이를 c라고 하면, x를 "c를 2진법으로 표현한 문자열"로 바꿉니다.
예를 들어, x = "0111010"이라면, x에 이진 변환을 가하면 x = "0111010" -> "1111" -> "100" 이 됩니다.
0과 1로 이루어진 문자열 s가 매개변수로 주어집니다. s가 "1"이 될 때까지 계속해서 s에 이진 변환을 가했을 때, 이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 각각 배열에 담아 return 하도록 solution 함수를 완성해주세요.
- 제한사항
s의 길이는 1 이상 150,000 이하입니다.
s에는 '1'이 최소 하나 이상 포함되어 있습니다.
def solution(s):
cnt = 0
zero_cnt = 0
while True:
if s == '1':
break
zero_cnt += s.count('0')
s = s.replace('0', '')
s = bin(len(s))[2:]
cnt += 1
answer = [cnt, zero_cnt]
return answer< 풀이 과정 >
주어진 문자열 s에서 0을 없애고 이진 변환하는 과정을 return 하는 문제.
- 이진변환 횟수 cnt 변수와 0을 없애는 zero_cnt 변수 생성.
- True로 반복하고, 문자 열이 1이라면 넘어가는 형태로 진행.
- 문자열에 '0'이 있다면, zero_cnt에 0 개수만큼 추가.
- 주어진 문자열에서 0을 공백으로 대체하고 이진변환하기. bin() 함수를 이용하면 숫자 > 0b1010 형태로 출력가능!
- 이진변환했으므로 cnt += 1처리!
카펫
Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.
Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.
Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.
- 제한사항
갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
def solution(brown, yellow):
carpet = yellow + brown
for width in range(carpet, 2, -1):
if carpet % width == 0:
height = carpet // width
if yellow == (width-2) * (height-2):
return [width, height]< 풀이 과정 >
수학적인 방식?으로 접근하여 문제를 해결하였다.
가로를 width, 세로를 height라 하면 주어진 brown 값은 2width + 2(height-2)로 구할 수 있고, yellow 값은 (width-2)*(height-2)로 구할 수 있다.
- yellow와 brown수를 더하면 나오는 값은 총 카펫 수. 즉 가로*세로의 값과 동일
- 가로가 세로보다 무조건 크거나 같으므로 for문을 역순으로 이용하여 carpet을 나눈 가로 값들을 구함.
- 이때 height는 carpet // width 임을 이용.
- 앞서 구했던 가로, 세로를 이용한 brown, yellow값을 적용하여 결과 return!
영어 끝말잇기
문제 설명
1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.
1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.
마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.
앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.
이전에 등장했던 단어는 사용할 수 없습니다.
한 글자인 단어는 인정되지 않습니다.
다음은 3명이 끝말잇기를 하는 상황을 나타냅니다.
- tank → kick → know → wheel → land → dream → mother → robot → tank
- 위 끝말잇기는 다음과 같이 진행됩니다.
1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.
2번 사람이 자신의 첫 번째 차례에 kick을 말합니다.
3번 사람이 자신의 첫 번째 차례에 know를 말합니다.
1번 사람이 자신의 두 번째 차례에 wheel을 말합니다.
(계속 진행)
끝말잇기를 계속 진행해 나가다 보면, 3번 사람이 자신의 세 번째 차례에 말한 tank 라는 단어는 이전에 등장했던 단어이므로 탈락하게 됩니다.
사람의 수 n과 사람들이 순서대로 말한 단어 words 가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해서 return 하도록 solution 함수를 완성해주세요.- 제한 사항
끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.
words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.
단어의 길이는 2 이상 50 이하입니다.
모든 단어는 알파벳 소문자로만 이루어져 있습니다.
끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.
정답은 [ 번호, 차례 ] 형태로 return 해주세요.
만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.
def solution(n, words):
for i in range(1, len(words)):
if words[i] in words[:i] or words[i][0] != words[i-1][-1]:
return [i%n+1, i//n+1]
else:
return [0, 0]<풀이 과정>
문제는 길었으나 생각보다 구현이 어렵지 않았던 문제!
주어진 단어들로 for문을 돌려 현재 외친 단어가 앞서 불렸거나, 현재 외친 단어의 첫글자가 이전 단어의 끝글자와 다른 경우의 말한 사람, 몇번째 외친 단어인지를 찾는 문제
1) 외친 사람의 번호의 경우, 현재 주어진 words의 인덱스를 사람 수로 나눈 나머지 값에 +1을 해준다. (인덱스는 0부터 시작하기 때문)
2) 외친 사람의 몇번 째 차례인지는 words의 인덱스를 사람 수로 나눈 몫에 +1을 해준다.
양궁대회
문제 설명
카카오배 양궁대회가 열렸습니다.
라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다.
카카오배 양궁대회 운영위원회는 한 선수의 연속 우승보다는 다양한 선수들이 양궁대회에서 우승하기를 원합니다. 따라서, 양궁대회 운영위원회는 결승전 규칙을 전 대회 우승자인 라이언에게 불리하게 다음과 같이 정했습니다.
어피치가 화살 n발을 다 쏜 후에 라이언이 화살 n발을 쏩니다.
점수를 계산합니다.
과녁판은 아래 사진처럼 생겼으며 가장 작은 원의 과녁 점수는 10점이고 가장 큰 원의 바깥쪽은 과녁 점수가 0점입니다. 012022공채문제_양궁대회_01.png
만약, k(k는 1~10사이의 자연수)점을 어피치가 a발을 맞혔고 라이언이 b발을 맞혔을 경우 더 많은 화살을 k점에 맞힌 선수가 k 점을 가져갑니다. 단, a = b일 경우는 어피치가 k점을 가져갑니다. k점을 여러 발 맞혀도 k점 보다 많은 점수를 가져가는 게 아니고 k점만 가져가는 것을 유의하세요. 또한 a = b = 0 인 경우, 즉, 라이언과 어피치 모두 k점에 단 하나의 화살도 맞히지 못한 경우는 어느 누구도 k점을 가져가지 않습니다.
예를 들어, 어피치가 10점을 2발 맞혔고 라이언도 10점을 2발 맞혔을 경우 어피치가 10점을 가져갑니다.
다른 예로, 어피치가 10점을 0발 맞혔고 라이언이 10점을 2발 맞혔을 경우 라이언이 10점을 가져갑니다.
모든 과녁 점수에 대하여 각 선수의 최종 점수를 계산합니다.
최종 점수가 더 높은 선수를 우승자로 결정합니다. 단, 최종 점수가 같을 경우 어피치를 우승자로 결정합니다.
현재 상황은 어피치가 화살 n발을 다 쏜 후이고 라이언이 화살을 쏠 차례입니다.
라이언은 어피치를 가장 큰 점수 차이로 이기기 위해서 n발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 구하려고 합니다.
화살의 개수를 담은 자연수 n, 어피치가 맞힌 과녁 점수의 개수를 10점부터 0점까지 순서대로 담은 정수 배열 info가 매개변수로 주어집니다. 이때, 라이언이 가장 큰 점수 차이로 우승하기 위해 n발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 10점부터 0점까지 순서대로 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 만약, 라이언이 우승할 수 없는 경우(무조건 지거나 비기는 경우)는 [-1]을 return 해주세요.
- 제한사항
1 ≤ n ≤ 10
info의 길이 = 11
0 ≤ info의 원소 ≤ n
info의 원소 총합 = n
info의 i번째 원소는 과녁의 10 - i 점을 맞힌 화살 개수입니다. ( i는 0~10 사이의 정수입니다.)
라이언이 우승할 방법이 있는 경우, return 할 정수 배열의 길이는 11입니다.
0 ≤ return할 정수 배열의 원소 ≤ n
return할 정수 배열의 원소 총합 = n (꼭 n발을 다 쏴야 합니다.)
return할 정수 배열의 i번째 원소는 과녁의 10 - i 점을 맞힌 화살 개수입니다. ( i는 0~10 사이의 정수입니다.)
라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.
가장 낮은 점수를 맞힌 개수가 같을 경우 계속해서 그다음으로 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.
예를 들어, [2,3,1,0,0,0,0,1,3,0,0]과 [2,1,0,2,0,0,0,2,3,0,0]를 비교하면 [2,1,0,2,0,0,0,2,3,0,0]를 return 해야 합니다.
다른 예로, [0,0,2,3,4,1,0,0,0,0,0]과 [9,0,0,0,0,0,0,0,1,0,0]를 비교하면[9,0,0,0,0,0,0,0,1,0,0]를 return 해야 합니다.
라이언이 우승할 방법이 없는 경우, return 할 정수 배열의 길이는 1입니다.
라이언이 어떻게 화살을 쏘든 라이언의 점수가 어피치의 점수보다 낮거나 같으면 [-1]을 return 해야 합니다.
from collections import deque
max_diff = 0
def bfs(n, info):
answer = []
global max_diff
queue = deque()
queue.append([0, [0]*11])
while queue:
arrow, array = queue.popleft()
if sum(array) == n:
ryan, appeach = 0, 0
for i in range(11):
if info[i] == 0 and array[i] == 0:
continue
if info[i] > array[i]:
appeach += 10-i
else:
ryan += 10-i
if ryan > appeach and ryan - appeach > max_diff:
max_diff = ryan - appeach
answer = array
if ryan - appeach == max_diff:
for i in range(len(answer)-1, 0, -1):
if answer[i] < array[i]:
answer = array
break
elif arrow == 10:
stop = array.copy()
stop[arrow] = n - sum(array)
queue.append([arrow+1, stop])
elif sum(array) > n:
continue
else:
choicezero = array.copy()
choicezero[arrow] = 0
queue.append([arrow+1, choicezero])
plusone = array.copy()
plusone[arrow] = info[arrow] + 1
queue.append([arrow+1, plusone])
return answer
def solution(n, info):
max_diff = 0
answer = bfs(n, info)
if len(answer) > 0:
return answer
else:
return [-1]< 풀이 과정 >
구현에 상당히 애를 먹었던 문제.. 약 2시간? 정도만에 겨우 해결한 것 같다.
경우의 수를 생각했던 것보다 더 많이 신경썼어야 했고, 특히 당연히 최대 10발인 것을 까먹고 계속해서 문제를 풀었기에 더 오래 걸렸다.
- BFS 탐색을 이용하여 라이언의 화살 점수 배열을 계산함.
- 어피치와 라이언 간의 점수 차이를 최대로 늘려주기 위해 max_diff = 0이라는 전역변수 적용!
- deque()를 이용하여 반복 진행
4-1) 주어진 화살 수 n과 라이언의 배열이 같은 경우에 for문으로 라이언과 어피치의 점수를 계산하도록 하였다. 이를 자세히 살펴보면 어피치, 라이언의 배열이 양쪽 모두 0인 경우 넘어가고, 어피치 쪽이 크면 어피치 값 += 10-i, 라이언이 크면 라이언 += 10-i를 해주었다.
이후 라이언의 점수가 어피치보다 크다면, max_diff값 update 후 정답에 현재 라이언의 점수 배열 update
이때 문제에서 "라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요."를 요구하였기에 현재 라이언 점수 - 어피치 점수가 max_diff와 동일하다면, for문을 역순으로 돌려 더 낮은 점수가 큰 배열을 정답으로 update!
4-2) 이부분을 놓쳐 시간이 오래걸렸다.. 주어진 화살이 10발 일때, 마지막 한 발을 어느 곳에 배치하든 상관이 없지만 이 코드가 없다면 문제에서 요구한 더 낮은 점수가 나오도록 하는 배열을 맞춰줄 수 없기 때문이다. 다음 과녘을 쏠 화살이 없으므로 다음 큐에 들어갈 arrow는 아무 값을 대입하였다.
4-3) 라이언이 쏜 화살의 배열이 주어진 화살 수 n보다 크다면 continue
4-4) 라이언이 어피치를 이기려면 어피치가 쏜 점수칸은 0으로, 어피치가 쏜 화살보다 1개 더 많이 쏴서 이기는 방식이 있어 2가지 case로 나누어 계산하였다.
- 최종 solution함수에는 array배열 대신 bfs(n, info)의 결과로 answer를 가져오도록 하였고, 주어진 배열이 없다면 [-1]을 리턴하도록 하였다.
✨11월 마지막 주(11/28 ~ 11/30) 중간 점검
- LV2에 들어서니 문제 푸는 시간보다 생각하는 시간이 많아졌다.
- SQL 공부도 시작하였다. (이전에 따놓았던 SQLD 자격증 재공부 중... 말나온김에 보수교육도 받아서 영구처리 전환할 계획)
- 꾸준함의 중요성을 느끼고 있다.. 날마다 못해도 2시간 씩은 코테 공부에 시간투자를 하려 하고 있다.
- 생활패턴의 변화를 가져와야 할 듯하다.. 곧 학교 기말고사도 준비해야하고,, 9, 10월 때 처럼 잠 자는 시간을 다시 줄여야 하나... 싶다
- 12/1 부터 naver AI boostcamp 지원 시작! 코테 공부를 더 바짝 끌어올릴 생각이다.
- 코테 공부만 주구장창하니 데이터 분석에 소홀해진 것 같다. (겨울에 공모전 나갈 계획!)
❗To do List ~ 2023.02
- Coding test 준비 (naver AI boostcamp 1月 초중순 예상), SW마에스트로 내년 상반기 (2月 예상)
- 12月 내 naver AI boostcamp 영상 (머신러닝, 딥러닝 등 데이터 분석 공부?)
- SQL Study (매주 日 /// SQLD 보수교육)
- 22년 2학기 KHU마무리 (report, 기말 등등..)
- Texas DataScientist masterclass 마무리 (12月)
할 일들이 태산이다.. 열심히 또 한번 달려보자!
