CodeDrive

문제:

풀이방법:

규칙 중 4를 구현하는 것이 핵심인 문제다.

 solution함수는 1,4,7 입력이 들어온다면 왼쪽 엄지손가락을 사용하고, 해당 번호로 left를 이동시키고, 3,6,9가 들어온다면 오른쪽 엄지손가락을 사용하고 right를 이동시킨다. 이제 2,5,8,0이 들어오는 경우 leftDistance와 rightDistance를 사용해서 거리를 계산한다. 더 작은 쪽의 엄지손가락으로 이동을 하고, 만약 같다면 hand의 우선순위에 따라 움직이도록 한다.

 leftDistance는 입력을 해야하는 숫자가 2,5,8,0일 때, 왼쪽 엄지손가락과 거리를 계산하는 함수다.

만약 이전 왼쪽 엄지 손가락이 2,5,8이고 입력해야 할 숫자가 0이라면 각 케이스마다 거리를 return 하게 만들고, 나머지는 두 수의 차를 3으로 나눈 몫을 반환하도록 한다. 왼쪽 엄지 손가락이 1,4,7에 있다면 이를 가운데 키패드로 옮겨주고 leftDistance로 재귀적으로 거리를 계산하도록 만든다. 이제 나머지 케이스인 0에 있거나, 초기 상태인 *에 있던 경우에 대해서만 거리를 계산해주면 된다.

 rightDistance로 leftDistance와 비슷하게 계산을 하도록 한다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/67256

문제:

어떤 파일 시스템에는 디스크 공간이 파일의 사이즈와 항상 같지는 않다. 이것은 디스크가 일정한 크기의 클러스터로 나누어져 있고, 한 클러스터는 한 파일만 이용할 수 있기 때문이다.

예를 들어, 클러스터의 크기가 512바이트이고, 600바이트 파일을 저장하려고 한다면, 두 개의 클러스터에 저장하게 된다. 두 클러스터는 다른 파일과 공유할 수 없기 때문에, 디스크 사용 공간은 1024바이트가 된다.

파일의 사이즈와 클러스터의 크기가 주어질 때, 사용한 디스크 공간을 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 파일의 개수 N이 주어진다. N은 1,000보다 작거나 같은 자연수이다. 둘째 줄에는 파일의 크기가 공백을 사이에 두고 하나씩 주어진다. 파일의 크기는 1,000,000,000보다 작거나 같은 음이 아닌 정수이다. 마지막 줄에는 클러스터의 크기가 주어진다. 이 값은 1,048,576보다 작거나 같은 자연수이다.

출력:

첫째 줄에 사용한 디스크 공간을 출력한다.

풀이방법:

파일을 클러스터에 넣으려고 할 떄 크게 3가지 경우가 발생한다.

1. 한 파일의 크기가 한 클러스터의 크기보다 큰 경우

2. 한 파일의 크기가 한 클러스터의 크기와 같은 경우

3. 한 파일의 크기가 한 클러스터의 크기보다 작은 경우

그리고 위 3가지 case는 몫과 나머지를 통해서 구할 수 있다.

파일사이즈를 클러스터의 크기로 나눴을 때, 몫이 1보다 커지게 된다면 1의 케이스에 해당하며 몫만큼 클러스터의 개수를 준비하고 나머지가 있을 경우 하나 더 준비하면 된다.

그리고 몫이 0이라면 나머지가 있을 경우에는 한 개를 준비하면 되고, 나머지가 없다면 준비안하면 된다.

몫과 나머지를 구할 수 있는 divmod를 사용해서 알고리즘을 구현하면 된다.

문제링크:

https://www.acmicpc.net/problem/1350

문제:

풀이방법:

 문자열을 처리하고 규칙에 따라 정리를 하면 되는 문제이다.

우선 양 끝은 {{~~}}으로 고정이 되어 있다. 따라서 슬라이싱을 통해서 이 부분을 떼어내고 숫자들을 구분하기 위해서    '}.{'로 split을 한다. 이렇게 하면 ['2', '2,1' , '2,1,3' , '2,1,3,4'] 와 같이 분리되게 된다.

 반복문으로 순환을 하면서 다시 ','을 기준으로 분리를 하면 숫자만 남게 되는데 이를 각 원소값이 int인 list로 tuples에 정리하게 된다. 이 단계까지 마치면 문자열을 규칙에 적용할 수 있도록 정리가 마무리 되었다.

규칙은 다음과 같다.

1. 각 list들을 길이가 짧은 순으로 정렬을 한다.

2. list의 숫자 값을 탐색하며 answer list에 없는 값이라면 answer에 넣고 break를 한 뒤 다음 list를 탐색한다.

