CodeDrive

문제:

영문 알파벳 대문자로 이루어진 두 단어가 다음의 두 가지 조건을 만족하면 같은 구성을 갖는다고 말한다.

1. 두 개의 단어가 같은 종류의 문자로 이루어져 있다.
2. 같은 문자는 같은 개수 만큼 있다.

예를 들어 "DOG"와 "GOD"은 둘 다 'D', 'G', 'O' 세 종류의 문자로 이루어져 있으며 양쪽 모두 'D', 'G', 'O' 가 하나씩 있으므로 이 둘은 같은 구성을 갖는다. 하지만 "GOD"과 "GOOD"의 경우 "GOD"에는 'O'가 하나, "GOOD"에는 'O'가 두 개 있으므로 이 둘은 다른 구성을 갖는다.

두 단어가 같은 구성을 갖는 경우, 또는 한 단어에서 한 문자를 더하거나, 빼거나, 하나의 문자를 다른 문자로 바꾸어 나머지 한 단어와 같은 구성을 갖게 되는 경우에 이들 두 단어를 서로 비슷한 단어라고 한다.

예를 들어 "DOG"와 "GOD"은 같은 구성을 가지므로 이 둘은 비슷한 단어이다. 또한 "GOD"에서 'O'를 하나 추가하면 "GOOD" 과 같은 구성을 갖게 되므로 이 둘 또한 비슷한 단어이다. 하지만 "DOG"에서 하나의 문자를 더하거나, 빼거나, 바꾸어도 "DOLL"과 같은 구성이 되지는 않으므로 "DOG"과 "DOLL"은 비슷한 단어가 아니다.

입력으로 여러 개의 서로 다른 단어가 주어질 때, 첫 번째 단어와 비슷한 단어가 모두 몇 개인지 찾아 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이하이다.

출력:

입력으로 주어진 첫 번째 단어와 비슷한 단어가 몇 개인지 첫째 줄에 출력한다.

풀이방법:

주어진 경우의 수가 많지 않기 때문에 모든 경우의 수에 대해 고려하도록 한다. main으로 선택한 단어는 비교할 단어가 들어올 때마다 복사해서 사용한다.

main 단어와 비교할 단어를 비교하면서 문자가 겹치는 것이 있는지 확인한다. 겹치는 문자가 있다면 remove를 하고 없다면 count를 증가시킨다. 모든 비교를 완료한 뒤에 count가 1 이하, 남은 단어가 1 이하인지 확인하도록 한다. 만약 각 값들이 2보다 크다면 '한 문자를 더하거나, 빼거나, 하나의 문자를 다른 문자로 바꾸어' 조건에 해당하지 않게 된다.

문제링크:

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

문제:

풀이방법:

 시간은 한정되어 있기 때문에 모든 케이스를 다 고려하는 방법으로 문제를 해결했다. 최대로 필요한 객실의 수는 입력으로 들어오는 book_time의 길이와 같다. 따라서 book_time의 높이와 시간의 길이를 가지는 배열(hotel)을 만들도록 한다.

 그리고 각 예약 손님이 사용하는 길이를 hotel 배열에 기록한다. 이 때, 10분간 청소를 하는 시간 또한 같이 고려하도록 한다. 모든 예약 손님에 대해 기록을 완료했다면 세로로 hotel 배열을 탐색하며 가장 많이 겹치는 구간을 답으로 선정한다.

문제링크:

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

문제:

세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다.

세준이는 저녁을 먹으러 갔다 와서, 자기가 쓴 수의 일부가 지워져있는 모습을 보고 충격받았다.

세준이는 수를 방금 전과 똑같이 쓰려고 한다. 하지만, N이 기억이 나지 않는다.

남은 수를 이어 붙인 수가 주어질 때, N의 최솟값을 구하는 프로그램을 작성하시오. 아무것도 지우지 않을 수도 있다.)

입력:

첫째 줄에 지우고 남은 수를 한 줄로 이어 붙인 수가 주어진다. 이 수는 최대 3,000자리다.

출력:

가능한 N 중에 최솟값을 출력한다.

풀이방법:

원래 세준이가 쓴 숫자는 다음과 같을 것이다.

12345678910111213141516....

그래서 앞에서 부터 일치하는 숫자들을 찾고서 더 이상 일치할 숫자를 찾을 수 없을 때까지 반복한다.

