[BOJ] 23253번 - 자료구조는 정말 최고야

BOJ 23253번, 자료구조는 정말 최고야

 

 

자료구조 중 스택에 대해 공부하였다.

 

스택이란, 쉽게말해 선입후출이 적용되는 자료 구조를 말한다.

리스트에 `.append()`를 통해 데이터를 삽입하면, 그 데이터는 리스트의 맨 앞에 추가된다.
반면 `.pop()`을 통해 데이터를 삭제하면, 순서를 지정하는 것이 아니한 경우 리스트의 맨 뒤부터 데이터가 삭제된다.
이러한 스택 구조의 개념을 BOJ 문제 풀이를 통해 응용해보고자 했다.

 

그리하여 찾은 것이 백준 online judge의 23253번, '자료구조는 정말 최고야'였다.

 

문제 설명

찬우는 스택을 배운 뒤 자료구조 과목과 사랑에 빠지고 말았다.
자료구조 과목만을 바라보기로 다짐한 찬우는 나머지 과목의 교과서 N권을 방 구석에 M개의 더미로 아무렇게나 쌓아 두었다. 하지만 중간고사가 다가오자 더 이상 자료구조만 공부할 수는 없었고, 결국 찬우는 팽개쳤던 나머지 과목의 교과서를 정리하고 번호순으로 나열하려 한다.
 N권의 교과서는 각각 1부터 N까지의 번호가 매겨져 있다. 찬우는 각 더미의 맨 위에 있는 교과서만 꺼낼 수 있으며, 반드시 교과서를 꺼낸 순서대로 나열해야 하기 때문에 번호순으로 나열하기 위해서는 1번, 2번, … N−1번, N번 교과서 순으로 꺼내야 한다. 교과서를 올바르게 나열할 수 없다면 중간고사 공부를 때려치겠다는 찬우를 위해 번호순으로 나열할 수 있는지 여부를 알려주는 프로그램을 작성해 주자.

입력

첫째 줄에 교과서의 수 N, 교과서 더미의 수 M이 주어진다.
둘째 줄부터 2×M줄에 걸쳐 각 더미의 정보가 주어진다.
 i번째 더미를 나타내는 첫 번째 줄에는 더미에 쌓인 교과서의 수 k_i 가 주어지며, 두 번째 줄에는 k_i 개의 정수가 공백으로 구분되어 주어진다.
각 정수는 교과서의 번호를 나타내며, 아래에 있는 교과서의 번호부터 주어진다.
교과서의 번호는 1부터 N까지의 정수가 한 번씩만 등장한다.

출력

올바른 순서대로 교과서를 꺼낼 수 있다면 Yes를, 불가능하다면 No를 출력한다.

 

14번의 시도와 Pypy 사용이라는 우회적인 방법을 통해 겨우 성공했고, 이후 다시 5차례의 시도 끝에 Python으로 문제 풀이를 성공했다.

결론적으로 말하자면, 해당 문제를 푸는 데 있어 스택에 대한 개념은 응용한 것이 없었다. 되려 스택에 얽매여 `append()`, `pop()`을 활용하려 했던 것이, 이 문제를 푸는 시간을 지연시키기만 했다.

하지만, 해당 문제 풀이가 아무런 효용이 없었던 것은 아니었다.

 

 

해당 문제 풀이 과정에서 내가 알게된, 혹은 느낀 바는 다음과 같다.

 

 

 

시간복잡도

 

이미 기존에 BOJ의 골드 이상의 문제를 풀어보며, 시간초과로 인해 오답 처리를 받은 경우가 많았다.
당시에는 시간복잡도를 줄이기위한 다른 방법을 고안해내지 못해, 풀이를 후일로 미뤄두기만 하였다.

 

하지만 해당 문제는, 골드도 아닌 실버5였던지라, 오기가 발동하여 시간을 단축하여 마침내 문제를 해결해보고 방법을 끊임없이 강구하였다.
 

결과 얻은 시간 단축 방법을 몇가지 정리하였다.

• `sys.stdin.readline()` 활용

`input()`을 대체하여 사용하면, 입력에 소요되는 시간을 절약할 수 있다.

 

• 불필요한 계산 제거

불필요한 변수를 선언하고, 거기에 계산식을 늘린다면 그만큼 시간복잡도는 늘어날 수밖에 없다. 더불어 불필요한 변수의 선언은 메모리까지 많이 잡아먹게 된다.

 

