방구석프로의 이야기

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

문제 해결을 위한 과정

이 문제의 경우 구현 문제로 문제에서 요구하는 바를 그대로 코드로 작성하면 해결할 수 있는 문제였습니다. 

과정은 다음과 같습니다.

1. 로봇과 벨트를 함께 이동

2. 먼저 올린 순서대로 로봇 이동(먼저 올린 순서는 n-1번째부터 0번째까지 역순으로 이동하면 쉽게 해결 가능)

3. 로봇을 0번째에 올리기

4. 내구도가 0인 벨트의 수가 K 이상인지 확인하기.

단, 이때 2번, 3번 과정은 해당하는 벨트의 내구도가 1 감소한다는 것 그리고 1번, 2번 과정은 n-1번째에서 로봇이 내린다는 것을 적용하면 해결할 수 있습니다.

소스코드

n, k = map(int, input().split())
arr = list(map(int, input().split()))
robotInfo = []

ans = 0
for i in range(len(arr)):
  robotInfo.append((arr[i], ''))
  
while True:
  ans += 1
  # 1단계
  temp, robot = robotInfo[2*n-1]
  for i in range(2*n-1, 0, -1):
    robotInfo[i] = robotInfo[i-1]
  robotInfo[0] = (temp, robot)
  temp, robot = robotInfo[n-1]
  robotInfo[n-1] = (temp, "")

  # 2단계
  for i in range(n-1, -1, -1):
    temp, robot = robotInfo[i]
    if robot != "":
      nextTemp, nextRobot = robotInfo[i + 1]
      if nextTemp >= 1 and nextRobot == "":
        robotInfo[i] = (temp, "")
        robotInfo[i + 1] = (nextTemp-1, "exist")
  temp, robot = robotInfo[n-1]
  robotInfo[n-1] = (temp, "")
  
  # 3단계
  temp, robot = robotInfo[0]
  if temp >= 1:
    robotInfo[0] = (temp-1, "exist")

  # 4단계
  cnt = 0
  for i in range(0, 2*n):
    temp, robot = robotInfo[i]
    if temp == 0:
      cnt += 1
  if cnt >= k:
    break
print(ans)

https://school.programmers.co.kr/learn/courses/30/lessons/42579

문제 해결을 위한 과정

이 문제는 딕셔너리를 사용하면 쉽게 해결할 수 있었습니다. 장르를 키, 횟수를 값으로 하면 다음과 같습니다. 

classic: 1450, pop: 3100. 이때 전체의 genres 및 plays 리스트를 조회하면서 temp 리스트에 장르별 전체 재생 횟수, 고유번호, 노래재생 횟수를 넣습니다. 이렇게 되면 다음과 같습니다.

temp = [(1450, 3, 800), (3100, 1, 600), (1450, 2, 150), (1450, 3, 800), (3100, 4, 2500)] 

이 temp를 재생횟수 내림차순 - 같으면 곡 재생 횟수 내림차순 - 같으면 고유번호 오름차순으로 정렬을 합니다. 그렇게 되면 다음과 같이 됩니다.

temp = [(3100, 4, 2500), (3100, 1, 600), (1450, 3, 800), (1450, 0, 500), (1450, 2, 150)]

이후 각 장르별로 두 곡씩 answer에 담아서 return 하면 됩니다.

소스코드

def solution(genres, plays):
    answer = []
    music_dict = {}
    temp = []
    for i in range(len(genres)):
        if genres[i] not in music_dict:
            music_dict[genres[i]] = plays[i]
        else:
            music_dict[genres[i]] += plays[i]
    
    for i in range(len(genres)):
        temp.append((music_dict[genres[i]], i, plays[i]))
    
    temp.sort(key = lambda x: (-x[0], -x[2], x[1]))
    gen = {}
    for i in range(len(temp)):
        if temp[i][0] not in gen:
            gen[temp[i][0]] = 1
            answer.append(temp[i][1])
        elif temp[i][0] in gen:
            if gen[temp[i][0]] == 1:
                gen[temp[i][0]] += 1
                answer.append(temp[i][1])
            else:
                continue
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/86491

문제 해결을 위한 과정

이 문제는 sizes 배열의 각 행마다 정렬을 해준 뒤 가로, 세로 최댓값을 구하면 쉽게 해결할 수 있는 문제였습니다.

