프로그래머스[Python] - 구명 보트, 영어 끝말잇기, 2개 이하로 다른 비트

구명보트

문제 url : https://programmers.co.kr/learn/courses/30/lessons/42885

코딩테스트 연습 - 구명보트

문제 내용 : 사람들의 무게가 주어지고 최대 2명이 탈 수 있는 구명 보트가 있을때, 가장 최소의 수로 구명보트를 태우려면 몇개가 필요한가?

알고리즘 : Greedy (탐욕 알고리즘), 투포인터

풀이과정 : 결론, 괜히 어렵게 생각해서 삽질했다..ㅋㅋ 처음에 당연히 배낭 문제처럼 heap 자료구조를 사용해서 무게를 하나씩 꺼낼때 마다(작은 무게가 나올 것) 가장 큰 무게부터 비교하면서 limit 에 안넘어 가면 짝꿍을 맞춰서 없애려고 했다. 하지만, sort를 매번 해야한다는 점 + 모든 구간을 탐색하는 점 이런 부분에서 정확성은 맞을지라도 효율성에서 문제가 있었다.

그래서 문제를 다시 읽어보니, 최대 2개라는 것이 강조되어 있다. 이게 힌트였다. 투 포인터를 이용해서 정렬된 무게에서 가장 작은 무게와 큰 무게를 비교해서 limit 에 안넘는다면 같이 없애고 넘어간다면 가장 큰 무게 하나만 없애면 되었다..

영어 끝말잇기

문제 url : https://programmers.co.kr/learn/courses/30/lessons/12981

코딩테스트 연습 - 영어 끝말잇기

문제 내용 : 말그대로 끝말잇기를 한다. 게임에서 지는 2가지 경우만 잘 따줘주면 된다. 첫번째는 끝말잇기 정의에 맞게 말이 이어져야하고, 동일한 말이 또 나오면 안된다.

또한 가장먼저 탈락하는 사람의 번호, 몇 번째에 탈락하는지를 구한다.

이는 N명의 사람의 나눗셈의 몫과 나머지 연산을 잘 활용하면 된다.

알고리즘 : 단순 구현, Queue, Stack, 연산

2개 이하로 다른 비트

문제 url : https://programmers.co.kr/learn/courses/30/lessons/77885

코딩테스트 연습 - 2개 이하로 다른 비트

문제 내용 : 하나의 수가 주어질때, 그 수 X보다 큰 수중, 비트가 1~2개 다를 수 있는 수 중에서 가장 작은 수를 구하라

알고리즘 : 단순 구현, 비트 연산

풀이과정 : 나는 처음에 짝수 홀수 이런것을 생각하지 않았다. 그래서 number부터 시작해서 하나씩 큰 수들과 비교하면서 자리에 맞게 서로 비트를 맞춰주고 비교해서 출력하려고 했으나, 10번과 11번 테스트 케이스에서 문제가 생겼다.

그래서 참고를 해서 풀었다. 짝수일 때는 1개만 크면 당연히 조건에 만족하니 이를 추가한다. 이는 기존에 알고 있었다. 홀수일때 어떻게 처리할까였는데, 홀수에는 규칙이 있다. 3→5, 7→11이 되는과정만 봐도 규칙성이 나온다.

0의 자리수를 이용하는 것이다. 비트 연산 문제를 풀때 홀수나 짝수같은 것을 생각해봐야겠다.