조이스틱
https://programmers.co.kr/learn/courses/30/lessons/42860
내 풀이 - 통과
def solution(name):
answer = 0
### 위, 아래 개수 세기 ###
for n in name:
asc = ord(n) - ord("A")
if asc > 13:
asc = 13 - (asc % 13)
answer += asc
### 왼, 오 개수 세기 ###
### A 가 없거나 뒤쪽에 있을 경우 => 오른쪽으로 가는게 가장 빠름
idx = name.find("A")
if idx == -1 or idx > len(name) // 2:
answer += len(name) - 1
return answer
### 왼쪽으로 가는 경우 확인
path = len(name) - 1
for i in range(1, len(name)):
tmp = i-1
if name[i] == "A":
n = name[i:] + name[:i]
while n[0] == "A":
n = n[1:]
tmp += len(n)-1
path = min(path, tmp)
answer += path
return answer-
위, 아래로 움직일 때의 횟수 세기
A ~ M까지는 위로,N ~ Z까지는 아래로 움직이는게 최솟값이므로
절반인 13 을 기준으로 횟수 계산해줌 -
왼, 오 횟수 세기 - 오른쪽으로 쭉 가는 경우
A가 아예 없거나 뒤쪽에 있는 경우는 그냥 오른쪽으로 한칸씩 움직이는게 가장 짧음
=>len(name) - 1더해서 return -
왼쪽으로 가는 경우 ==
A가 절반 앞쪽에 있는 경우
path는 오른쪽으로 쭉 가는 경우로 초기화
0 자리에는 어떤 값이 있든 움직일 필요가 없으므로 1 부터 시작
A를 만나면 슬라이싱으로A까지의 값들을 맨 뒤로 보내고 앞의A들을 모두 제거
ex)"JEAAN"=>"AANJE"=>"NJE"
=> 왼쪽은i-1번 움직이고 오른쪽으로len(n)-1번 움직임
=> 둘을 더해서 최솟값만answer에 추가
깔끔하지는 못하다...ㅎ
다른 사람의 풀이
def solution(name):
answer = 0
n = len(name)
def alphabet_to_num(char):
num_char = [i for i in range(14)] + [j for j in range(12, 0, -1)]
return num_char[ord(char) - ord('A')]
for ch in name:
answer += alphabet_to_num(ch)
move = n - 1
for idx in range(n):
next_idx = idx + 1
while (next_idx < n) and (name[next_idx] == 'A'):
next_idx += 1
distance = min(idx, n - next_idx)
move = min(move, idx + n - next_idx + distance)
answer += move
return answer이것도 우선 위, 아래의 경우 처리
=> alphabet_to_num 함수로 A ~ M 는 0 ~ 12, N ~ Z 는 1 ~ 13 의 값을 갖게 함
현재 숫자 바로 다음에 몇개의 A 가 연속되어있는지 개수를 세줌
그러면 idx 와 next_idx 를 기준으로 세 그룹으로 나뉜다
=> 0 ~ idx & A 무리들 & next_idx ~ 끝
distance : 1그룹 (idx) 과 2그룹 (n - next_idx) 중에 더 작은 값을 찾음
=> 왼 -> 오 or 오 -> 왼 처럼 겹치는 부분이 된다
총 움직인 횟수 move 는
중간 A 들을 제외한 1그룹과 2그룹의 이동 횟수 + 겹치는 부분 distance 가 됨
큰 수 만들기
https://programmers.co.kr/learn/courses/30/lessons/42883
내 풀이 1 - 실패
from itertools import combinations
def solution(number, k):
p = max(list(map("".join, combinations(number, len(number)-k))))
return pcombinations 함수로 len(number)-k 길이의 모든 조합을 구한 후, 최댓값 return
참고로 직접 재귀 함수를 만들어서 해도 타임리밋,,
내 풀이 2 - 실패
def solution(number, k):
answer = "0"
k += 1
prev = "0"
for i in range(len(number)):
if prev <= number[i]:
for j in range(len(answer)):
if answer[j] >= number[i]:
break
if j < k:
answer = answer[j:]
k -= j
else:
answer = answer[k:]
k = 0
answer += number[i]
elif prev > number[i]:
k -= 1
if k == 0:
answer += number[i+1:]
break
prev = number[i]
return answer그래서 조합을 모두 찾는 것 말고
이전 값보다 큰 숫자들이 나올 때마다 그 이전의 값들은 없애주는 방식을 생각
answer 에 임의로 0 을 추가, 이 0 도 제거돼야 하므로 k += 1
prev 와 비교해서 큰 숫자를 만나면 answer 에 있는 숫자들 중 작은 값들은 k 개 만큼 삭제
삭제할 개수와 k 를 비교해서 0 이 되는지 범위 체크
했지만 실패!!
너무 끼워맞추듯이 하다보니 지저분해졌다...
다른 사람의 풀이
def solution(number, k):
stack = [number[0]]
for num in number[1:]:
while len(stack) > 0 and stack[-1] < num and k > 0:
k -= 1
stack.pop()
stack.append(num)
if k != 0:
stack = stack[:-k]
return ''.join(stack)stack 을 이용하면 작은 값들을 제거하기 편함
맨 처음 값을 stack 에 넣어주고 그 다음 숫자들부터 보면서 현재 숫자보다 작은 값들 제거
=> stack 의 가장 마지막 값과 현재 숫자를 비교
k 가 0 이 아니면 k 개 만큼 뒤 숫자들 제거
이렇게 간단하게 풀 수 있다니...
구명보트
https://programmers.co.kr/learn/courses/30/lessons/42885
내 풀이 - 통과
def solution(people, limit):
answer = len(people)
people.sort()
idx = 0
for i in range(len(people)-1, -1, -1):
if people[i] == 0:
continue
for j in range(idx, i):
if people[i] + people[j] <= limit:
people[i] += people[j]
people[j] = 0
idx = j+1
else:
break
zero = people.count(0)
return answer - zero구명보트의 최댓값 = 사람 수 이므로 answer 는 len(people) 로 초기화
사람은 몸무게 순으로 정렬해준다
무거운 사람부터 보면서 가벼운 사람 중에 같이 탈 수 있는 사람을 최대한 구함
=> for i in range(len(people)-1, -1, -1): & for j in range(idx, i):
동행자가 있을 경우, 가벼운 사람은 0 으로 바꿔주고 무거운 사람의 무게와 합쳐준다
idx 는 그 다음으로 가벼운 사람을 가리키도록 함
모두 합쳐줬으므로 무게가 있는 사람들의 수를 return
통과되긴 했지만 "한 번에 최대 2명" 이라는 조건을 못 봤다...ㅠ
최대 2 명이라면 2 중 for 문 사용해서 최대한의 인원을 합칠 필요 없이
그냥 하나의 반복문으로 가벼운 사람과 무거운 사람만 보면 될 듯!!
다른 사람의 풀이
def solution(people, limit):
answer = 0
people.sort()
a = 0
b = len(people) - 1
while a < b :
if people[b] + people[a] <= limit :
a += 1
answer += 1
b -= 1
return len(people) - answer몸무게를 기준으로 정렬한 후,
제일 가벼운 사람 + 제일 무거운 사람을 묶어서 확인
동행자를 구한 사람들만 answer 로 세줘서 전체 인원에서 빼주기
투 포인터를 사용해서 더 빠르다!!