def solution(sizes):
    answer = 0
    for i in range(len(sizes)):
        sizes[i].sort()
    maxA = 0
    maxB = 0
    
    for a, b in sizes:
        maxA = max(maxA, a)
        maxB = max(maxB, b)
    answer = maxA * maxB
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/1845

문제 해결을 위한 과정

이 문제는 해시를 이용하면 쉽게 풀 수 있는 문제였습니다. 각 폰켓몬들을 딕셔너리에 추가해 주고 n/2보다 딕셔너리의 수가 크거나 같다면 n/2를, 그렇지 않다면 딕셔너리의 수를 return 해주면 되는 문제입니다.

소스코드

def solution(nums):
    answer = 0
    pocket_dict = {}
    for i in range(len(nums)):
        if nums[i] not in pocket_dict:
            pocket_dict[nums[i]] = 1
        else: 
            pocket_dict[nums[i]] = 1
            
    if len(nums)//2 <= len(pocket_dict): 
        answer=len(nums)//2
    else: 
        answer=len(pocket_dict)
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/42578

문제 해결을 위한 과정

이 문제는 가장 쉽게 해결 방법을 떠올릴 수 있는 건 이중 for문이다. 그러나 이중 for문을 사용하면 phone_book의 길이는 1 이상 1,000,000 이하입니다.라는 조건 때문에 최대 1,000,000 * 1,000,000 = 1,000,000,000,000 1조 번의 연산을 수행하면 이는 시간 초과 (TLE)로 이어진다.(파이썬은 1초에 20,000,000번 연산 가) 따라서 TLE를 받지 않기 위해서는 이중 for문이 아닌, Hash를 사용하여 단일 for문으로 풀어야 함을 알 수 있다. 각각을 조회하며 각 번호가 접두사로 존재하는지 확인하고, 번호 전체를 Hash에 등록해 주면 된다. (소스코드 참고) 

단, 이때 예외케이스가 발생할 수 있는데 바로 정렬의 문제이다. ["1192345", "119"]로 phone_book이 있다면 이를 정렬하여 ["119", "1192345"]로 정렬을 한 뒤 진행해야 한다. 그렇지 않다면 위 경우는 True를 return하며 이는 오답이 될 것이다.

 소스코드

def solution(phone_book):
    answer = True
    phone_dict = {}
    phone_book.sort()
    for i in range(len(phone_book)):
        for j in range(1, len(phone_book[i]) + 1):
            if phone_book[i][:j] in phone_dict:
                return False
        if phone_book[i] not in phone_dict:
            phone_dict[phone_book[i]] = 1
        
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/42578

문제 해결을 위한 과정

이 문제의 경우 dict를 이용하면 쉽게 해결할 수 있었습니다. 얼굴(1번 용품, 2번 용품), 상의(1번 용품, 2번 용품), 하의(1번 용품) 이렇게 있을 때 입는 경우는 다음과 같습니다.

얼굴(1번 용품, 2번 용품, 아무것도 안 입는 경우) - 3가지

상의(1번 용품, 2번 용품, 아무것도 안입는 경우) - 3가지

하의(1번 용품, 아무것도 안 입는 경우) - 2가지

결과 =  3 x 3 x 2 - 1(아무것도 안 입는 경우)

이를 일반화 하면 다음과 같습니다.

(얼굴 + 1) * (상의  + 1) * (하의 * 1) - 1

소스코드

def solution(clothes):
    answer = 1
    cloth_dict = {}
    for name, type in clothes:
        if type in cloth_dict:
            cloth_dict[type] += 1
        else:
            cloth_dict[type] = 1
    for name, type in clothes:    
        if cloth_dict[type] != 0:
            num = cloth_dict[type]
            cloth_dict[type] = 0
            answer *= (num + 1)
    answer -= 1
    return answer

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

문제 해결을 위한 과정

이 문제의 경우 백트래킹을 통해 해결할 수 있는 문제였습니다. Queen의 경우 같은 열 혹은 같은 행에 있거나 같은 대각선에 있는 곳을 이동할 수 있습니다. 따라서 다음 그림과 같이 퀸을 놓을 수 있습니다. (단, n이 4 인 경우)

