Python으로 푸는 LeetCode 6. ZigZag Conversion

LeetCode 6. ZigZag Conversion이 문제는 입력받은 String을 문제에서 준 지그재그 패턴 조건에 따라 변형하여 출력하는 문제이다. LeetCode 문제 바로 가기LeetCode에서 푼 문제 리스트 바로 가기github에서 코드 보기 문제에서 제시한 조건 "PAYPALISHIRING"는 지그재그 패턴으로 문자를 나열할 경우 다음과 같다. 결과는 "PAHNAPLSIIGYIR"으로 출력된다. P A H N A P L S I I G Y I RRelated TopicsString문제 풀이문제에서는 지그재그 패턴대로 문자를 나열 했을 때, 규칙을 찾으면 쉽게 풀 수 있다. 지그재그의 패턴 원칙대로 각 층별로 lines 배열에 그 값을 저장해나간다.P A H N
온라인 코딩 테스트 문제 풀이/LeetCode 문제 풀이 2019. 2. 12. 23:30

Python으로 푸는 LeetCode 373. Find K Pairs with Smallest Sums

LeetCode 373. Find K Pairs with Smallest Sums 이 문제는 정렬된 두 배열(nums1, nums2)에서 원소를 한개씩 뽑았을 때, 그 합이 작은 순서대로 k개 만큼 두 조합을 반환하는 문제이다. LeetCode 문제 바로 가기LeetCode에서 푼 문제 리스트 보기github에서 코드 보기주의할 사항배열에서 중복된 값이 있다는 사실을 간과한다면 결과 값이 잘못 나올 수 있다. nums1 =[1,1,2] nums2=[1,2,3] k=2 output : (1,1), (1,1) Related TopicHeap 문제 풀이미리 말하지만 내가 푼 코드는 효율이 좋지 못하다. itertools.product를 사용하여 두 배열에서 원소들을 꺼내 만들 수 있는 조합을 만들면서 그 합을..
온라인 코딩 테스트 문제 풀이/LeetCode 문제 풀이 2019. 2. 11. 23:30

Python으로 푸는 LeetCode 33. Search in Rotated Sorted Array

LeetCode 33. Search in Rotated Sorted Array 문제에서는 오름차순으로 정렬된 배열이 어떤 pivot을 기준으로 회전하였을 때, 특정 원소(target)이 몇 번째 Index에 위치했는지 반환하는 코드를 짜려고 한다. 원소가 배열에 포함되지 않았을 경우 -1을 반환하면 된다. 원소는 중복되지 않는다. 단, 알고리즘을 수행했을 때, 런타임 복잡도(runtime complexity)는 O(log n) 내에 수렴해야 한다. LeetCode에 문제 보러 가기 LeetCode에서 푼 문제 리스트 바로 가기 github에서 코드 보기 문제에서 제시한 조건 - 어떤 pivot을 기준으로 회전을 한지 알 수 없다. - 원소가 배열에 포함되지 않았을 경우 -1을 반환한다. - 알고리즘의 시..
온라인 코딩 테스트 문제 풀이/LeetCode 문제 풀이 2019. 2. 10. 23:30

Python으로 푸는 SW Expert Academy 1244. 최대 상금

SW Expert 아카데미 1244. 최대 상금문제에서는 숫자판을 주어진 횟수만큼 교환하여 최대 숫자를 만들도록 코드를 짜야한다.미리 말해두지만 여기에 올린 코드는 남이 이해하기에 좋은 코드가 아니다. (효율도 그닥 안좋은 것 같고..)그럼에도 이 포스팅을 하는 이유는 문제가 계속 fail이 뜨는데 그 이유를 모르는 사람이 있다면 풀이 방법을 참고하면 해결할 수 있기 때문이다.앞서 말하지만, 주어진 케이스가 잘못된게 아니고 그냥 코드를 잘못 짠거다.나중에 알고리즘을 다시 정리해서 좀더 깔끔한 코드로 포스팅을 수정했으면 좋겠다.github에서 코드 보기삼성 SW Expert Academy에서 푼 문제 리스트 보기문제에서 제시한 조건- 주어진 횟수만큼 반드시 모두 교환이 일어나야 한다. - 동일한 위치의 교..
온라인 코딩 테스트 문제 풀이/삼성 SW Expert 문제 풀이 2019. 2. 9. 23:30

Python으로 푸는 SW Expert Academy 4012. 요리사

