CodeDrive

문제:

정수 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

문제:

서울에서 경산까지 여행을 하면서 모금 활동을 하려 합니다. 여행은 서울에서 출발해 다른 도시를 정해진 순서대로 딱 한 번 방문한 후 경산으로 도착할 예정입니다. 도시를 이동할 때에는 도보 혹은 자전거를 이용합니다. 이때 도보 이동에 걸리는 시간, 도보 이동 시 얻을 모금액, 자전거 이동에 걸리는 시간, 자전거 이동 시 얻을 모금액이 정해져 있습니다. K시간 이내로 여행할 때 모을 수 있는 최대 모금액을 알아보려 합니다

예를 들어 여행 루트가 다음과 같고 K=1,650 일 때,

1, 2번 구간은 도보로, 3번 구간은 자전거로 이동해 모금액을 660으로 하는 것이 가장 좋은 방법입니다. 이때, 1,600시간이 소요됩니다.

solution 함수의 매개변수로 각 도시를 이동할 때 이동 수단별로 걸리는 시간과 모금액을 담은 2차원 배열 travel과 제한시간 K가 주어집니다. 제한시간 안에 서울에서 경산까지 여행을 하며 모을 수 있는 최대 모금액을 return 하도록 solution 함수를 작성하세요.

풀이방법:

동적계획법을 사용해서 풀어야 하는 문제이다. 0번째 인덱스에는 도보로 걸리는 시간, 2번째 인덱스에는 자전거 이동시 걸리는 시간이 담겨 있으며. 1번째, 3번째 인덱스에는 각각 금액이 담겨져 있다. 따라서 0,2번째로 K시간이 넘어가지 않는 선에서 1,3을 더 했을 때 최대가 되는 값을 찾으면 된다.

문제링크:

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

문제:

직사각형 종이를 n번 접으려고 합니다. 이때, 항상 오른쪽 절반을 왼쪽으로 접어 나갑니다. 다음은 n=2인 경우의 예시입니다.

먼저 오른쪽 절반을 왼쪽으로 접습니다.

다시 오른쪽 절반을 왼쪽으로 접습니다.

종이를 모두 접은 후에는 종이를 전부 펼칩니다. 종이를 펼칠 때는 종이를 접은 방법의 역순으로 펼쳐서 처음 놓여있던 때와 같은 상태가 되도록 합니다. 위와 같이 두 번 접은 후 종이를 펼치면 종이에 접은 흔적이 생기게 됩니다.

V 모양이 생긴 부분은 점선(0)으로, ㅅ 모양이 생긴 부분은 실선(1)으로 표시했습니다.

종이를 접은 횟수 n이 매개변수로 주어질 때, 종이를 절반씩 n번 접은 후 모두 펼쳤을 때 생기는 접한 부분의 모양을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

풀이방법:

이 문제는 종이접기 수열을 사용하는 문제이다. 종이접기 수열이란 이 문제처럼 종이를 일정한 방향으로 접었을 때 생기는 굴곡에 대한 수열이다. 

이 문제처럼 오른쪽에서 왼쪽으로 접는 경우에는 가운데가 0으로 고정되어서 수열이 생성된다.

1 ->  0

2 ->  0 + 0 + 1

3 ->  0 + 0 +1 + 0 +0 + 1+ 1

4 -> 001+0+011 + 0 + 001+1+011

5 -> 0010011+ 0 + 0011011 + 0 +0010011 + 1 + 0011011

....

1, 2, 3에서는 규칙을 찾기 어렵지만 4부터는 규칙을 찾을 수 있다.

가운데 0을 기준으로 이전 단계의 모양이 반복되는 것을 알 수 있다. 가운데 0을 기준으로 했을 때 왼쪽은 이전단계의 중간이 0인 경우 오른쪽은 이전단계의 중간이 1인 경우이다. 따라서 1, 2의 경우에는 예외처리로 두어서 답을 반환하도록 하고, 3부터는 반복문을 통해서 규칙을 생성하도록 하였다.

문제링크:

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

문제:

 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기 입니다. 이 종이를 격자 선을 따라 1cm x 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm x 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.

 가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

풀이방법:

직사각형에서 대각선으로 잘랐을 때 제거되는 부분은 다음과 같이 동일하게 삭제됨을 알 수 있다. 이들의 개수는 gcd를 통해서 구할 수 있으며 제거되는 칸 수도 w//gcd+h//gcd -1로 구할 수 있다. 

따라서 gcd를 구한 뒤 전체에서 해당하는 만큼 제거하면 답을 구할 수 있다.

문제링크:

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

문제:

풀이방법:

 내가 말해야 하는 단어까지만 알면 되므로 0부터 n진수로 변환을 하면서 digits에 더하고 digits의 길이가 t*m보다 커지면 그만 변환하도록 하면 된다.

 digits를 다 구했다면 내가 말해야 하는 위치의 인덱스 값을 answer에 더해서 반환하도록 한다.

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

문제:

풀이방법:

우선 파일명을 HEAD, NUMBER, TAIL로 정리를 해야한다. 이를 위해서 isdigit이라는 숫자인지 확인하는 함수를 사용한다.

 처음 isdigit이 참이 되는 순간 이전까지의 글자가 HEAD가 되므로 isdigit이 참이 되는 순간 parser에 값을 추가하고 break를 걸어서 반복문을 나온다. 

 해당 위치부터 다시 반복문을 사용해서 이번에는 isdigit이 거짓이 되는 순간이 NUMBER의 끝이므로 parser에 값을 추가하고 break를 걸어서 반복문을 나온다.

 이제 남은 부분은 TAIL에 해당하므로 parser에 추가해주면 되지만 TAIL이 아무것도 없을 경우에는 위 NUMBER를 파악하는 과정에서 맨 마지막 숫자가 추가되지 못했을 것이다. 따라서 해당 인덱스에 isdigit을 사용해서 참이면 TAIL이 없는 경우, 거짓이면 TAIL이 있는 경우를 의미한다.

 이제 파일명을 HEAD, NUMBER, TAIL로 나눴으므로 sort의 key를 사용해서 정렬을 하도록 한다. 우선 HEAD를 기준으로 사전 순 정렬을 하고, 대소문자 구별을 하지 않는다. 그리고 HEAD가 동일하다면 NUMBER가 작은순으로 정렬을 하는데 스트링 상태가 아닌 int 상태로 변환해서 정렬을 해야 한다. 따라서 sort의 key는 (x[0].upper(), int(x[1])) 이 된다. 이처럼 해야지 원래 파일명을 보존하면서 정렬을 할 수 있다.

 정렬을 완료했으므로 이를 다시 붙여서 출력을 해야 한다. TAIL이 있는 경우에는 parser에 2번째 인덱스가 존재하지만 없다면 1까지만 존재한다. 따라서 이를 try~ except ~ 예외처리 구문을 사용해서 추가하도록 한다.

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

문제:

풀이방법:

LZW 압축 과정대로 코드를 작성하면 된다.

 우선 길이가 1인 모든 단어를 포함해서 사전을 구축해야 하므로 dictionary에 밑과 같이 구축한다. 그 뒤에 idx가 입력으로 들어온 문자열의 길이와 같아질 때까지 반복해서 확인하고 추가하는 작업을 한다.

 LZW 압축과정은 다음과 같이 작동된다.

1. KAKAO의 경우에 KAKAO와 인덱스 0 그리고 사전이 check로 입력된다.

2. 이를 뒤에서부터 비교를 한다. 즉 KAKAO가 사전에 있는가? -> KAKA가 사전에 있는가? -> .... 순으로 진행이 되고 K가 사전에 있는가에서 참이므로 break를 걸고 반복문 밖으로 나온다.

3. 그러면 KA는 사전에 없는 단어였으므로 사전에 추가하고 인덱스와 사전을 반환한다.

4. check에서 나온 인덱스와 check에 넣기 전에 사용한 인덱스를 사용해서 슬라이싱을 하고 이를 사전의 색인 번호를 answer에 추가한다.

5. idx를 i로 지정한다.

 idx가 msg와 동일할 떄까지 진행을 하면 압축과정이 끝나게 된다.

문제링크:

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

문제:

풀이방법:

 이 문제에서 처리해야 할 것은 크게 두 가지이다. 재생된 시간의 길이에 따라서 음이 달라지므로 시간 형식으로 되어 있는 자료형을 분 단위로 바꿔야 한다. 그리고 음계 중에 C#, D#, F#, G#과 같이 #이 붙어 있는 음계가 있는데 스트링 형식으로 되어 있기 때문에 이들도 하나의 인덱스를 차지하고 있으므로 처리하는 방법에 대해서 생각해야 한다.

 우선 분으로 바꾸기 위해서 :를 기준으로 분할을 한다. 시작하는 분과 끝나는 분을 비교해서 음악의 총 재생된 시간을 구하도록 한다.

 C#과 같이 #이 달려있는 음들은 하나의 인덱스로 처리를 하는 것이 편하므로 소문자로 변경하도록 한다. (C#->c , D# ->d , ....) 이 작업을 하고 위에서 구한 재생된 시간으로 실제 재생된 멜로디를 구할 수 있고, 이 안에 m이 있는지 판단하여서 answers 리스트에 담도록 한다. 

 이 때 조건이 일치하는 음악이 여러 개일 경우에는 재생된 시간이 제일 긴 음악, 먼저 입력된 음악 제목 순으로 정렬해야 하므로 (재생된 시간, 입력된 인덱스,음악제목)과 같이 answers에 넣도록 한다.

 일치하는 음악을 모두 담았다면 sort의 key를 이용해서 위 조건에 맞게 정렬을 하도록 한다. 재생된 시간은 길수록 앞으로 와야 하므로 음수를 붙여주고, 먼저 입력된 것이 앞으로 와야 하므로 이는 양수로 정렬하도록 한다. 이렇게 정렬을 하고 난 뒤에 answers에 가장 앞에 있는 값의 맨 마지막 값을 출력한다면 그것이 음악제목일 것이다. (만약 answers가 비어 있다면 "(None)"을 출력해야 한다.

문제링크:

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