같은 행에는 다시 queen을 위치할 수 없고, 시간복잡도를 위해 2차원 배열을 1차원 배열로 단순화해서 표시할 수 있습니다. 위 그림의 경우는 다음과 같습니다. arr = [1, 3, 0, 2] 해석하면 0번째 인덱스(행)의 1번째 인덱스(열), 1번째 인덱스(행)의 3번째 인덱스(열), 2번째 인덱스(행)의 0번째 인덱스(열), 3번째 인덱스(행)의 2번째 인덱스(열)에 위치했다는 뜻입니다. 이를 완전탐색 식으로 표현하면 아래의 코드와 같습니다. 중요한 검사 로직은 같은 열에 있는지(check함수의 첫 번째 if문), 대각선에 있는지(check 함수의 두 번째 if문)으로 검사합니다. 이때 같은 행인 경우는 존재할 수 없는데 배열의 인덱스 자체가 행을 의미하기 때문에 같은 행에는 queen이 무조건 없습니다.

소스코드

n = int(input())
arr = [0] * n
count = 0

def dfs(depth):
  global count
  if depth == n:
    count += 1
    return

  for i in range(n):
    arr[depth] = i
    if check(depth):
      dfs(depth + 1)

def check(col):
  for i in range(col):
    if arr[i] == arr[col]:
      return False
    elif abs(i-col) == abs(arr[i]-arr[col]):
      return False
  return True

dfs(0)
print(count)

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

문제 해결을 위한 과정

이 문제의 경우 역시 마찬가지로 구현 문제이므로 차분하게 조건을 작성하면 해결할 수 있었다. 돌리게 되는 톱니를 기준으로 좌측 영역, 우측 영역을 분리하여 각자 맞게 회전을 시켜주었다. 다만 이때 flagLeft(왼쪽에 맞물리는 부분) flagRight(우측에 맞물리는 부분)을 for문 내부에 그대로 넣어서 덮어진 값을 사용하게 되어 틀렸습니다. 를 받게 되었다. 따라서 tempFlagLeft, tempFlagRight로 분리하여 덮어씌워짐을 방지 하였다.

소스코드

arr = [[] for _ in range(4)]
for i in range(4):
   tempArr = input()
   for j in range(len(tempArr)):
       arr[i].append(int(tempArr[j]))
k = int(input())
moves = []
for _ in range(k):
    a, b = map(int, input().split())
    moves.append((a, b))

def turn_right(array):
    right = array[7]
    for i in range(6, -1, -1):
        array[i + 1] = array[i]
    array[0] = right

def turn_left(array):
    left = array[0]
    for i in range(0, 7):
        array[i] = array[i + 1]
    array[7] = left

for x in range(k):
    num, dir = moves[x]
    num -= 1 # index 맞추기 위함
    flagLeft = arr[num][6]
    flagRight = arr[num][2]
    if dir == 1:
        turn_right(arr[num])
    else:
        turn_left(arr[num])
    tempDir = dir
    tempFlagLeft = flagLeft
    tempFlagRight = flagRight
    for i in range(num-1, -1, -1):
        if tempFlagLeft != arr[i][2]:
            if tempDir == 1:
                tempFlagLeft = arr[i][6]
                tempFlagRight = arr[i][2]
                turn_left(arr[i])
                tempDir *= -1
            else:
                tempFlagLeft = arr[i][6]
                tempFlagRight = arr[i][2]
                turn_right(arr[i])
                tempDir *= -1
        else:
            break
    tempDir = dir
    tempFlagLeft = flagLeft
    tempFlagRight = flagRight
    for i in range(num + 1, 4):
        if tempFlagRight != arr[i][6]:
            if tempDir == -1:
                tempFlagLeft = arr[i][6]
                tempFlagRight = arr[i][2]
                turn_right(arr[i])
                tempDir *= -1
            else:
                tempFlagLeft = arr[i][6]
                tempFlagRight = arr[i][2]
                turn_left(arr[i])
                tempDir *= -1
        else:
            break

ans = 0
for i in range(len(arr)):
    if arr[i][0] == 1:
        if i == 0:
            ans += 1
        elif i == 1:
            ans += 2
        elif i == 2:
            ans += 4
        else:
            ans += 8
print(ans)