Implementation

문제 https://codeforces.com/problemset/problem/550/A 풀이 스트링 s가 주어지고, 이 s 안에서 서브스트링 "AB"와 "BA"가 겹쳐지지 않은 상태로 존재하면 "YES" 아니라면 "NO" 출력하면 된다. 문제에서 주어진 예시인 "ABA" 같은 경우는 "NO"가 된다. "AB"와 "BA"가 서로 따로 존재하지 않기 때문이다. 하지만 "ABCABA" 같은 경우에는 "AB"와 "BA"가 "BA"는 겹쳐져 있지만 이미 앞에서 "AB"가 존재하기 때문에, "YES"가 된다. 이런 예외들을 알아내면, 문제를 푸는 방식은 단순하다. "AB"를 찾은 후, 그 이후("B" 이후)에 있는 인덱스부터 "BA"를 찾고, 만약 존재한다면 "YES", 존재하지 않는다면 다시 "BA"를 먼저 찾은 후, "A"의 인덱스 이후에 있는 인덱스부터 "AB"를 찾으면 된다. 둘 다 불가능하다면 "NO"가 된다. ...

문제 https://codeforces.com/problemset/problem/25/A 풀이 n 개의 원소를 가진 수열이 입력으로 들어오고 입력으로 들어온 숫자 중 홀/짝이 다른 하나의 숫자의 인덱스(1-base 인덱스)를 출력하면 된다. 수열이 들어올 때마다 홀/짝 각각의 마지막 인덱스를 저장하고, 홀수의 개수, 짝수의 개수를 세면된다. 마지막 이렇게 얻어진 개수로 홀/짝인지 판별을 한 뒤에, 홀수면 짝수의, 짝수면 홀수의 마지막 인덱스를 출력하면 된다. 코드 #include <iostream> int main() { int n; std::cin >> n; int oddCount = 0; int evenCount = 0; int oddIndex = 0; int evenIndex = 0; for (int i = 1; i <= n; ++i) { int number; std::cin >> number; if (number % 2 == 0) { evenCount++; evenIndex = i; } else { oddCount++; oddIndex = i; } } std::cout << (oddCount == 1 ? oddIndex : evenIndex) << std::endl; }

문제 https://school.programmers.co.kr/learn/courses/30/lessons/68646 풀이 문제의 조건은 쉬운데, 풀이 과정은 쉽지 않아보인다. 하지만 문제를 최대한 단순화해보자. 기본적으로, 인접한 두 풍선을 고를 수 있고 두 풍선중 번호가 더 큰 풍선을 터트려야 한다. 하지만 1회에 한정에서 번호가 더 작은 풍선을 터트릴 수 있다. 일단 기본적으로 마지막까지 남을 수 있는 풍선의 개수를 세야 하므로 모든 풍선에 대해 확인해봐야 한다. 그리고 마지막까지 남을 수 있는 풍선이라고 했으므로, 항상 마지막에 고르는 두 풍선들 중 하나는 현재 내가 확인하고 싶은 풍선일 것이다. ...

문제 https://www.acmicpc.net/problem/14891 풀이 상황 설명이 굉장히 난해하고 비직관적이므로 글을 잘 읽어야 한다. 문제를 겨우 이해하고 나면 알고리즘이나 구현 능력 자체는 크게 요구하지 않는다. 글을 이해하는것 자체가 이 문제의 가장 큰 난관이다. 이 문제에서 톱니바퀴는 현실의 톱니바퀴처럼 움직이지 않는다. 이전 톱니바퀴가 회전하면 다음 톱니바퀴도 회전해야할지 말아야 할지를 이미 돌아간 상태의 이전 톱니바퀴가 아닌 돌기 전의 이전 톱니바퀴의 상태로 판단해야 한다. 코드 class Gear(): def __init__(self, stat): self.__stat = stat self.__top = 0 self.__left = 6 self.__right = 2 def rotate(self, drct): self.__top = (self.__top - drct) % 8 self.__left = (self.__left - drct) % 8 self.__right = (self.__right - drct) % 8 @property def top(self): return self.__stat[self.__top] @property def left(self): return self.__stat[self.__left] @property def right(self): return self.__stat[self.__right] def left_shift(gear_num, drct): new_drct = drct * -1 cur_gear = gear_num for next_gear in range(gear_num - 1, 0, -1): if gears[next_gear].right != gears[cur_gear].left: rotate_queue.append((next_gear, new_drct)) cur_gear = next_gear new_drct *= -1 else: break def right_shift(gear_num, drct): new_drct = drct * -1 cur_gear = gear_num for next_gear in range(gear_num + 1, 5): if gears[next_gear].left != gears[cur_gear].right: rotate_queue.append((next_gear, new_drct)) cur_gear = next_gear new_drct *= -1 else: break gear1 = Gear(list(map(int, input()))) gear2 = Gear(list(map(int, input()))) gear3 = Gear(list(map(int, input()))) gear4 = Gear(list(map(int, input()))) gears = [None, gear1, gear2, gear3, gear4] k = int(input()) answer = 0 rotate_queue = [] for _ in range(k): num, drct = map(int, input().split()) rotate_queue.append((num, drct)) left_shift(num, drct) right_shift(num, drct) for g, d in rotate_queue: gears[g].rotate(d) rotate_queue = [] rank = 1 for idx in range(1, 5): answer += gears[idx].top * rank rank *= 2 print(answer)