즉, 234092와 같은 경우에는 1234567891011121314151617181920 중 굵은 숫자의 일부분이 남은 것과 같다. 1부터 하나씩 증가하면서 234092와 비교한다. 2,3,4 에서는 바로 일치되긴 하지만 10부터는 바로 일치되지 않을 것이다. 따라서 자릿수가 늘어난 경우에는 모든 자리에서 일치하는지 여부를 확인하도록 한다.

문제링크:

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

문제:

IQ Test의 문제 중에는 공통된 패턴을 찾는 문제가 있다. 수열이 주어졌을 때, 다음 수를 찾는 문제이다.

예를 들어, 1, 2, 3, 4, 5가 주어졌다. 다음 수는 무엇인가? 당연히 답은 6이다. 약간 더 어려운 문제를 보면, 3, 6, 12, 24, 48이 주어졌을 때, 다음 수는 무엇인가? 역시 답은 96이다.

이제 제일 어려운 문제를 보자.

1, 4, 13, 40이 주어졌을 때, 다음 수는 무엇일까? 답은 121이다. 그 이유는 항상 다음 수는 앞 수*3+1이기 때문이다.

은진이는 위의 3문제를 모두 풀지 못했으므로, 자동으로 풀어주는 프로그램을 작성하기로 했다. 항상 모든 답은 구하는 규칙은 앞 수*a + b이다. 그리고, a와 b는 정수이다.

수 N개가 주어졌을 때, 규칙에 맞는 다음 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 N개의 수가 주어진다. 이 수는 모두 절댓값이 100보다 작거나 같은 정수이다.

출력:

다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다.

풀이방법:

문제에서 찾아야 하는 a와 b를 찾는 것은 연립방정식을 사용한다면 쉽게 찾을 수 있다. 하지만 A, B와 같이 특이 케이스들이 다수 존재하기 때문에 이를 위한 노력이 필요하다. 다음과 같은 케이스들이 존재할 수 있다.

1. N이 1인 경우

N이 1인 경우에는 a와 b를 알 수 없기 때문에 다음에 여러 수가 존재할 수 있다. -> A

2. N이 2인 경우

N이 2인 경우에도 a와 b를 알 수 없기 때문에 여러 수가 존재할 수 있다.(A) 하지만 첫 두 수가 같다면 a=1, b=0인 특수한 케이스에 해당하기에 마지막 수를 출력한다.

3. N이 3 이상인 경우

 N이 3 이상이면 연립방정식을 통해 a와 b를 구할 수 있게 된다. 따라서 첫 세 수를 사용하여 a와 b를 구하도록 한다. 이 때, a와 b를 정수라는 조건이 있기 때문에 소수가 구해지게 된다면 B를 출력하도록 한다.

 a와 b를 정상적으로 구해도 첫 세 수를 통해 구한 값이기 때문에 이 규칙이 주어진 배열 끝까지 동작하는지 확인하는 작업이 필요하다. 규칙이 정상적으로 작동한다면 규칙을 사용하여 다음 수를 출력하고, 그렇지 않다면 B를 출력한다.

문제링크:

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

문제:

천수는 여러 종류의 주사위를 가지고 쌓기 놀이를 하고 있다. 주사위의 모양은 모두 크기가 같은 정육면체이며 각 면에는 1부터 6까지의 숫자가 하나씩 적혀있다. 그러나 보통 주사위처럼 마주 보는 면에 적혀진 숫자의 합이 반드시 7이 되는 것은 아니다.

주사위 쌓기 놀이는 아래에서부터 1번 주사위, 2번 주사위, 3번 주사위, … 의 순서로 쌓는 것이다. 쌓을 때 다음과 같은 규칙을 지켜야 한다: 서로 붙어 있는 두 개의 주사위에서 아래에 있는 주사위의 윗면에 적혀있는 숫자는 위에 있는 주사위의 아랫면에 적혀있는 숫자와 같아야 한다. 다시 말해서, 1번 주사위 윗면의 숫자는 2번 주사위 아랫면의 숫자와 같고, 2번 주사위 윗면의 숫자는 3번 주사위 아랫면의 숫자와 같아야 한다. 단, 1번 주사위는 마음대로 놓을 수 있다.

