그냥 코딩하는 사람의 블로그

풀이 과정

1. 재귀함수를 사용하여 구현하면 쉽게 구현할 수 있다.
   • 재귀함수를 통해 전체 사전을 구성
   • 구성한 사전들 중 입력받은 단어가 몇번째에 있는지 검사
2. 재귀함수의 하나의 함수 내에서 하는 역할은 다음과 같다.
   • 현재의 단어를 사전에 저장
   • A, E, I, O, U 각각을 붙여서 다음 재귀함수 호출
   • 단어의 길이가 6을 넘어가면 종료

소스 코드

dictionary = []

def recursion(p, step):
    if step == 6:
        return
    if p != '':
        dictionary.append(p)
    for c in ['A', 'E', 'I', 'O', 'U']:
        recursion(p+c, step+1)

def solution(word):
    answer = 0
    recursion('', 0)
    for i in range(len(dictionary)):
        if dictionary[i] == word:
            answer = i+1
            break

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 모든 직업군을 탐색하면서 주어진 언어별 선호도와 직업군 언어 점수의 곱셈의 합을 구한다.
   • 만약, 이 합계가 최대값인 경우 갱신 / 직업군 이름 저장
   • 이 과정에서, 직관적으로 계산하기 위해 파이썬 딕셔너리 활용
   • {직업군명 : 점수} 형식으로 저장
2. 계산시, 개발자가 선호하는 언어에는 있지만, 직업군에서 선호하는 언어에 없을수도 있음.
   • 딕셔너리의 get 메서드를 써서 있는지 확인해주어야 한다.
   • 없는 경우에는 계산 생략
3. 동점인 경우에는 사전순으로 앞서는걸 정답으로 해주어야 한다.

소스 코드

def solution(table, languages, preference):
    answer = ''

    score = {languages[i]: preference[i] for i in range(len(languages))}    
    max_score = 0
    for information in table:
        inf = information.split()
        # 언어별 점수 부여
        current_score = {inf[i]: 6-i for i in range(1, len(inf))}
        total_score = 0
        # 현재 직업에서의 점수 구함
        for lan in score.keys():
            if current_score.get(lan) != None:
                total_score += (current_score[lan] * score[lan])

        # 동점이면 사전순으로 앞서는걸 정답으로
        if total_score == max_score:
            if answer > inf[0]:
                answer = inf[0]

        # 최대 점수일때 갱신
        if total_score > max_score:
            max_score = total_score
            answer = inf[0]

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 열별로 진행한다.
   • 최저점인 행, 최고점인 행, 최저점인 인원 수, 최고점인 인원 수를 구한다.
2. 평균 계산
   • 최저점이거나 최고점인 행이 현재 진행중인 열과 같고(자기 자신이 낸 점수)
   • 유일한 인원인지 검사 필요 !! ( 최고점/최저점 인원수가 1인지 )
   • 해당 점수는 빼주고, 인원수도 1 줄여준다.
   • 이후, 평균을 계산하고 평균에 따라 학점을 매겨주면 된다.

• 구현 문제는 너무 복잡한거 같다..

소스 코드

def solution(scores):
    answer = ''
    for j in range(len(scores[0])):
        min_idx = 0
        max_idx = 0
        min_count = 1
        max_count = 1
        score_sum = scores[0][j]
        for i in range(1, len(scores)):
            # 최저점인지 검사
            if scores[i][j] <= scores[min_idx][j]:
                # 최저점이면서 동일한 점수가 있다면 인원수 증가
                if scores[i][j] == scores[min_idx][j]:
                    min_idx = i if i == j else min_idx
                    min_count += 1
                else:
                    min_idx = i
                    min_count = 1

            # 최고점인지 검사
            if scores[i][j] >= scores[max_idx][j]:
                # 최고점이면서 동일한 점수가 있다면 인원수 증가
                if scores[i][j] == scores[max_idx][j]:
                    max_idx = i if i == j else max_idx
                    max_count += 1
                else:
                    max_idx = i
                    max_count = 1

            score_sum += scores[i][j]

        # 점수 계산 파트( 자기가 낸 점수가 유일한 최고점, 최저점이라면 빼고 계산 )
        total_student = len(scores)
        if (min_idx == j and min_count == 1) or (max_idx == j and max_count == 1):
            p = min_idx if min_idx == j else max_idx
            total_student -= 1
            score_sum -= scores[p][j]

        avg = score_sum / total_student

        if avg >= 90: answer += 'A'
        elif avg >= 80: answer += 'B'
        elif avg >= 70: answer += 'C'
        elif avg >= 50: answer += 'D'
        else: answer += 'F'

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