따라서 이 규칙을 끝까지 적용하면 answer를 얻을 수 있다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/64065

문제:

풀이방법:

문제에서 주어진대로 구현을 해도 되지만 stack을 활용해서 풀었다. 각 열별로 newboard에 stack으로 정리를 하며, move를 이용해서 각 열에 있는 값들을 pop을 해서 빼온다. move에 해당하는 열에 값이 없다면 continue로 행동을 넘기며 값이 있다면 basket에 값을 넣는다.

 basket에 값을 넣었다면 위의 두 값이 같은지 확인하고 같다면 pop을 사용해서 빼고 answer 카운트를 2 증가시킨다. (두 값이 같아 없어지는 행위를 세는 것이 아니라 없어진 것의 개수를 구하는 것이므로 2를 더하는게 맞다.)

이 행위를 moves에 있는 행동대로 다 하고 난 뒤의 answer를 반환한다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/64061

문제:

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.

1234567891011121314151617181920212223...

이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N(1<=N<=100,000,000)이 주어진다.

출력:

첫째 줄에 새로운 수의 자릿수를 출력한다.

풀이방법:

처음에는 브루트 포스로 알고리즘 분류가 되어 있어서 그냥 N까지의 수를 다 붙인 다음에 길이를 구하는 방식으로 했는데 시간초과가 발생했다.

그래서 처음 받은 N을 기준으로 자릿수를 줄여나가면서 더하는 방식으로 바꾸어서 해결을 했다.

ex) 3자리수의 갯수*3 + 2자리수의 갯수*2 ....

문제링크:

https://www.acmicpc.net/problem/1748

문제:

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1<=N<=500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1<=M<=500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있따. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력:

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

풀이방법:

 많은 수를 비교해야 하므로 일반 탐색을 사용하면 시간 초과가 발생할 것 같았다. 그래서 로그 단위로 탐색이 가능한 이진탐색을 사용하고자 하였다. 그리고 이진탐색이 가능했던 이유가 같은 수가 적혀있는 경우가 없기도 했다.

 python에 이진탐색을 제공하는 bisect모듈을 사용하였다. bisect.bisect를 사용하면 배열에 값이 있는 위치를 반환하며 이 인덱스는 0부터 시작하는 것이 아닌 1부터 시작한다.(왜 그런진 모르겠다.) 또한 없는 값에 대해서는 그 근처의 값의 인덱스를 반환하기 때문에 bisect로 찾은 값과 내가 찾고자 하는 값이 참일 경우에만 answers의 값을 1로 바꾸도록 하였다.

문제링크:

https://www.acmicpc.net/problem/10815

문제:

정수 N이 주어져 있을 때 이 수가 10보다 크면 일의 자리에서 반올림을 하고, 이 결과가 100보다 크면 다시 10의 자리에서 반올림을 하고, 또 이 수가 1000보다 크면 100의 자리에서 반올림을 하고..(이하 생략) 이러한 연산을 한 결과를 출력하시오.

입력:

첫째 줄에 정수 N이 주어진다. (0<=N<=99,999,999)

출력:

첫째 줄에 위와 같은 연산을 한 결과를 출력하시오.

풀이방법:

뒷자리에서 부터 하나씩 반올림을 하면서 진행하면 된다. 반올림을 하려고 하는 자릿수가 5이면 앞자리에 1을 더해주고, 그렇지 않다면 그 자리를 0으로 바꾼 뒤 그대로 이어붙이면 된다. 그런데 반올림을 하는 자리의 수가 5이상이고 1을 받는 자리가 9이면 문제가 발생한다. 이 경우에는 9가 1을 받아서 10이 되기 때문에 그 앞자리까지에도 영향을 받게 된다. 

이를 int 연산으로 바꾸어서 진행을 했다면 문제가 없겠지만 str의 슬라이싱을 사용해서 문제를 풀고 있기 때문에 이 경우를 따로 예외 케이스로 만들어서 해결해 주도록 한다.

문제링크:

https://www.acmicpc.net/problem/2033

문제:

당신은 FCFS(First-Come, First-Served)의 규칙에 따라 요청된 일을 처리하는 서버를 담당하게 되었다. 매일, 당신은 일을 처리하기 위해 최대 T분 동안 서버에 시간을 할당할 수 있다. 당신은 오늘 주어진 시간동안 몇개의 일이 완료될 수 있는지 알고 싶다.

예시를 들어보겠다. T=180이고, 요청된 일들의 수행시간이 요청된 순으로 45,30,55,20,80,20 분이다. 그러면, 단 4개의 일만이 완료될 수 있다. 처음 4개의 일의 수행시간은 150분으로 주어진 시간 내에 완료될 수 있지만, 처음 5개의 일의 수행시간은 230분으로 주어진 시간 180분보다 크기 때문에 완료될 수 없다. 처음 4개의 일을 수행한 뒤 6번째의 일을 수행해도 T를 초과하지 않지만 5번째 일을 수행할 수 없기 때문에 6번째 일을 수행할 수 없음을 참고해라.

