[programmers] 과일 장수, 모음 사전, 혼자서 하는 틱택토

💡 오늘의 학습 키워드
- 과일 장수
- 모음 사전
- 혼자서 하는 틱택토

 

🥉 과일 장수

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/135808

 

문제 설명

과일 장수가 사과 상자를 포장하고 있습니다.
사과는 상태에 따라 1점부터 k점까지의 점수로 분류하며,
k점이 최상품의 사과이고 1점이 최하품의 사과입니다. 사과 한 상자의 가격은 다음과 같이 결정됩니다.

한 상자에 사과를 m개씩 담아 포장합니다.
상자에 담긴 사과 중 가장 낮은 점수가 p (1 ≤ p ≤ k)점인 경우, 사과 한 상자의 가격은 p * m 입니다.

과일 장수가 가능한 많은 사과를 팔았을 때, 얻을 수 있는 최대 이익을 계산하고자 합니다.
(사과는 상자 단위로만 판매하며, 남는 사과는 버립니다)
예를 들어, k = 3, m = 4, 사과 7개의 점수가 [1, 2, 3, 1, 2, 3, 1]이라면,
다음과 같이 [2, 3, 2, 3]으로 구성된 사과 상자 1개를 만들어 판매하여 최대 이익을 얻을 수 있습니다.

(최저 사과 점수) x (한 상자에 담긴 사과 개수) x (상자의 개수) = 2 x 4 x 1 = 8

사과의 최대 점수 k, 한 상자에 들어가는 사과의 수 m, 사과들의 점수 score가 주어졌을 때,
과일 장수가 얻을 수 있는 최대 이익을 return하는 solution 함수를 완성해주세요.

제한 사항
1. 3 ≤ k ≤ 9
2. 3 ≤ m ≤ 10
3. 7 ≤ score의 길이 ≤ 1,000,000
    3-1. 1 ≤ score[i] ≤ k
4. 이익이 발생하지 않는 경우에는 0을 return 해주세요.

 

문제 회고

💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지

리스트를 정렬하고 나누고 특정 리스트 원소를 추출하는 단순 구현 문제입니다.
입력 받은 사과 점수 리스트를 상자 크기에 맞게 정렬하는 부분에서 약간의 고민이 들어갔습니다.
문제 해결 과정은 다음과 같습니다.

1. 입력 받은 사과 점수 리스트를 크기에 맞게 자르기 위해 정렬합니다.
2. m개의 단위로 리스트를 나누어 저장합니다.
3. m개로 분리된 리스트를 구분하여 각각의 최솟값을 더하여 리턴합니다. 

리스트 쪼개는 과정에서 2차원 리스트가 되었는데, 리스트 하나로도 풀 수 있을 것 같아
append 과정을 생략하고 리스트 하나로 개선하여 풀어보았습니다.

💡 내가 해결한 방식은?

리스트 연산을 통한 최대 이익 구하기

def solution(k, m, score):
    answer = 0
    score_list = []
    # score 정렬 후 내림차순 정렬
    score.sort(reverse=True)
    # score 리스트 내림차순 정렬
    # score.reverse()
    # m개 단위로 리스트 나누기
    for i in range(0, len(score), m):
        score_list.append(score[i:i+m])
    
    # 각 리스트의 가장 작은 값 추출
    for i in range(len(score_list)):
        if len(score_list[i]) == m:
            answer += min(score_list[i])
            
    return answer*m

개선된 코드

def solution(k, m, score):
    answer = 0
    score.sort(reverse=True)
    for i in range(0, len(score), m):
        if len(score[i:i+m]) == m:
            answer += min(score[i:i+m])
    return answer * m

---

🥈 모음 사전

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/84512

 

문제 설명

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는,
길이 5 이하의 모든 단어가 수록되어 있습니다.
사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.
단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록
solution 함수를 완성해주세요.

제한 사항
1. word의 길이는 1 이상 5 이하입니다.
2. word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.

 

문제 회고

💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지

재귀함수를 통한 DFS 완전 탐색으로 해결 가능했던 문제였습니다. 풀이 로직은 다음과 같습니다.

1. 모음 알파벳 리스트를 만들어 줍니다.
2. 단어 생성 함수로 기저 코드는 단어 길이 5개로 제한합니다.
3. 모음 5개를 순회하며 처음 단어에 모음을 추가하는 재귀 코드를 수행합니다.
4. 단어 추가는 모음 생성 과정에 계속해서 append 될 수 있도록 구현합니다.
5. 생성된 단어 리스트에 입력받은 단어의 index 값을 리턴해줍니다.