SW Expert 아카데미 4012. 요리사 문제는 입력 받는 방법의 차이는 있으나,백준의 스타트와 링크 문제와 같은 문제이다.두 명의 손님에게 두 개의 요리를 만들어 제공하려고 한다.두 명의 손님은 식성이 비슷하기 때문에, 최대한 비슷한 맛의 음식을 만들어 내야 한다.식재료의 종류를 둘로 나누지만, 비슷한 맛의 음식을 두 가지 만들어 제공하기로 했을 때각각 음식에 사용할 식재료들의 궁합에 따라 시너지의 합을 구하고그 시너지의 합의 차가 최소가 되는 경우를 찾아그 최솟값을 정답으로 출력하도록 코드를 짜도록 하자.문제 보러 가기백준 스타트와 링크 풀이 보기github에서 코드 보기 문제에서 제시한 조건- 두 명의 손님은 식성이 비슷하여 최대한 비슷한 맛의 음식을 만들어 내야 한다.- N 개의 식재료가 있고..
온라인 코딩 테스트 문제 풀이/삼성 SW Expert 문제 풀이 2019. 2. 8. 23:30

python으로 푸는 백준 14889. 스타트와 링크

백준 14889. 스타트와 링크 문제는 삼성 SW 기출 문제에 포함되어 있다. 축구를 하기 위해 모인 사람들의 능력치를 비교하여두 팀으로 나눴을 때 각각의 팀의 능력치의 차가 최소가 되도록 코드를 짜야 한다.문제 보러 가기github에서 코드 보기 문제에서 제시한 조건- 축구를 하기 위해 모인 사람의 수 n은 매번 짝수다. (그래서 반 씩 나눠서 경기가 가능함)- 나눠진 팀원 끼리 함께 축구를 했을때의 발휘하는 능력치가 서로 다르다. (철수와 영희가 같은 팀이 되었다면, 철수가 영희랑 했을때의 철수의 능력치와 영희가 철수랑 했을때의 능력치가 서로 다르므로 이 두 값을 합쳐줘야 이 팀의 전체 능력치가 나온다.)- 그렇기 때문에 스타트와 링크 팀으로 나눴을 때, 팀원들 간의 능력치의 합한 값이 서로 비등비등..
온라인 코딩 테스트 문제 풀이/백준 문제 풀이 2019. 2. 7. 23:30

Python으로 푸는 백준 2109. 순회강연

백준 2109. 순회강연저명한 학자에게 여러 대학에서 강연 요청이 들어 왔다. 각 대학에서는 몇일 안에 와서 강연을 해주면 얼마의 강연비를 주겠다고 제시했다.학자가 하루에 한 곳에서만 강연을 할 수 있으므로,최대한 유리하게 스케줄을 짜서, 가장 많은 돈을 벌 수 있도록 순회 강연을 하려고 한다.이 학자가 최대 벌 수 있는 강연비는 총 얼마인가?문제 보러 가기github에서 코드 보기 문제에서 제시한 조건- n개의 대학에서 d일 안에 와서 강연을 해주면 p만큼의 강연료를 지불하겠다고 알려준다.- 4개의 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d 값이 차례로 2, 1, 2, 1이라고 하자. 이럴 대에서는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만..
온라인 코딩 테스트 문제 풀이/백준 문제 풀이 2019. 2. 6. 23:30

Python으로 푸는 백준 1758. 알바생 강호

백준 1758. 알바생 강호 문제는 간단한 문제인데도 정답 비율이 40%도 안되는 문제이다.카페를 기다리는 대기줄 순위에 따라서 본래 알바생 강호가 받을 수 있었던 팁이 일정 규칙에 따라 줄어들기 때문에손님이 지불하려고 하는 팁이 주어졌을 때,손님의 순서를 적절히 바꿔 강호가 받을 수 잇는 팁의 최댓값을 구하는 문제이다.문제 보러 가기github에서 코드 보기 문제에서 제시한 조건각 손님은 강호에게 원래 주려고 생각했던 돈 - (받은 등수 - 1) 만큼의 팁을 강호에게 준다.만약, 위의 식으로 나온 값이 음수라면, 강호는 팁을 받을 수 없다.강호는 손님의 순서를 마음대로 바꿀 수 있다. 문제 풀이 방법최대 이익을 얻기 위해서는 팁이 가장 많은 사람이 가장 먼저 입장시키면 된다.따라서 파이썬에 내장된 정렬..
온라인 코딩 테스트 문제 풀이/백준 문제 풀이 2019. 2. 5. 23:30