• 문자열의 길이가 최대 50글자까지밖에 되지 않으므로..
  • zero ~ nine까지 모든 문자열이 전체 문자열 s에 있는지 검사
  • 있다면, 해당 문자열을 replace 해주면 된다.

소스 코드

def solution(s):
    string_dict = {'zero': 0, 'one': 1, 'two': 2, 'three': 3,
                  'four': 4, 'five': 5, 'six': 6, 'seven': 7,
                  'eight': 8, 'nine': 9}    
    answer = 0
    for string in string_dict.keys():
        if string in s:
            s = s.replace(string, str(string_dict[string]))
    answer = int(s)
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 위 그림을 보면 바깥쪽 삼각형을 채우고, 안쪽 삼각형을 채우는 구조로 볼 수 있다.
2. 삼각형을 채울 때는, 맨 위 시작점을 기준 3가지 과정을 거친다.
   1. 아래로 이동
   2. 우측으로 이동
   3. 왼쪽 위 대각선으로 이동
3. 시작점을 조정해 가면서 2번 과정을 거치면 된다.
   • 시작점의 경우 (0, 0), (2, 1), ... (2n, n)
4. 종료 조건은 모든 삼각형을 채운 경우이다.

소스 코드

def solution(n):
    lists = [[0] * i for i in range(1, n+1)]
    idx = 1
    i = 0
    while True:
        x = 2 * i
        y = i
        i += 1

        # 아래 내려가는 부분
        while x < n and lists[x][y] == 0:
            lists[x][y] = idx
            x += 1
            idx += 1
        x -= 1

        # 오른쪽 진행
        y += 1
        while y < x+1 and lists[x][y] == 0:
            lists[x][y] = idx
            y += 1
            idx += 1
        y -= 1

        # 대각선 왼쪽 위 진행
        x -= 1; y -= 1
        while lists[x][y] == 0:
            lists[x][y] = idx
            x -= 1
            y -= 1
            idx += 1

        # 전체 체크
        end = True
        for l in lists:
            for e in l:
                if e == 0:
                    end = False
                    break
            if not end:
                break

        if end:
            break

    answer = []

    # 정답 저장
    for l in lists:
        for e in l:
            answer.append(e)
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

• row와 column의 범위가 작은 편이므로 combinations를 사용하여서 풀이

1. 모든 column의 조합들을 구한다. (1개 ~ column의 길이)
2. 각각의 column 조합에 대해 최소성과 유일성 검사
   • 최소성의 경우는, 각 column의 조합에 대해 다시 조합들을 구한 뒤, 조합들중 하나라도 후보키에 있는지 검사
   • 유일성의 경우는, 릴레이션에서 각 튜플들에 대해 column의 조합으로 데이터를 구성하여 하나씩 넣어본 다음, 중복되는 요소가 있다면 유일성 만족하지 않음.
3. 후보키의 개수를 리턴해주면 된다.

소스 코드

from itertools import combinations

# 유일성 만족 확인
def simulation(relation, columns):
    compare_set = set()
    for tup in relation:
        target = []
        for col in columns:
            target.append(tup[col])
        target = tuple(target)
        if target in compare_set:
            return False
        compare_set.add(target)
    return True

# 최소성 확인(자신보다 짧은 최소키가 있는지)
def check_in_set(candidate, case):
    case_len = len(case)

    for i in range(1, case_len+1):
        total_case = list(combinations(case, i))
        for case_ in total_case:
            if case_ in candidate:
                return False
    return True


def solution(relation):
    answer = 0
    col_len = len(relation[0])
    cols = [i for i in range(col_len)]
    candidate = set()
    for i in range(1, col_len+1):
        all_case = list(combinations(cols, i))
        for case in all_case:
            # 유일성과 최소성을 만족하는지 확인
            if check_in_set(candidate, case) and simulation(relation, case): 
                candidate.add(case)
                answer += 1

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. "ICN"이 시작점이므로, ICN에서 시작하여 DFS를 진행하면서, DFS의 깊이가 ticket의 길이까지 진행되는지 체크
   • 이 때, 가능한 경로가 2개 이상인 경우 알파벳 순서가 앞서는 경로를 return 해주어야 한다.
   • 따라서, 시작하기 전에 tickets의 2번째 요소([i][2]) 기준으로 오름차순 정렬 해 준다.
2. DFS를 진행하면서 정답과 방문여부에 push/pop 해주고, DFS를 ticket의 길이만큼 깊게 진행하였다면 정답 리스트를 출력해주면 된다.

• DFS의 이론은 알겠는데 Recursion에서 정답을 어떻게 표시해 주어야 할지 공부가 더 필요함..