문제 https://www.acmicpc.net/problem/14890 풀이 경사로의 방향을 생각해보면 왼쪽에서 오른쪽으로 올라가는 방향이 있을 것이고, 그 반대인 오른쪽에서 왼쪽으로 올라가는 방향도 있을 것이다. 이러한 경우에는 한 번에 해결하기 보다는 배열을 정방향, 역방향으로 각각 순회하여 경사로를 만들어주는 것이 좋다. 따라서 알고리즘은 다음과 같다. 주어진 2차원 배열을 Transpose한 배열을 하나 더 만든다. 세로 모양의 길을 찾기 위해서이다. 정방향으로 우선 순회한다. 다음에 있는 칸의 높이가 현재 칸보다 같으면 count를 하나 늘리고(count는 경사로를 지을 수 있는지 판단할 때 사용한다.) 1 낮으면 일단은 패스(역방향에서 확인한다), 1 높으면 경사로를 설치할 수 있는지 판단한다. 경사로를 설치할 수 있는지 판단하는 기준은 두 가지이다. 일단 경사로를 설치하기 충분한 공간이 확보되었는가 (count로 충분한 공간이 얼마나 있는지를 알 수 있다.), 만약 가능하다면 이미 그곳에 경사로가 설치되어 있지는 않는가(이는 is_built 배열로 추적한다. 하지만 정방향을 먼저 하므로 지금 상황에선 필요 없다.) 역방향으로 순회한다. 정방향과 같지만 정방향을 순회하면서 경사로를 지은 곳을 유의할 필요가 있다. 코드 def check(line): is_built = [False] * n current_height = line[0] count = 1 for idx in range(1, n): if current_height == line[idx]: count += 1 elif current_height - line[idx] == 1: current_height = line[idx] continue elif current_height - line[idx] == -1: if count >= l: for back in range(1, l + 1): is_built[idx - back] = True count = 1 else: return False current_height = line[idx] else: return False current_height = line[n - 1] count = 1 for idx in range(n - 2, -1, -1): if current_height == line[idx]: count += 1 elif current_height - line[idx] == 1: current_height = line[idx] continue elif current_height - line[idx] == -1: if count >= l: for back in range(1, l + 1): if is_built[idx + back]: return False is_built[idx + back] = True count = 1 else: return False current_height = line[idx] else: return False return True n, l = map(int, input().split()) graph = [] graph_tranposed = [[0] * n for _ in range(n)] answer = 0 for _ in range(n): graph.append(list(map(int, input().split()))) for row in range(n): for column in range(n): graph_tranposed[row][column] = graph[column][row] for idx in range(n): answer += 1 if check(graph[idx]) else 0 answer += 1 if check(graph_tranposed[idx]) else 0 print(answer)

문제 https://www.acmicpc.net/problem/14499 풀이 특별한 알고리즘이나 문제 해결 기법을 사용할 필요 없이, 순수하게 딕셔너리 자료구조만을 사용해서 풀 수 있는 문제이다. 주어진 주사위의 전개도를 이용하여 각 면에 숫자를 붙이고(면에 써져있는 숫자가 아닌 각 면을 인식하게 해주는 숫자, 이하 ID숫자라고 하겠다.) 이를 방향: ID 숫자의 꼴로 딕셔너리를 생성한다. 또 ID숫자: 면에 적힌 숫자 꼴로 딕셔너리를 하나 더 생성하여 두개의 딕셔너리로 주사위의 방향과 각 면에 적혀있는 숫자를 추적할 수 있다. 코드 import copy def north(): global dice_drct original_drct = copy.deepcopy(dice_drct) for new, ori in zip(["u", "l", "n", "e", "w", "s"], ["s", "n", "u", "e", "w", "l"]): dice_drct[new] = original_drct[ori] def south(): global dice_drct original_drct = copy.deepcopy(dice_drct) for new, ori in zip(["u", "l", "n", "e", "w", "s"], ["n", "s", "l", "e", "w", "u"]): dice_drct[new] = original_drct[ori] def east(): global dice_drct original_drct = copy.deepcopy(dice_drct) for new, ori in zip(["u", "l", "n", "e", "w", "s"], ["w", "e", "n", "u", "l", "s"]): dice_drct[new] = original_drct[ori] def west(): global dice_drct original_drct = copy.deepcopy(dice_drct) for new, ori in zip(["u", "l", "n", "e", "w", "s"], ["e", "w", "n", "l", "u", "s"]): dice_drct[new] = original_drct[ori] def change(): if graph[x][y] == 0: graph[x][y] = dice_num[dice_drct["l"]] else: dice_num[dice_drct["l"]] = graph[x][y] graph[x][y] = 0 def check(x, y): if x < 0 or x >= n or y < 0 or y >=m: return False return True n, m, x, y, k = map(int, input().split()) graph = [] for _ in range(n): graph.append(list(map(int, input().split()))) orders = list(input().split()) dice_num = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0} dice_drct = {"u": 1, "l": 6, "n": 2, "e": 3, "w": 4, "s": 5} for order in orders: isTrue = False if order == "1": if check(x, y + 1): y += 1 east() change() isTrue = True if order == "2": if check(x, y - 1): y -= 1 west() change() isTrue = True if order == "3": if check(x - 1, y): x -= 1 north() change() isTrue = True if order == "4": if check(x + 1, y): x += 1 south() change() isTrue = True if isTrue: print(dice_num[dice_drct["u"]])