방구석프로의 이야기

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

문제

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

participantcompletionreturn

입출력 예 설명

예제 #1
leo는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
vinko는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
mislav는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한 명은 완주하지 못했습니다.

문제 해결을 위한 과정

이 문제는 제가 생각하기엔 Level 1 문제 치고는 생각할것들이 많았던 문제였습니다. 리스트의 크기가 100,000이었기 때문에 일반적인 반복문으로 코드를 작성하면 시간 초과 판정을 받을 수 있기 때문입니다. 따라서 저의 경우는 두 리스트들을 set으로 집합의 형태로 바꾼후 차집합을 이용하는 방식으로 구하려 했습니다. 그러나 이 경우 예제 3번과 같은 방식에서 에러가 났습니다. 바로 동명이인이 있는 경우 집합을 사용하면 중복을 허용하지 않는 성질로 인해 동명이인이 합쳐지기 때문입니다. 따라서 Zip()을 이용하였습니다. zip()은 파이썬의 내장 함수로 동일한 개수의 자료형들이 있다면 그들을 묶어주는 역할을 합니다. 이렇게 작성을 하면 예제 #1의 경우 다음과 같이 묶입니다. (각 리스트들을 정렬을 해주어야 동일한 사람들끼리 묶이기 때문에 정렬은 필수 입니다.)

(eden, eden), (kiki, kiki)  - 그 뒤는 참가자 명단에는 leo가 있지만 완주자 명단에 없기 때문에 숫자가 맞지 않아서 묶이지 않음 이 경우 정렬된 참가자 명단의 가장 마지막 원소인 leo 출력을 하면 정답입니다.

소스코드

participant.sort();&nbsp;completion.sort()&nbsp;<span

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

문제

문제 설명

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers의 길이는 2 이상 100 이하입니다.
  • numbers의 모든 수는 0 이상 100 이하입니다.

입출력 예

numbersresult

입출력 예 설명

입출력 예 #1

• 2 = 1 + 1입니다. (1이 numbers에 두 개 있습니다.)
• 3 = 2 + 1 입니다.
• 4 = 1 + 3입니다.
• 5 = 1 + 4 = 2 + 3입니다.
• 6 = 2 + 4입니다.
• 7 = 3 + 4입니다.
• 따라서 [2,3,4,5,6,7] 을 return 해야 합니다.

입출력 예 #2

• 2 = 0 + 2입니다.
• 5 = 5 + 0 입니다.
• 7 = 0 + 7 = 5 + 2 입니다.
• 9 = 2 + 7 입니다.
• 12 = 5 + 7 입니다.
• 따라서 [2,5,7,9,12] 를 return 해야 합니다.

문제 해결을 위한 과정

이 문제의 경우 Level 1 문제로 어렵지 않은 문제였습니다. 리스트로 주어진 숫자 중에서 2개의 숫자를 골라서 그 합을 출력을 하는 문제입니다. 입출력 예 #1을 보면 2, 1, 3, 1, 4인데 3 + 4 = 7, 4 + 3 = 7로 순서가 상관이 없으므로 순열이 아닌 조합의 방법을 사용해야 한다는 것을 알 수 있습니다. 따라서 해당 리스트에서 2개의 숫자를 골라서 그 합을 answer리스트에 넣어주면 됩니다.

문제 해결을 위한 팁

조합을 하여 계산을 하면 중복되는 것들이 문제가 됩니다. 입출력 예제 #2를 보면 5, 2를 뽑아서 5 + 2 = 7과 0 , 7을 뽑이서 합한 값인 0 + 7 = 7이 중복이 되는 것을 확인할 수 있습니다. 이 경우는 집합의 정리를 활용하면 쉽게 해결할 수 있습니다. 집합은 중복을 허용하지 않기 때문입니다. 따라서 set()을 이용하면 아주 손쉽게 중복을 제거할 수 있습니다. 그 후 출력방식에 맞게 다시 리스트로 변경을 해주면 됩니다.

