CodeDrive

문제:

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

- push X: 정수 X를 큐에 넣는 연산이다.

- pop : 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

- size : 큐에 들어있는 정수의 개수를 출력한다.

- empty : 큐가 비어있으면 1, 아니면 0을 출력한다.

- front : 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

- back : 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력:

첫째 줄에 주어지는 명령의 수 N (1<=N<=2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력:

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

풀이방법:

python의 queue 기능을 사용할 수 있었지만 최근에 알게 된 collections의 deque를 사용해서 풀었다. deque에서 append는 list와 같이 동작을 하고, popleft와 같은 경우에는 맨 앞의 값을 빼는 역할을 수행한다.

문제링크:

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

문제:

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬으 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다.

지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력:

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력:

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

풀이방법:

visited 배열과 bfs를 이용해서 섬의 개수를 세도록 한다.

우선 visited 배열을 만들고, 이를 countLand라는 함수에게 넘겨준다. countLand에서는 주어진 지도를 반복문으로 반복하면서 방문하지 않은 땅이라면 bfs 함수로 들어갈 수 있도록 하며, 이 때마다 count를 하나씩 늘려주는 역할을 한다.

bfs는 일반적인 bfs 함수와 동일하고, 다른점이 있다면 이 문제에서는 대각선까지도 이동이 가능하기 때문에 더 많은 상황을 고려해 줘야 한다.

문제링크:

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

문제:

풀이방법:

 효율적으로 풀어야 하는 문제이기 때문에 O(N^2) 방법으로는 시간초과에 걸릴 것이다. 따라서 투 포인터를 사용하는 슬라이딩 윈도우를 사용해서 풀었다. 

 우선 앞에서부터 뒷 포인터를 이동시키면서 모든 보석을 포함할 때까지 이동한다. 모든 보석을 포함하게 된다면 앞 포인터를 움직여서 가장 앞에 존재했던 보석을 뺀다. 그래도 모든 보석이 포함되어 있다면 앞 포인터를 움직여서 다시 앞을 빼고, 모든 보석이 포함되어 있지 않다면 뒷 포인터를 움직여서 다시 모든 보석을 포함시킬 때까지 움직인다. 

이 과정을 반복하면서 가장 짧은 길이의 포인터들을 저장해두고 최종적으로 출력하도록 한다.

문제링크:

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

문제:

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 정수 N(1<=N<=500,000)이 주어진다.

출력:

첫째 줄에 남게 되는 카드의 번호를 출력한다.

풀이방법:

빠른 입출력을 위해서 collections의 deque를 사용했다. 스택과 큐의 기능을 한번에 사용할 수 있다.

문제링크:

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

문제:

풀이방법:

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

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

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

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

문제링크:

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

문제:

풀이방법:

규칙 중 4를 구현하는 것이 핵심인 문제다.

 solution함수는 1,4,7 입력이 들어온다면 왼쪽 엄지손가락을 사용하고, 해당 번호로 left를 이동시키고, 3,6,9가 들어온다면 오른쪽 엄지손가락을 사용하고 right를 이동시킨다. 이제 2,5,8,0이 들어오는 경우 leftDistance와 rightDistance를 사용해서 거리를 계산한다. 더 작은 쪽의 엄지손가락으로 이동을 하고, 만약 같다면 hand의 우선순위에 따라 움직이도록 한다.

 leftDistance는 입력을 해야하는 숫자가 2,5,8,0일 때, 왼쪽 엄지손가락과 거리를 계산하는 함수다.

만약 이전 왼쪽 엄지 손가락이 2,5,8이고 입력해야 할 숫자가 0이라면 각 케이스마다 거리를 return 하게 만들고, 나머지는 두 수의 차를 3으로 나눈 몫을 반환하도록 한다. 왼쪽 엄지 손가락이 1,4,7에 있다면 이를 가운데 키패드로 옮겨주고 leftDistance로 재귀적으로 거리를 계산하도록 만든다. 이제 나머지 케이스인 0에 있거나, 초기 상태인 *에 있던 경우에 대해서만 거리를 계산해주면 된다.

 rightDistance로 leftDistance와 비슷하게 계산을 하도록 한다.

문제링크:

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

문제:

세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 설 수는 없다.

세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. 둘째 줄에 검색하고 싶은 단어가 주어진다. 이 길이는 최대 50이다. 문서와 단어는 알파벳 소문자와 공백으로 이루어져 있다.

출력:

첫째 줄에 중복되지 않게 최대 몇 번 등장하는지 출력한다.

풀이방법:

브루트 포스 방법으로 문서에서 함수를 찾는 방법을 사용했다. 이 때 함수를 찾았다면 함수의 길이만큼 인덱스를 이동시키고, 그렇지 않으면 1을 증가시켰다.

문제링크:

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

문제:

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 Pn 이라고 한다.

P1 IOI

P2 IOIOI

P3 IOIOIOI

Pn IOIOI...OI (O가 N개)

I과 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 Pn이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1<=N<=1,000,000 , 2N+1 <= M <= 1,000,000)

출력:

S에 Pn이 몇 군데 포함되어 있는지 출력한다.

풀이방법:

Pn은 I와 O가 교대로 나오는 문자열이다. 따라서 index로 비교해서 IOI 패턴을 만족하는지 확인하고 이렇게 연속된 횟수를 세고 N과 일치할 경우 answer를 1 증가시킨다.

문제링크:

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

문제:

준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -2^62보다 크거나 같고, 2^62보다 작거나 같다.

준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다.

입력:

첫째 줄에 준규가 가지고 있는 숫자 카드의 개수 N (1<=N<=100,000)이 주어진다. 둘째 줄부터 N개 줄에는 숫자 카드에 적혀있는 정수가 주어진다.

출력:

첫째 줄에 준규가 가장 많이 가지고 있는 정수를 출력한다.

풀이방법:

 숫자를 입력받으면서 HashTabel을 만들고, 이를 item 리스트로 만들면서 조건에 맞게 정렬을 하면 된다.

문제링크:

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

문제:

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자.

- 긴급전화 : 911

- 상근 : 97 625 999

- 선영 : 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.

입력:

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1<=t<=50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1<=n<=10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화 번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

출력:

각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

풀이방법:

 이전에 프로그래머스에서 이 문제를 풀었었지만, 그 때에는 단순히 반복문을 사용해서 풀었다면 이번에는 문자열에서 비교하는 자료구조인 Trie를 사용하도록 한다.

 정보를 담을 Node 클래스와 이 Node들로 이루어진 Trie 클래스를 사용한다. Node의 key에는 알파벳, char 하나의 값이 들어가고, terminate는 이 Node가 마지막인지, 즉 string의 마지막인지를 나타내는 boolean 값이다. children은 더 이동할 수 있는 곳을 나타낸다.

 함수로는 insert와 search 두 개가 있다. insert로 전화번호를 넣어주고 search로 일관성을 파악하도록 한다.

문제링크:

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