Python으로 푸는 백준 1946. 신입사원

백준 1946. 신입사원 문제는 특정 기준에 충족되는 신입 사원만을 선발하고자 하며그 기준에 따라 총 몇 명의 신입사원을 채용하게 되는지 알아보려고 한다. 문제 보러 가기github에서 코드 보기 문제에서 제시한 조건- 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접 시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다.- 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.- 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다. 문제 풀이 방법한 지원자의 성적을 다른 모든 지원자의 성적과 비교할 경우, 반복문을 자주 사용하게 되고 그러면 시간 초과가 날 확률이 높다. 이 문제는 단 한번..
온라인 코딩 테스트 문제 풀이/백준 문제 풀이 2019. 2. 4. 23:30

Python으로 푸는 SW Expert Academy 5202. 화물 도크

SW Expert 아카데미 5202. 화물도크 문제에서는 일정 시간동안 최대한 많은 화물차가 화물을 싣고 내릴 수 있도록 하면,최대 몇대의 화물차가 이용할 수 있는지 알아내야 한다.문제 보러 가기github에서 코드 보기문제에서 제시한 조건 1. 작업은 24시간 진행된다.2. 작업 시작 시간은 매시 정각을 기준으로 하며, 앞 작업의 종료와 동시에 다음 작업을 시작할 수 있다.문제 풀기 전 결정 사항- 최대한 많은 화물차가 싣고 내릴 수 있도록 하려면 최단 시간에 업무를 종료하는 화물차를 우선으로 내보내야 한다. - 모든 테스트 케이스를 입력받아 처리하지 않고 yield 키워드로 generator를 사용하여 각각의 케이스별로 input 데이터를 처리하여 결과 값을 출력한다. 문제 풀이 방법이 문제는 그리디..
온라인 코딩 테스트 문제 풀이/삼성 SW Expert 문제 풀이 2019. 2. 3. 23:30

Python으로 푸는 SW Expert Academy 5201. 컨테이너 운반

SW Expert 아카데미 5201. 컨테이너 운반 문제에서는 A에서 B 도시로 N개의 트럭이 무게가 서로 다른 콘테이너를 운반하는데 최적의 방법을 찾아야 한다.최적의 방법에 따라 옮겨진 화물의 전체 무게가 얼마인지 출력해보자.문제 보러 가기github에서 코드 보기 문제에서 제시한 조건1. 컨테이너의 무게가 정해져 있고, 트럭마다 적재 가능한 용량이 주어진다.2. A도시에서 B도시로 최대 M대의 트럭이 편도로 한번만 운행한다.3. 화물을 싣지 못한 트럭이 있을 수도 있고, 남는 화물이 있을 수도 있다.4. 트럭은 하나의 컨테이너만 실을 수 있다. 문제 풀기 전 결정 사항이 문제는 그리디 알고리즘에 해당하는 문제이다.많은 양을 적재할 수 있는 트럭이 가장 무거운 콘테이너를 들고 간다. 문제 풀이 방법 수..
온라인 코딩 테스트 문제 풀이/삼성 SW Expert 문제 풀이 2019. 2. 2. 23:30

Python으로 푸는 백준 1931. 회의실배정

백준 1931. 회의실배정 문제는 삼성 SW Expert에 5202. 화물 도크 문제와 유사하지만좀더 까다로운 문제라고 할 수 있다.시작하자마자 종료되는 회의가 존재하기 때문이다.회의실 사용표를 보고 최대 사용할 수 있는 회의수를 출력해야 한다.이 문제를 해결하려면 어떻게 해야 할까.문제 보러 가기github에서 코드 보기 문제에서 제시한 조건- 회의는 한번 시작하면 종료할 수 없다.- 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.- 회의의 시작 시간과 끝나는 시간이 같을 수도 있다. (시작하자 마자 끝나는 회의로 보면 된다.)문제 풀기 전 결정 사항- 내부적으로 파이썬에 내장되어 있는 sort 함수의 시간 복잡도는 평균적으로 nLogn이므로 별도의 정렬 메소드를 다시 짤 필요는 없다.(보..
온라인 코딩 테스트 문제 풀이/백준 문제 풀이 2019. 2. 1. 23:30