재귀 흐름만 알 수 있다면 구현 자체는 어렵지 않았습니다.

answer.index(word) + 1

단어 리스트를 생성하고 word 값의 인덱스를 찾는 반복문을 작성하다가 
index 함수를 알게 되었고 이 함수를 사용해 원하는 인덱스를 한번에 찾을 수 있었습니다.

💡 내가 해결한 방식은?

def solution(word):
    answer = []
    vowels = ['A', 'E', 'I', 'O', 'U']
    # dfs 재귀 완전 탐색
    def generate_words(curr_word):
        if len(curr_word) == 5:
            return
        
        for vowel in vowels:
            answer.append(curr_word + vowel)
            generate_words(curr_word + vowel)
    
    generate_words('');
    
    return answer.index(word) + 1

---

🥇 혼자서 하는 틱택토

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/160585

 

문제 설명

틱택토는 두 사람이 하는 게임으로 처음에 3x3의 빈칸으로 이루어진 게임판에
선공이 "O", 후공이 "X"를 번갈아가면서 빈칸에 표시하는 게임입니다.
가로, 세로, 대각선으로 3개가 같은 표시가 만들어지면 같은 표시를 만든 사람이 승리하고 게임이 종료되며
9칸이 모두 차서 더 이상 표시를 할 수 없는 경우에는 무승부로 게임이 종료됩니다.
할 일이 없어 한가한 머쓱이는 두 사람이 하는 게임인 틱택토를 다음과 같이 혼자서 하려고 합니다.

혼자서 선공과 후공을 둘 다 맡는다.
틱택토 게임을 시작한 후 "O"와 "X"를 혼자서 번갈아 가면서 표시를 하면서 진행한다.

틱택토는 단순한 규칙으로 게임이 금방 끝나기에 머쓱이는 한 게임이 종료되면
다시 3x3 빈칸을 그린 뒤 다시 게임을 반복했습니다.
그렇게 틱택토 수 십 판을 했더니 머쓱이는 게임 도중에 다음과 같이 규칙을 어기는 실수를 했을 수도 있습니다.

"O"를 표시할 차례인데 "X"를 표시하거나 반대로 "X"를 표시할 차례인데 "O"를 표시한다.
선공이나 후공이 승리해서 게임이 종료되었음에도 그 게임을 진행한다.

게임 도중 게임판을 본 어느 순간 머쓱이는 본인이 실수를 했는지 의문이 생겼습니다.
혼자서 틱택토를 했기에 게임하는 과정을 지켜본 사람이 없어 이를 알 수는 없습니다.
그러나 게임판만 봤을 때 실제로 틱택토 규칙을 지켜서 진행했을 때 나올 수 있는 상황인지는
판단할 수 있을 것 같고 문제가 없다면 게임을 이어서 하려고 합니다.

머쓱이가 혼자서 게임을 진행하다 의문이 생긴 틱택토 게임판의 정보를 담고 있는 문자열 배열 board가
매개변수로 주어질 때, 이 게임판이 규칙을 지켜서 틱택토를 진행했을 때 나올 수 있는 게임 상황이면
1을 아니라면 0을 return 하는 solution 함수를 작성해 주세요.

제한 사항
1. board의 길이 = board[i]의 길이 = 3
    1-1. board의 원소는 모두 "O", "X", "."으로만 이루어져 있습니다.
2. board[i][j]는 i + 1행 j + 1열에 해당하는 칸의 상태를 나타냅니다.
    2-1. "."은 빈칸을, "O"와 "X"는 해당 문자로 칸이 표시되어 있다는 의미입니다.

 

문제 회고

💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지

 

💡 내가 해결한 방식은?

 

✍️ TIL

python 리스트는 자르고 붙이는걸로 웬만한건 다 해결할 수 있는 것 같다.
반복문으로 3-4줄 먹는 코드도 대괄호 씌우고 리스트 범위 조정해서 한줄로 표현할 수 있는게 너무 사기야..
이렇게 하루하루 파이썬에 익숙해지니 c++ 언어로 어떻게 문제를 풀어왔나 벌써 가물가물해진다.
오늘 문제들은 리스트 활용과 재귀 활용만 능숙하게 할 줄 안다면 간단하게 풀 수 있는 문제들이었지만
확실히 기본기에서 풀이 속도 차이가 난다고 느꼈다. 별거 아닌 함수나 로직에 하나만 막혀도 5분 10분
삽질은 기본이라 복잡하지 않은 문제일 수록 풀이 시간을 타이트하게 갖고 풀어야 겠다.