소스 코드

end_flag = False
answer = []

def dfs(tickets, visited, city):
    global end_flag, answer
    if len(visited) == len(tickets):
        answer.append(city)
        end_flag = True
        return

    for i in range(len(tickets)):
        if tickets[i][0] == city and i not in visited:
            visited.add(i)
            answer.append(tickets[i][0])
            dfs(tickets, visited, tickets[i][1])
            if end_flag:
                return
            answer.pop()
            visited.remove(i)


def solution(tickets):
    global answer
    tickets.sort(key=lambda x:x[1])
    dfs(tickets, set(), "ICN")

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 현재 자리수가 맨 앞자리라고 할때, 뒷자리 가능한 경우의 수는 (n-1)!이다.
   • 따라서, 맨 앞자리가 1일때는 0(n-1)!, 맨 앞자리가 2일때는 (n-1)!(n-2)!, ... 의 범위를 갖게 된다.
2. 따라서, 맨 앞자리부터 범위를 구한다.
   • 해당 범위라면, 현재 남아있는 경우의 수에서
     1. 범위의 최솟값을 빼주고
     2. 사용 가능한 숫자 리스트에서 제거
     3. 범위 조정
   • 범위를 조정하는 방식은 (n-1)!에서 (n-1)을 나누어주어 (n-2)!로 만들어 준다.
   • 해당 범위가 아니라면, 범위를 조정해가면서 검사한다.
3. 매 순간 범위에 해당하는 경우를 answer에 넣어주면 된다.

소스 코드

def solution(n, k):
    answer = []
    candidate = list(i+1 for i in range(n))
    # 맨 앞자리가 고정되었을때 뒷자리 가능한 경우의 수
    p = factorial(n-1) 
    div = n-1

    while div >= 0:
        fr = 0
        to = p
        for idx in range(len(candidate)):
            if fr <= k and k <= to: 
                # 현재 범위 내에 들어가는 경우
                answer.append(candidate[idx])
                # 현재 범위의 최솟값을 빼줌
                k = k - fr
                if div != 0:
                    # 맨 앞자리가 무엇이 나오는지 알음. 
                    # 따라서 다음 자리를 구해야 하므로 n-1자리를 검사했다면
                    # factorial의 결괏값에 n-1을 나누어주면 n-2!이 나옴.
                    p = p // div 
                # 자리수 조정
                div -= 1 
                del candidate[idx] # 현재 사용된 숫자는 지워줌.
                break
            else: 
                # 현재 범위 내에 들어가지 않으면 다음 범위
                fr = fr + p
                to = to + p

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 곱이 최대가 되려면 집합의 모든 수가 비슷한 값을 가질때가 최대이다
   • 예시) n = 3, s = 9라면, (3, 3, 3)이 최대값
2. 따라서.. s를 n으로 나눈 값들을 넣어 주고, 나머지값은 n+1을 넣어서 채워준다.
   • 즉, s//n을 (n - (s % n))개 넣어주고, (s//n)+1을 (s % n)개 넣어주면 된다.
3. 결과값을 오름차순으로 정렬해준다.

소스 코드

def solution(n, s):
    answer = []
    temp = s // n
    p = s

    if temp == 0:
        return [-1]

    if s % n == 0:
        answer = [temp] * n
    else:
        answer = [temp + 1] * (s % n) + [temp] * (n - (s % n))

    answer.sort()
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. works를 내림차순으로 정렬한다(작업량 순)
2. 거듭제곱의 합을 최소로 하려면 가장 큰 작업량부터 줄여야 한다.
   • 따라서, 가장 큰 작업량을 기준으로 1씩 빼주면서.
   • 각 작업들을 루프돌면서 현재 작업량보다 크다면 1을 빼주고, 작다면 바로 종료(내림차순으로 정렬하였으므로 아래는 모두 작음), 평탄화한다고 생각하면 됨.
   • 이 과정을 총 빼준 값이 n이 될때까지 하면 된다.

     

3. answer 전체를 제곱후 더하면 된다.

소스 코드

from collections import deque

def solution(n, works):
    answer = 0
    cut = 0
    flag = False
    works.sort(reverse=True)
    m_height = works[0]
    for height in range(m_height, 0, -1): 
    # 작업량을 높이로 두고 한층씩 잘라가면서 생각
        for i in range(len(works)):
            if works[i] == height:
                cut += 1
                works[i] -= 1
                if cut == n: # n개 자르면 종료
                    flag = True
                    break
            else: 
                # 내림차순 정렬했으므로 높이보다 작아지면 바로 break
                break
        if flag:
            break

    for work in works:
        answer += work * work

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges