[백준/Python] 10798번 : 세로읽기

시간 제한	메모리 제한	문제 티어	정답 비율
1 초	256 MB	브론즈 I	53.044%

📜 문제

아직 글을 모르는 영석이가 벽에 걸린 칠판에 자석이 붙어있는 글자들을 붙이는 장난감을 가지고 놀고 있다. 

이 장난감에 있는 글자들은 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’부터 ‘9’이다. 영석이는 칠판에 글자들을 수평으로 일렬로 붙여서 단어를 만든다. 다시 그 아래쪽에 글자들을 붙여서 또 다른 단어를 만든다. 이런 식으로 다섯 개의 단어를 만든다. 아래 그림 1은 영석이가 칠판에 붙여 만든 단어들의 예이다. 

A A B C D D
a f z z 
0 9 1 2 1
a 8 E W g 6
P 5 h 3 k x

<그림 1>

한 줄의 단어는 글자들을 빈칸 없이 연속으로 나열해서 최대 15개의 글자들로 이루어진다. 또한 만들어진 다섯 개의 단어들의 글자 개수는 서로 다를 수 있다. 

심심해진 영석이는 칠판에 만들어진 다섯 개의 단어를 세로로 읽으려 한다. 세로로 읽을 때, 각 단어의 첫 번째 글자들을 위에서 아래로 세로로 읽는다. 다음에 두 번째 글자들을 세로로 읽는다. 이런 식으로 왼쪽에서 오른쪽으로 한 자리씩 이동 하면서 동일한 자리의 글자들을 세로로 읽어 나간다. 위의 그림 1의 다섯 번째 자리를 보면 두 번째 줄의 다섯 번째 자리의 글자는 없다. 이런 경우처럼 세로로 읽을 때 해당 자리의 글자가 없으면, 읽지 않고 그 다음 글자를 계속 읽는다. 그림 1의 다섯 번째 자리를 세로로 읽으면 D1gk로 읽는다. 

그림 1에서 영석이가 세로로 읽은 순서대로 글자들을 공백 없이 출력하면 다음과 같다:

Aa0aPAf985Bz1EhCz2W3D1gkD6x

칠판에 붙여진 단어들이 주어질 때, 영석이가 세로로 읽은 순서대로 글자들을 출력하는 프로그램을 작성하시오.

 

📥입력

총 다섯줄의 입력이 주어진다. 각 줄에는 최소 1개, 최대 15개의 글자들이 빈칸 없이 연속으로 주어진다. 주어지는 글자는 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’부터 ‘9’ 중 하나이다. 각 줄의 시작과 마지막에 빈칸은 없다.

 

📤출력

영석이가 세로로 읽은 순서대로 글자들을 출력한다. 이때, 글자들을 공백 없이 연속해서 출력한다. 

 

💡풀이

참고로 나는 모든 문제에서 입력값을 받을 때 무조건 sys.stdin.readline() 을 사용한다. 이유는 input()과 이 둘은 기능상으로는 큰 차이가 없지만, 속도 차이에서는 sys.stdin.readline()이 압도적으로 빠르기 때문이다. 따라서 시간 초과 안나기 위해 sys.stdin.readline()을 선호한다.

 

이번 문제에서는 말 그대로 세로로 읽으면 되기 때문에 먼저 문자열들을 입력받아서 string_list 한 곳에다가 모아둔다. 예를들어 

 

AABCDD
afzz
09121
a8EWg6
P5h3kx

 

이렇게 입력했다면 string_list = ['AABCDD', 'afzz', '09121', 'a8EWg6', 'P5h3kx'] 이렇게 될 것이다.

 

여기서 몇몇 사람들은 이 문제가 2차원 배열 문제인데 왜 2차원 배열을 안만드는지에 대해 궁금증을 가질 것이다.

그렇지만 결국 문자열은 iterable하기 때문에 2차원 배열처럼 인덱스로 꺼내어서 쓸 수 있으므로 이대로 써도 된다.(즉, 각각의 문자열들을 리스트 안에 있는 각각의 리스트들이라 생각하면 된다.)

 

이제 입력했으면 이중 반복문을 통해서 세로읽기 logic에 맞게 출력을 하면 된다.

중요한 점은 어떤 문자열 길이는 6이고, 어떤 문자열 길이는 4인 등 각각 다르므로 그 중 최대 문자열 길이를 저장하고, 바깥 반복문을 최대 문자열 길이 기준으로 설정해서 반복을 하는 것이다. 여기서 해당 인덱스가 없어 문자 출력을 못하는 문자열을 만났을 때는 try, except 구문과 continue를 통해서 생략하고 다음 문자열로 넘어가는 식으로 코드를 작성했다.

 

내가 작성한 정답 코드는 아래와 같다.

import sys

string_list = [None] * 5
max_length = 0

for i in range(5):
  string_list[i] = sys.stdin.readline().rstrip()
  if len(string_list[i]) > max_length:
    max_length = len(string_list[i])

for j in range(max_length):
  for k in range(5):
    try:
      print(string_list[k][j], end='')
    except:
      continue​

 

아, 물론 다른 사람들 풀이처럼 애초에 string_list안에 None이 아닌 0으로 15개를 만들고, 조건문을 통해서 0을 만났을 때 continue 하는 식으로 코드 작성하는 것도 좋은 방법이다.

 

이 문제를 풀면서 'list 안에 있는 문자열들 중 최대 문자열의 길이를 시간복잡도를 줄이면서 출력할 수 있을까?'라고 궁금해서 찾아봤다.

https://www.geeksforgeeks.org/python-longest-string-in-list/

 

Python | Longest String in list - GeeksforGeeks

 

 

여기에는 내가 사용한 루프 방법도 있고, max, key 사용, lambda 사용 등 여러가지 방법이 있었다. 하지만 거의 다 시간 복잡도가 O(n)이거나 sorted()로 사용하는 방법은 O(n)이었고, 내가 사용한 루프 방법은 보조 공간이 O(1)이라 이 방법이 더 효율적이었다.