이렇게 쌓아 놓으면 긴 사각 기둥이 된다. 이 사각 기둥에는 4개의 긴 옆면이 있다. 이 4개의 옆면 중에서 어느 한 면의 숫자의 합이 최대가 되도록 주사위를 쌓고자 한다. 이렇게 하기 위하여 각 주사위를 위 아래를 고정한 채 옆으로 90도, 180도, 또는 270도 돌릴 수 있다. 한 옆면의 숫자의 합의 최댓값을 구하는 프로그램을 작성하시오.

입력:

첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 주사위의 전개도에서 A, B, C, D, E, F 의 순서로 입력된다. 입력되는 숫자 사이에는 빈 칸이 하나씩 있다. 주사위의 개수는 10,000개 이하이며 종류가 같은 주사위도 있을 수 있다.

그림 1

출력:

첫줄에 한 옆면의 숫자의 합이 가장 큰 값을 출력한다.

풀이방법:

 주사위는 상하로 연결되어 있기 때문에, 이를 위한 새로운 인덱스가 필요하다. 따라서 각 인덱스별로 연관있는 면의 인덱스를 담고 있는 dict을 만들도록 한다.

 그리고 첫 밑면에 따라 모든 경우의 수를 고려할 수 있도록 구현하도록 한다. 1번 주사위에 따라 2번부터 주사위가 결정되기 때문이다. 밑면의 숫자를 고르면 자동으로 윗 숫자가 결정되게 되고, 옆면의 숫자는 회전이 가능하기 때문에 남은 숫자 중에 max 값을 고른다.

 그 뒤로는 첫 주사위의 윗면의 숫자로 다음 주사위의 아래 인덱스가 결정되기 때문에 주사위는 순차적으로 주사위를 올리면서 옆면 중  max 값을 찾으면 된다.

문제링크:

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

문제:

N명이 모여 숫자 게임을 하고자 한다. 각 사람에게는 1부터 10사이의 수가 적혀진 다섯 장의 카드가 주어진다. 그 중 세 장의 카드를 골라 합을 구한 후 일의 자리 수가 가장 큰 사람이 게임을 이기게 된다. 세 장의 카드가 (7, 8, 10)인 경우에는 합은 7+8+10 = 25가 되고 일의 자리 수는 5가 된다. 어떤 사람이 받은 카드가 (7, 5, 5, 4, 9)인 경우 (7, 4, 9)를 선택하면 합이 20이 되어 일의 자리 수는 0이 되고, (5, 5, 9)를 선택하면 합이 19가 되어 일의 자리 수는 9가 된다. 게임을 이기기 위해서는 세 장의 카드를 선택할 때 그 합의 일의 자리 수가 가장 크게 되도록 선택하여야 한다.

예를 들어, N=3일 때

• 1번 사람이 (7, 5, 5, 4, 9),
• 2번 사람이 (1, 1, 1, 1, 1),
• 3번 사람이 (2, 3, 3, 2, 10)의 

카드들을 받았을 경우, 세 수의 합에서 일의 자리 수가 가장 크게 되도록 세 수를 선택하면

• 1번 사람은 (5, 5, 9)에서 9,
• 2번 사람은 (1, 1, 1)에서 3,
• 3번 사람은 (2, 3, 3)에서 8의

결과를 각각 얻을 수 있으므로 첫 번째 사람이 이 게임을 이기게 된다.

N명에게 각각 다섯 장의 카드가 주어졌을 때, 세 장의 카드를 골라 합을 구한 후 일의 자리 수가 가장 큰 사람을 찾는 프로그램을 작성하시오. 가장 큰 수를 갖는 사람이 두 명 이상일 경우에는 번호가 가장 큰 사람의 번호를 출력한다.

입력:

첫 줄에는 사람의 수를 나타내는 정수 N이 주어진다. N은 2이상 1,000이하이다. 그 다음 N 줄에는 1번부터 N번까지 각 사람이 가진 카드가 주어지는 데, 각 줄에는 1부터 10사이의 정수가 다섯 개씩 주어진다. 각 정수 사이에는 한 개의 빈칸이 있다.

출력:

게임에서 이긴 사람의 번호를 첫 번째 줄에 출력한다. 이긴 사람이 두 명 이상일 경우에는 번호가 가장 큰 사람의 번호를 출력한다.

풀이방법:

 시간복잡도가 N이며, N은 최대 1000이기 때문에 브루트 포스 방법으로 해결해도 된다. 각 사람들에 대해서 모든 조합을 구한 뒤 가장 큰 일의 자리의 수를 가지고 있는 사람을 찾으면 된다.

문제링크:

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

문제:

알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다.

먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다. 각각은 적어도 길이가 1 이상인 단어여야 한다. 이제 이렇게 나눈 세 개의 작은 단어들을 앞뒤를 뒤집고, 이를 다시 원래의 순서대로 합친다.

예를 들어,

• 단어 : arrested
• 세 단어로 나누기 : ar / rest / ed
• 각각 뒤집기 : ra / tser / de
• 합치기 : ratserde

단어가 주어지면, 이렇게 만들 수 있는 단어 중에서 사전순으로 가장 앞서는 단어를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 영어 소문자로 된 단어가 주어진다. 길이는 3 이상 50 이하이다.

출력:

첫째 줄에 구하고자 하는 단어를 출력하면 된다.

풀이방법:

반복문 두 개를 사용해서 주어진 조건대로 하나씩 단어를 만들면서 해당하는 단어가 사전상 먼저 인지 확인하면 된다.

문제링크:

www.acmicpc.net/problem/1251

문제:

인체에 치명적인 바이러스르 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 NxM인 직사각형으로 나타낼 수 있으며, 직사각형은 1x1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3<=N,M<=8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

출력:

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

풀이방법:

벽을 3개 세우는 방법을 한 눈에 찾는 것은 어렵기 때문에 가능한 모든 경우의 수에 대해 벽을 세워보면서 안전 영역 크기가 최대인 경우를 찾아야 한다. 

input을 모두 받은 뒤에 지도를 한번 탐색해서 0인 점인 빈 칸과, 2인 바이러스가 담겨 있는 배열을 만든다. 그리고 itertools의 combinations를 사용해서 지도에서 빈 칸을 3개를 고르는 모든 경우의 수를 구하고, 0인 점의 배열의 길이를 safeArea라고 정의한다.(안전 영역 계산을 빠르게 하기 위함이다.)

combinations의 각 경우에 대해서 bfs(spreadVirus)를 수행한다. 처음 바이러스가 담겨 있는 배열을 queue로 생각하며 이를 하나씩 빼면서 상하좌우로 이동하는 것으로 생각하며, 바이러스가 이동했다면 이를 다시 배열에 담아서 이 배열의 크기가 0이 될 때까지 반복하도록 했다. 그리고 이 때마다 spreadCount를 하나씩 증가하면서 처음 0인 칸에서 얼마나 바이러스가 펴졌는지 체크하도록 한다.

그리고 최종적으로는 safeArea-spreadCount-3으로 안전영역의 크기를 구한다.(-3은 0에다가 벽을 3개 세웠기 때문이다.)

이렇게 모든 경우의 수에 대해 탐색을 하면서 maxVal을 업데이트해 최댓값을 구하도록 한다.

문제링크:

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

문제:

풀이방법:

 연산자를 계산하는 방법으로 주로 스택을 사용하기 때문에 스택을 사용하고, 수식의 갯수가 3개이므로 최대 6가지 조합이 가능하기 때문에 브루트 포스 방법을 사용해서 모든 케이스에 대해 계산을 하고 그 중 최대값을 찾는 방법을 사용한다.

 우선 정규표현식과 itertools의 permutations을 사용해서 입력받은 expression에 대해서 숫자와 수식을 분리해내고, 연산자들의 우선순위를 만든다.

 생성된 우선순위별로 숫자와 연산자들을 스택에 넣고, 연산자가 현재 해당하는 우선순위의 연산자라면 숫자 스택에서 두 개를 빼고, 연산자 스택에서 하나를 빼서 연산을 하고 다시 숫자 스택에 넣도록 한다.

 이 과정을 우선순위와 연산자별로 계속 반복해서 하고 이 중 max 값을 찾아서 반환하도록 한다.

문제링크:

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

문제:

풀이방법:

여러가지 푸는 방법이 있겠지만, 가장 단순하면서 쉬운 방법을 사용하고자 한다. 브루트 포스 방식으로 가능한 모든 경우의 수를 만들고 그 중에서 해당하는 조건을 찾는 방법으로 했다.

 우선 python의 itertools의 permutation을 사용해서 모든 경우의 수를 만든다. 그리고 각 조건에 맞는지 확인을 하는데, 조건의 길이와 다르면 바로 False로 가도록 하고, 길이가 같다면 그 때 조건을 비교하도록 한다.

 이렇게 조건에 맞는 경우를 찾았다면 중복을 방지하기 위해서 set으로 값을 넣도록 한다.

문제링크:

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