소스코드

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

문제 (그림 자료는 위의 프로그래머스 링크를 참조해주세요)

문제 설명

게임개발자인 죠르디는 크레인 인형 뽑기 기계를 모바일 게임으로 만들려고 합니다.
죠르디는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.

게임 화면은 1 x 1 크기의 칸들로 이루어진 N x N 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 5 x 5 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 1 x 1 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다. 다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다.

만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다. 위 상태에서 이어서 [5번] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다.

크레인 작동 시 인형이 집어 지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면 표시 제약으로 5칸만으로 표현하였음)

게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• board 배열은 2차원 배열로 크기는 5 x 5 이상 30 x 30 이하입니다.
• board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
  • 0은 빈칸을 나타냅니다.
  • 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
• moves 배열의 크기는 1 이상 1,000 이하입니다.
• moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

입출력 예

boardmovesresult

입출력 예에 대한 설명

입출력 예 #1

인형의 처음 상태는 문제에 주어진 예시와 같습니다. 크레인이 [1, 5, 3, 5, 1, 2, 1, 4] 번 위치에서 차례대로 인형을 집어서 바구니에 옮겨 담은 후, 상태는 아래 그림과 같으며 바구니에 담는 과정에서 터트려져 사라진 인형은 4개입니다.

문제 해결을 위한 과정

이 문제는 레벨 1 문제답게 크게 어려운 점은 존재하지 않았습니다. 문제에서 제시한 조건들만 잘 따라가면 어렵지 않게 해결할 수 있었고 제가 생각할 땐 구현 종류의 알고리즘이라고 생각됩니다. 먼저 가장 중요한 것은 배열 moves가 예시에서  1, 5, 3, 5, 1, 2, 1, 4로 주어졌는데 이 배역 혹은 리스트가 N * N 크기의 이차원 배열에서의 열을 의미한다는 것입니다. 먼저 표로 정리 헤서 보여드리면 다음과 같습니다.

moves 배열이 시작이 1이기 때문에 이차원 리스트에서 0행 0열, 1행 0열, 2행 0열 순으로 조회하다가 처음 0이 아닌 3행 0열을 발견하면 이 값인 4를 다른 리스트에 추가한 후 이차원 배열에서 해당 원소를 0으로 바꿔주면 됩니다.(인형을 뽑은 경우이기 때문입니다.) 그 다음은 moves는 5 이므로 4열을 조회하는데 이차원 리스트에서 0행 4열, 1행 4열을 조회하던 중 0이 아닌 1행 4열을 조회한 후 이 값인 3을 다른 리스트에 추가한 하면 되는것 입니다. 이렇게 계속 진행하다보면 리스트에 어느순간 4, 3, 1, 1 이 들어가는 경우가 생기는데 이 경우 같은 리스트의 마지막 원소와 그 앞의 원소를 비교하여 같은 인형인 1과 1을 리스트에서 제거를 합니다. 결국 인형 2개가 제거되었다고 생각하면 됩니다.

문제 해결을 위한 팁

위의 과정에서 다른 리스트에 추가를 한다고 하였는데 질문게시판을 보니 많은 분들이 놓쳤던 경우가 있습니다. 바로 다른 리스트에 추가 한 후 제거해나가는 과정인데 이 다른 리스트(answer 리스트라고 하겠습니다.) answer 리스트의 개수가 2 이상인 경우부터 제거를 해야 한다는 것입니다. 그렇지 않다면 없는 리스트를 조회하는 문제 즉 런타임 에러가 발생할 수 있기 때문입니다.

소스코드

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

문제 설명

데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, abcabcdede와 같은 문자열은 전혀 압축되지 않습니다. 어피치는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, ababcdcdababcdcd의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 2ab2cd2ab2cd로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 2ababcdcd로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

다른 예로, abcabcdede와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 abcabc2de가 되지만, 3개 단위로 자른다면 2abcdede가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

제한사항

• s의 길이는 1 이상 1,000 이하입니다.
• s는 알파벳 소문자로만 이루어져 있습니다.