• 과도한 Loop문의 사용

 이미 Loop문은 한번 사용된 순간부터 해당 데이터의 크기 만큼의 시간을 늘리게 된다. 그런데 그 Loop문을 이중, 삼중으로 사용하게 된다면, 시간복잡도는 그에 따라 곱절, 혹은 그 이상으로 늘어나게 되는 것이다.
 

이에, 특히 BOJ 문제 등과 같이 데이터가 억단위를 넘어가는 경우에는 과도한 시간이 요구될 수밖에 없다.

 

그러므로 Loop문의 사용은 가능한 줄이고, 대신 더 빠르게 연산을 수행하는 방법에 대하여 고민해보아야 한다.

 

• 여러 알고리즘에 대한 학습
       

앞서 `for`, `while`과 같은 루프문을 줄여야한다고 했는데, 그 방법으로 가장 좋은 것은 여러 알고리즘에 대한 학습이다.

 

일전에 소수 구하기와 관련된 문제를 풀어본 적이 있었다. 하지만, `에라토스테네스의 체`를 알지 못한다면 결코 시간복잡도 문제를 해결할 수가 없는 문제였다.

 

해당 23253번 문제를 해결함에 있어서, 타 알고리즘에 대한 학습은 직접적인 관련은 없었다.

다만, 여러 알고리즘을 학습해두면 문제에 대한 접근 방법을 찾고, 이에 풀이함에 있어 보다 수월해 질 수 있음을 느꼈다.

더불어 시간복잡도 이슈를 해결하기 위해, 여러 알고리즘에 대한 학습이 필수적이라는 것을 다시금 느낀다.

 

• `.sort(by=lambda ~~~)`

  - 람다 함수를 통해 2차원 리스트 내의 리스트에 대한 정렬을 실행할 수 있다.
  -`lambda x : len(x)`를 통해 리스트 크기별로 정렬할 수 있다.
  -`lambda x : (리스트명)[a]`를 통해 내부 리스트의 a번째 인덱스 크기에 따라 정렬할 수 있다.

아래의 코드들은 해당 23253번 문제에 대한 풀이들이다.

 

 

 

import sys

a,b = map(int,sys.stdin.readline().split())
lst1=[]
lst2=[]
for i in range(b):
    sys.stdin.readline()
    lst1.append(list(map(int,sys.stdin.readline().split())))

find = 1
escape = 0
while True:
    for i in range(b):
        try:
            if find == lst1[i][-1]:
                lst1[i].pop()
                find += 1
                break
        except:
            lst1.sort(reverse=True)
            b -= 1
            break
    escape += 1
    if find == a+1:
        print("Yes")
        break
    if escape > find:
        print("No")
        break

 

모든 책의 배열을 그대로 재현한 뒤, 위에서부터 하나하나 책을 찾고자 했다.

단순한 생각과는 달리 코드는 복잡했다.

그리고 반복되는 Loop 구조를 통해, 시간초과 판정은 어렵지 않게 예측할 수 있었다.

 

import sys

a,b = map(int,sys.stdin.readline().split())

lst = []

for i in range(b):

    input()

    lst.append(list(map(int,sys.stdin.readline().split())))

lst.sort(key=lambda x : len(x), reverse=True)

find = 0

for i in range(len(lst)):

    res = lst[i].copy()

    res.sort(reverse=True)

    if lst[i] == res:

        find += 1

    else:

        print("No")

if find == len(lst):

    print("Yes")

생각을 바꾸어, 먼저 입력된 리스트를 복사하였다.

복사한 리스트를 내림차순 정렬한 것이 원래 리스트의 모양과 같은 지를 확인하였다.

단 하나라도 내림차순으로 입력되지 리스트가 존재한다면, 쉽사리 답을 찾을 수 있으리라 생각했다.

나름 괜찮은 방법이라 생각했지만, Pypy를 사용하고나서야 겨우 시간초과 이슈를 해결할 수 있었다.

 

하지만, Pypy가 아닌 Python을 통해 문제를 풀고싶었다.

 

한가지 묘수가 떠올랐다.

 

a,b = map(int,input().split())
c = 1
for i in range(b):
    input()
    lst=list(map(int,input().split()))
    if c == 0:
        pass
    else:
        res = lst.copy()
        res.sort(reverse=True)
        if lst != res:
            c = 0
        else:
            c = 1
print("Yes") if c==1 else print("No")

굳이 입력받은 리스트들을 받아서 저장해야할까?

입력받은 리스트가 내림차순이면 pass, 그게 아니라면 답은 찾은 것이다.

 

이러한 일련의 과정을 거치고 나서야, 비로소 Python으로 문제를 풀이하는데 성공하였다.