입력:

첫 줄을 두 정수 n과 T이며 (1<=n<=50, 1<=T<=500) n은 일의 개수를 나타낸다. 두 번째 줄은 n개의 100이하의 자연수가 입력되며, 입력된 각 일의 수행 시간을 나타낸다.

출력:

일이 First-come, First-serverd 규칙에 따라 처리될 때, T분 안에 완료될 수 있는 일들의 개수를 출력하라.

풀이방법:

앞에서 부터 더하면서 T를 넘는지 확인하면 된다. T를 넘는다면 break를 걸고 나와서 그 때까지의 값을 출력하면 된다. idx<n이라는 조건이 있는데 이 것은 주어진 일을 모두 T 시간 내에 해결할 수 있을 때 발생하는 에러에 대한 조건이다. while문을 사용했기 때문에 T가 아직 남아 있다면 계속해서 반복하게 될 것이고 런타임에러가 발생한다. 따라서 모든 값을 탐색했다면 종료해야 하기 때문에 이 조건을 넣었다.

문제링크:

https://www.acmicpc.net/problem/10409

문제:

준민이는 탄산 음료를 좋아한다. 탄산 음료를 사느라 돈을 다 써버렸기 때문에, 이제 준민이는 가진 돈이 없어 탄산 음룔를 사먹을 수 없다.

준민이는 항상 법을 지키며 사는 사람이기 때문에, 아무리 탄산 음료가 먹고 싶어도 훔치지 않는다. 따라서, 법적으로 문제가 없는 방법으로 탄산 음료를 구매할 것이다.

마침 빈 병을 특정 개수만큼 가져가면, 새 병으로 바꾸어주는 이벤트가 진행중이다. 준민이는 길에서 빈 병을 열심히 찾은 뒤, 탄산 음료를 먹으려고 한다.

준민이가 현재 가지고 있는 빈 병의 수와 길에서 발견한 빈 병의 수, 새 병으로 바꾸는데 필요한 빈 병의 수가 주어졌을 때, 준민이가 탄산 음료를 몇 개 먹을 수 있는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 준민이가 가지고 있는 빈 병의 수 e, 그날 발견한 빈 병의 수 f, 새 병으로 바꾸는데 필요한 빈 병의 개수 c가 주어진다. (e<1000, f<1000,1<c<2000)e,f,c는 모두 음이 아닌 정수이다.

출력:

첫째 줄에 준민이가 탄산 음료를 몇 개나 먹을 수 있는지를 출력한다.

풀이방법:

가지고 있는 빈 병이랑 발견한 빈 병의 수도 중요하지만 이를 통해서 구매한 병의 수도 중요하다. 이 문제의 경우처럼 9개의 빈병으로 3개를 바꿀 수가 있다. 그리고 이 3병을 다 마시면 다시 1병을 바꿀 수 있기 때문에 총 4병이 되는 것이다. 그래서 이와 같은 방법으로 몇번을 더 바꾸어 먹을 수 있는지 모르기 때문에 while을 사용하였다.

병의 수를 c로 나누었을 때 몫을 계속해서 더하며 남은 병과 몫을 다시 더해서 빈 병으로 만든다. 

이 과정을 계속해서 반복하면서 몫이 0이 되는 경우에 빠져 나오도록 하였다.

문제링크:

https://www.acmicpc.net/problem/5032

문제:

Day of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다.

끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의  가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주어진다. 가격은 0보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력:

첫째 줄에 기타줄을 적어도 N개 사기 위해 필요한 돈의 최솟값을 출력한다.

풀이방법:

여러 개의 기타줄에서 패키지 가격이 가장 작은 값과, 낱개 가격이 가장 작은 값만 필요하다. 이 두 개의 가격을 비교했을 때, 만약 낱개로 6개를 사는 것이 패키지 가격보다 싸다면 모든 기타줄을 낱개로 사는 것이 이득이다.

만약 그렇지 않다면 사야하는 기타줄을 6으로 나눴을 때 그 몫만큼은 패키지로 사는 것이 이득이다. 그 뒤로는 남은 나머지를 낱개로 샀을 때와 패키지로 샀을 때(적어도 N개를 구매하면 되므로 초과해서 사도 괜찮다.) 어떤 것이 이득인지 알아보고 그에 맞게 구매를 해야 한다. (ex 패키지 7 낱개 2면 패키지가 더 이득)  

문제링크:

https://www.acmicpc.net/problem/1049