입출력 예

sresult

입출력 예에 대한 설명

입출력 예 #1

문자열을 1개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #2

문자열을 8개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #3

문자열을 3개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #4

문자열을 2개 단위로 자르면 abcabcabcabc6de 가 됩니다.
문자열을 3개 단위로 자르면 4abcdededededede 가 됩니다.
문자열을 4개 단위로 자르면 abcabcabcabc3dede 가 됩니다.
문자열을 6개 단위로 자를 경우 2abcabc2dedede가 되며, 이때의 길이가 14로 가장 짧습니다.

입출력 예 #5

문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.

문제 해결을 위한 과정

이 문제의 경우 문제에서 주어진 조건은 아니지만 문제를 읽다 보면 유추할 수 있는 조건이 있습니다. 바로 문자열을 최대 몇 개의 단위로 잘라 압축할 수 있느냐입니다. 입출력 예 #1을 기준으로 설명을 드리면 aabbaccc의 길이 8을 2로 나는 몫 즉 최대 4개의 단위로 잘라 압축을 할 수 있다는 것입니다. 이유는 5개로 압축을 한다면 aabba / accc 즉 애초에 압축이 불가능하다는 것을 알 수 있습니다. 따라서 최대 단위는 입력받은 문자열 길이의 나누기 2 한 값입니다.

문제 해결을 위한 팁

계속해서 입출력 예 #1을 기준으로 설명을 드리겠습니다. 먼저 표는 다음과 같습니다.

이 표를 기준으로 슬라이싱하는 인덱스들을 기준점으로 잡아서 소스코드를 작성하면 됩니다. 가장 먼저 단위는 1부터 4까지이기 때문에 이중 for문 중 바깥에 있는 for문은 for i in range(1, len(s)//2+1): 로 해주시면 됩니다.

다음 인덱스는 맨 처음 열을 제외하고 보면 슬라이싱의 시작 지점이 단위와 같은 것을 확인할 수 있습니다. ex) 단위 1개의 경우 첫 열을 제외하고 두 번째 열의 슬라이싱 시작 지점이 s[1:2]로 1 임, 단위 2개의 경우 첫 열을 제회하고 시작 지점이 s[2:4]로 2 임 다른 과정 역시 동일.

따라서 두 번째 for문은 for j in range(i, len(s)+1, i):로 작성하면 됩니다. for문에서 마지막 원소는 한 번에 i 만큼씩 뛰어넘겠다 라는 의미로 생각하면 됩니다. 이게 없는 경우 default로 1 만큼 뛰어넘는 일반적인 for문이 되는 것입니다.

마지막으로 두 번째 for문에서 왜 len(s)+1을 조건으로 하는지 궁금해하시는 분이 많을 텐데 이렇게 하면 마지막에 조회하는 s가 "" 즉 빈칸이 됩니다. 빈칸의 경우 무조건 이전 단계에서 슬라이싱으로 조회한 것과 다를 수밖에 없기 때문에 따로 마지막 원소에 대해 예외처리를 해줄 필요가 없다는 것이 장점입니다.

소스코드

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

문제

문제 해결을 위한 과정

이 문제는 상당히 쉬운 문제였습니다. 단순히 입력받은 점수를 반으로 나누어서 좌측 영역의 합을 구하고 우측 영역의 합을 구한 뒤 두 합끼리 비교를 하여 같으면 LUCKY를 다르면 READY를 출력해주면 됩니다.

문제 해결을 위한 팁

팁이라기보다 문법적인 내용이라고 할 수 있겠습니다. 처음에 점수를 입력받을 때 point = int(input())의 형태로 int형으로 입력받는다면 문자열의 길이를 구하는 len()의 매개변수로 point를 사용할 수 없습니다. int형태이기 때문입니다.  따라서 저는 처음에 점수를 입력받을 때 len()를 사용하기 위해 point = input()으로 문자열로 입력받았습니다.

소스코드