알고리즘 공부.
이 게시글은, python의 기초적인 문법을 공부하며,
알고리즘을 공부하고 내가 풀이한 것을 적어낸 게시글입니다.
옹알이
문제
조카는 아직 "aya", "ye", "woo", "ma" 네 가지 발음만사용할 수 있다.
입력값이 ["aya", "yee", "u", "maa", "wyeoo"]라면, 발음 할 수 있는단어는 1개
입력값이 ["ayaye", "uuuma", "ye", "yemawoo", "ayaa"]라면, 발음 할 수있는 단어는3개
입출력 예 #1
["aya", "yee", "u", "maa", "wyeoo"]에서 발음할 수 있는 것은 "aya"뿐입니다. 따라서 1을 return합니다.
입출력 예 #2
["ayaye", "uuuma", "ye", "yemawoo", "ayaa"]에서 발음할 수 있는 것은
"aya" + "ye" = "ayaye", "ye", "ye" + "ma" + "woo" = "yemawoo"로 3개입니다.
따라서 3을 return합니다.
문제의 접근 방법
문제를 이해하는게 조금 시간이 걸렸다, 아직 초보자인 만큼 이해 능력과 분석능력이 부족했다.
결국, 여러번 읽고나서 출제자가 원하는 방향을 생각해냈는데.
입력으로 주어진 값에서 아이가 따라 읽을 수 있는 단어가 몇개인지 출력하라는 것이였다.
이에 관한 이해는 입출력 예제 2번을 보면 쉽게 이해할 수 있다.입출력 예 #2
["ayaye", "uuuma", "ye", "yemawoo", "ayaa"]에서 발음할 수 있는 것은
"aya" + "ye" = "ayaye", << 1개
"ye", <<2개
"ye" + "ma" + "woo" <<3개
= "yemawoo"로 3개입니다.
깨닫는순간, 바로 replace로 단어를 지우고,
비어있는 문자열이나 리스트는 조건문에 False를 반환하는데
if not False : 를 사용하여, 참이라면 카운트 하면 되겠다 생각했다.
나의 풀이
def solution(arr):
student = ["aya", "ye", "woo", "ma"]
cnt = 0
for i in range(len(arr)):
for j in range(len(student)):
arr[i] = arr[i].replace(student[j]," ")
arr[i]=arr[i].replace(" ","")
if(not arr[i]): cnt+=1
return cnt반복문을 돌며,
입력 리스트 arr[i]에 들어있는 string에서 replace를 진행하는데.
아이가 발음할 수 있는 리스트
student[j]에 있는 리스트 단어들로 문자열 변경을 통해 지워나간다.
이 문제에 함정이 있는데 바로
"wyeoo" 이 단어다, 아이는 발음할 수 없는 단어인데,
ye를 발음 할 수 있으니 지우고 나면
woo가 되는데, 또 지우면 발음할 수 있는 단어가 된다.
따라서 발음할수 있는 단어인지 확인하는 반복문에서는 지운 단어는 공백을 삽입했고.
최종적으로 발음 할수 있는 단어가 몇개인지 확인하는 조건문을 들어가기 전에,
공백 문자열을 모두 지워냈다.
다음에 올 숫자
문제
등비수열,등차수열인지 구분하여 다음에 올 숫자를 구하시오.
입력 : 1,2,3,4
출력 : 5
입력 : 2,4,6,8
출력 : 16
문제의 접근 방법
제한사항, 등비,등차수열이 아닌 경우의 수는 없다.
그렇다면, 조건문을 통해 등차수열인지 판단하고
등차 수열이 아니라면, 등비수열인지 조건문을 걸어 판단하지 말고
바로 값을 리턴하면 되겠다 생각했습니다.
리스트의 길이는 2보다 크다.
나의 풀이
def solution(arr):
if arr[2] - arr[1] == arr[1]-arr[0]:
return (arr[2]-arr[1]) + arr.pop()
return int((arr[2]/ arr[1])) * arr.pop()
arr = [4,16,64,256,1024] # 4096
print(solution(arr))일반항을 구하는 문제입니다.
등비수열의 경우, 공식을 사용할 필요 없이
arr[2]/arr[1]을 통해 구해진 몫을 int형으로 형변환후,
arr.pop()을통해 마지막 index값과 구해진 몫과 곱하여 반환했으며,
등차수열의 경우, 세가지 원소가 같은 공차를 가지고 있다면,
마찬가지로 공차 + 마지막원소값을 구하여 반환하여 풀이했습니다.
피자 나눠 먹기
문제
피자 조각 수 slice와 피자를 먹는 사람의 수 n이 주어질 때, n명의 사람이 최소 한 조각 이상 피자를 먹으려면 최소 몇 판의 피자를 시켜야 하는지 구하라
def solution(x,y):
result = int(y/x)
if(y%x != 0) : result+=1
return result인원수 / 피자 조각수 = 필요한 피자의 개수
인원수 % 피자조각수 = 공평하게 배분 못받은 사람이 있는지 확인
%연산을 통해, 나눴을때 남은 몫이 있는지 판단한다.
짝수 홀수 개수
문제
정수가 담긴 리스트 num_list가 주어질 때, num_list의 원소 중 짝수와 홀수의 개수를 담은 배열을 return 하도록 solution 함수를 완성해보세요.
나의 접근 방식
%연산에 관해 잘 알고있다면 누구나 쉽게 풀 수 있는 문제다.
n%2 는 홀수 또는 짝수의 값을 1 또는 0이 되므로,
이번 문제는 쉬운 문제의 로직이 아닌, 코드를 최대한 축약한 결괏값을 적어보려고 한다.
첫번째 풀이
def solution(arr):
l =[0,0]
for i in arr: l[0 if i%2==0 else 1] +=1
return l리스트의 주소를 찾는 [] 영역에서 연산을 하고,
홀수라면 0번째 인덱스를 +=1
짝수라면 1번째 인덱스를 +=1
이런 코드를 만들었는데, 다른사람의 풀이를 보니, 더 축약할 수 있어서 수정했다.
for i in arr: l[i%2] +=1if문으로 삼항 연산을 통해 하는 방법도 있겠으나, 위 코드는
i%2의 값은 0또는 1이기에 그 값 자체로도 조건 연산을 할 필요없이
바로 배열 인덱스로 삼아 사용하여, 코드를 축약했다.
