2866번: 문자열 잘라내기

문제 출처 : https://www.acmicpc.net/problem/2866

2866번: 문자열 잘라내기

언어 : Kotlin

 

문제 설명 :

R개의 행과 C개의 열로 이루어진 테이블이 입력으로 주어진다. 이 테이블의 원소는 알파벳 소문자이다.
각 테이블의 열을 위에서 아래로 읽어서 하나의 문자열을 만들 수 있다. 예제 입력에서

dobarz
adatak

 

이 주어지는 경우 "da", "od", "ba", "at", "ra", "zk"와 같이 6개의 문자열들이 만들어지게 된다.

만약 가장 위의 행을 지워도 테이블의 열을 읽어서 문자열이 중복되지 않는다면, 가장 위의 행을 지워주고, count의 개수를 1 증가시키는, 이 과정을 반복한다. 만약 동일한 문자열이 발견되는 경우, 반복을 멈추고 count의 개수를 출력 후 프로그램을 종료한다.

테이블이 주어질 경우 count의 값을 구해보자.

 

입력 :

첫 번째 줄에는 테이블의 행의 개수와 열의 개수인 R과 C가 주어진다. (2 ≤ R, C ≤ 1000)

이후 R줄에 걸쳐서 C개의 알파벳 소문자가 주어진다. 가장 처음에 주어지는 테이블에는 열을 읽어서 문자열을 만들 때, 동일한 문자열이 존재하지 않는 입력만 주어진다.

 

출력 :

문제의 설명과 같이 count의 값을 출력한다.

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 256MB

 

입출력 예 :

입력	출력
2 6 dobarz adatak	0
3 4 alfa beta zeta	2
4 6 mrvica mrvica marica mateja	1

 

풀이 : 

가장 위에 있는 행을 지울때, 세로 문자열들을 읽으면 그들 중 중복되는 값이 있는지 판별하는 문제.

예를 들어 문제에서 준 "dobarz" "abatak"의 경우,

d	o	b	a	r	z
a	b	a	t	a	k
↓	↓	↓	↓	↓	↓
a	b	a	t	a	k

 

첫번째부터 세로로 읽으면 da, ob, ba, at, ra, zk가 나온다.

가장 위의 행인 "dobarz"를 지웠을때 세로로 읽으면 a, b, a, t, a, k가 나온다.

이 때, 중복되는 문자열이 존재하지 않으면 cnt++하고 반복하라는 것인데, a가 3번이나 나와 중복되어 cnt = 0으로 종료되는 것이다.

 

다른 예제로 다시 한번 보자.

m	r	v	i	c	a
m	r	v	i	c	a
m	a	r	i	c	a
m	a	t	e	j	a
↓	↓	↓	↓	↓	↓
m	r	v	i	c	a
m	a	r	i	c	a
m	a	t	e	j	a
↓	↓	↓	↓	↓	↓
m	a	r	i	c	a
m	a	t	e	j	a

 

예제 3번이다.

가장 위의 행을 지우고 시작하면, mmm, raa, vrt, iie, ccj, aaa가 나오고 중복이 없기에 cnt = 1이 된다.

가장 위의 행을 한 번 더 지운다. mm, aa, rt, ie, cj, aa가 나오게 되고 aa가 중복되므로 cnt는 증가하지 않고 종료되어 cnt = 1로 마무리 된다.

 

이를 바탕으로 구현을 하면 된다.

먼저 아예 세로로 읽은 문자열들로 리스트를 만든 뒤, 가장 처음 문자열은 지우고 시작하므로 substring으로 문자열 시작부분부터 자르면서 set에 자른 문자열을 넣어 크기를 비교하면 된다.

중복된 값이 존재한다면 크기가 주어졌던 c에서 벗어나게 될 것이므로.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val (r, c) = readLine().split(" ").map { it.toInt() }
    val input = MutableList<String>(r) { readLine() }
    val list = mutableListOf<String>()
    var cnt = 0

    for (i in 0 until c) {
        list.add(input.map { it[i] }.joinToString(""))
    }

    for (i in 1 .. r) {
        val temp = mutableSetOf<String>()
        list.forEach {
            temp.add(it.substring(i - 1, r))
        }

        if (temp.size == c) cnt++ else break
    }

    bw.write("${cnt - 1}")
    bw.flush()
    bw.close()
}