1)Level1-체육복
알고리즘:
[1] 예외 처리 하나를 실수 해서 고생한 문제.
이 예외들 속에서도, sort가 되는줄 알았다. 하지만, reserve가 무조건 왼쪽에 줘도 되 라는 가정을 위해서는 sort를 무조건 해줘야 풀 수 있는 문제.
[2] check라는 배열을 사람 수 만큼 만들어주고, 모두 1을 집어 넣는다.
[3] lost배열에 해당하는 번째 사람은 0을 넣어준다.
[4] reserve를 sort하고, 하나씩 꺼내면서 lost안에 이게 있는지 확인 한다.
[5] 있다면 자기 자신을 1로 만들어주고, 없다면 나-1확인 또 없으면 나 +1을 확인해주면 된다.
주의: 나-1이 만약 0이 아니라 이미 있다면 구지 줄 필요 없으니까 +1에게 전달해주면 된다.
2)Level2-조이스틱
알고리즘:
[1] updown과 우왼 두가지 경우에서 각각 그리디 선택이 필요하다.
[2] 먼저 updown은 아스키 코드의 차이로 쉽게 구할 수 있다.
[3] 문제는 위왼에서의 선택이다. 가장 중요한 포인트는 효율적인 이동을 위해서는 오른쪽으로 쭉 가거나 왼쪽으로 쭉 가거나 이다. 우리가 원하는건 복수가 가장 많은곳, 가장 비 효율적인 구간을 어떤 방향에서 접근 할 것인가 이다.
[4] 복수 구간을 먼저 찾는다.
[5] BBAAAABA 예를들어 이런 배열이 있을 경우, 2번 인덱스부터 4번 A가 반복된다.
이때 갈 수 있는 방향은 두가지 이다. 먼저 오른쪽으로 쭉 가는걸 가장 minimum이라고 할때 이것보다 효율적인가를 판단하면 된다. 비교 대상은 BBAB이다. 계산은 A가 시작 할때까지 갔다가 다시 맨처음으로 돌아가는것 + 맨 끝에서 부터 A의 마지막 이다.
즉, i*2 + len(name) - next
이렇게 구한 최소 컨트롤 시간을 더해주면 문제 완성이다.
3)Level2-큰수 구하기
알고리즘:
[1] stack에 넣어주면서 만약 나보다 큰수가 오면 그전에 있는 수들을 삭제 해준다.
[2] 그리고 큰수를 넣어준다. 이런 방식으로 하면 큰수 부터 정렬이 된다.
[3] 만약 나보다 작은수가 온다면 우선 뒤에 그냥 넣어 주면 된다.
[4] k를 다쓰면 끝내주면 된다. 만약 아직 덜 썼다면 그냥 맨 뒤부터 남은 k개 지워주면 된다.
4)Level2-구명보트
알고리즘:
한 번에 최대 2명씩 밖에 탈 수 없고*** 라는 제한이 있다. 문제 잘읽기!!
[1] people을 내림차순으로 정렬한다.
[2]첫번째 수(가장 큰 수)와 마지막 수(가장 작은 수)를 더한 값을 구한다.
2-1. limit을 넘는다면 (첫번째 수만 배에 태우기 때문에) 다음 수로 향하도록 l++ 한다.
2-2. limit을 넘지 않으면 (첫번째 수와 마지막 수를 배에 태우기 때문에) 양 끝에서 다음 수로 향하도록 l++, r-- 한다.
[3]혼자 탄 배 추가를 위해 answer++
[4]함께 탄 배 추가를 위해 answer++
[5]만약 people[l] == people[r] 즉, 계산되지 않은 마지막 숫자가 남았다면, 이 숫자 혼자 타는 배를 추가하기 위해 answer++ 한다.
5)Level3-섬연결하기
https://soohyun6879.tistory.com/145
알고리즘:
내가 처음 푼 방식은 다익스트라 알고리즘이였는데, 잘 동작하지 않았다.
그래서 위에 블로그를 참조해서 좋은 코드의 알고리즘을 소개하려고 한다.
크루스칼 알고리즘을 이용하면 minimum spanning tree를 만들 수 있다.
[1] 먼저 그래프의 간선을 오름 차순으로 정렬한다.
[2] 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
[3] 이미 정렬하여 minimum을 보장하기 때문에, 나와 연결된애만 신경 쓰면된다.
6)Level3-단속카메라
알고리즘:
[1] 정렬을 합니다. 기준점은 차량이 진입하는 순간입니다.
[2] 처음 차가 나가는 거리를 임시변수에 넣어줍니다.
[3] 다음차가 현재차가 나간후에 들어온다면 카메라를 추가해야합니다. 그리고 car_out 범위 조정
[4] 현재 차보다 뒤차가 먼저나가면, 즉 뒤차가 범위 안에 있으면 car_out범위 조정