https://www.acmicpc.net/problem/2866
2866번: 문자열 잘라내기
첫 번째 줄에는 테이블의 행의 개수와 열의 개수인 R과 C가 주어진다. (2 ≤ R, C ≤ 1000) 이후 R줄에 걸쳐서 C개의 알파벳 소문자가 주어진다. 가장 처음에 주어지는 테이블에는 열을 읽어서 문자
www.acmicpc.net
Code
import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))){
val bw = BufferedWriter(OutputStreamWriter(System.out))
val (N, C) = readLine().split(" ").map { it.toInt() }
//val table = MutableList(N){readln()} // 하나하나 타이핑하면 ㄱㅊ 근데 복붙하면 터지네?
val table: MutableList<String> = mutableListOf();
repeat(N){
val str = readLine()
table.add(str)
}
val colTable = setCol(table, C)
bw.write("${countLen(colTable, N, C)}")
bw.flush()
bw.close()
}
fun setCol(table: MutableList<String>, C: Int): MutableList<String>{
val colTable = mutableListOf<String>()
for (i in 0 until C){
val temp = table.map{it[i]}.joinToString("")
colTable.add(temp)
}
return colTable
}
fun countLen(colTable: MutableList<String>, N: Int, C: Int): Int{
var count = 0
for (i in 1 .. N){
val tempSet = mutableSetOf<String>()
colTable.forEach{
val temp = it.substring(i,N)
tempSet.add(temp)
}
if (tempSet.size != C) break
count++
}
return count
}이게 내가 선택한 정답이고, 여기까지 도달하기까지의 과정은 아래와 같다.
import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))){
val bw = BufferedWriter(OutputStreamWriter(System.out))
val (N, C) = readLine().split(" ").map { it.toInt() }
//val table = MutableList(N){readln()} // 하나하나 타이핑하면 ㄱㅊ 근데 복붙하면 터지네?
val table: MutableList<String> = mutableListOf();
repeat(N){
val str = readLine()
table.add(str)
}
val colTable = setCol(table, C)
bw.write("${countLen(colTable, N, C)}")
bw.flush()
bw.close()
}
/*
// 타임아웃 나는 방법
fun stringCutter(table: MutableList<String>, N:Int, C: Int): Int {
var cnt = 1
while (true){
val set = mutableSetOf<String>()
for (i in 0..C-1){
var str = ""
for (j in cnt..N-1)
str += table[j][i]
set.add(str)
}
if (set.size != C) return cnt
cnt++
}
}
*/
/*
//1차적으로 체크 후 전체 체크 => 여전히 타임아웃
fun stringCutter(table: MutableList<String>, N:Int, C: Int): Int {
var cnt = 0
while (true){
cnt++
if (firstCheck(table, C, cnt)) continue
val set = mutableSetOf<String>()
for (i in 0..C-1){
var str = ""
for (j in cnt..N-1)
str += table[j][i]
set.add(str)
}
if (set.size != C) return cnt
}
}
fun firstCheck(table: MutableList<String>, C: Int, cnt: Int): Boolean{
val test = mutableListOf<Char>()
for (i in 0..C-1){
if (test.contains(table[cnt][i])) return false
test.add(table[cnt][i])
}
return true
}
*/
/*
// 이진탐색으로 확인. => 타임아웃
fun binarySearch(table: MutableList<String>, N:Int, C: Int): Int{
var fir = 1
var end = N
var mid = (fir + end)/2
while (true){
//println("fir = $fir, mid = $mid, end = $end")
if (mid == fir || mid == end) return mid -1
if (init(table, N, C, mid)){ // 같은게 존재함
end = mid
if ((fir + end) / 2 == mid) mid = (fir + end) / 2 + 1
else mid = (fir + end) / 2
}else{ // 같은게 존재하지 않음
//if (mid == fir || mid == end) return mid -1
fir = mid
if ((fir + end) / 2 == mid) mid = (fir + end) / 2 + 1
else mid = (fir + end) / 2
}
}
}
fun init(table: MutableList<String>, N:Int, C: Int, mid: Int): Boolean{
val set = HashSet<String>()
if (!isFirstLetterSame(table, C, mid)) return false // 같은게 존재한다면 밑에내용을 실행. 아니라면 바로 보냄.
for (i in 0..C-1){
var str = ""
for (j in mid-1..N-1)
str += table[j][i]
set.add(str)
}
//println(set.toString())
if (set.size != C) return true
return false
}
fun isFirstLetterSame(table: MutableList<String>, C: Int, mid: Int): Boolean{
val set = HashSet<Char>()
for (i in 0..C-1){
set.add(table[mid-1][i])
}
if (set.size != C) return true
return false
}
*/
fun setCol(table: MutableList<String>, C: Int): MutableList<String>{
val colTable = mutableListOf<String>()
for (i in 0 until C){
val temp = table.map{it[i]}.joinToString("")
colTable.add(temp)
}
return colTable
}
fun countLen(colTable: MutableList<String>, N: Int, C: Int): Int{
var count = 0
for (i in 1 .. N){
val tempSet = mutableSetOf<String>()
colTable.forEach{
val temp = it.substring(i,N)
tempSet.add(temp)
}
if (tempSet.size != C) break
count++
}
return count
}첫번째 사고의 과정은 일종의 브루트 포스이다.
매번 맨 위부분을 잘라내고, 아랫부분을 string으로 만들어서 체크하는 방법이었다.
예를 들자면
abc
def
ghi
jkl
이 있다고 생각하자
첫번째 cycle에는 dgj, ehk, fil을 만들고 비교하는 것이다. 다음에는 gj, hk, il을 만들어서 비교하는 방식으로 진행했다.
결과는 당연하게도 타임아웃.
시간을 줄이고자 고안한 두번째 아이디어가 각 문장의 맨 첫번째 글자를 체크하는 것이다.
예를 들어 abc, def, ghi가 있다면 a, d, g를 비교하는 것이다.
만약 이것이 다르다면 밑에부분을 보지 않아도 당연히 같을 수 없다.
그러므로 맨 앞부분을 보고 같다면 아래를 비교하고 아니라면 바로 다음 줄을 검사하는 방법이다.
하지만 이것도 타임아웃.
여기서 들게 된 생각은 윗부분부터 탐색하는 것은 너무 느린 방법이라는 것이다.
세번째 방법은 이분탐색이다.
위에서부터 하나씩 탐색하는 것이 아닌, 이분탐색을 사용해서 비교해나가는 것이다.
배열의 중간부터 시작했을때, 만약 아래 부분이 전부 같다면, 시작점을 더 위로 움직이고, 전부 같지 않다면 시작점을 더 아래로 움직이는.
전형적인 이분탐색을 사용했다.
결과는 타임아웃.
탐색하는 속도를 높였는데도 왜 타임아웃이 날까 생각했다.
네번째 방법은 세로로 string을 만드는 과정을 단 한번만 하는것 이다.
이분탐색이든, 위에서부터 탐색이든 탐색이 진행되면 1회 탐색마다 모든 string을 만들어가며 검사를 진행했다. 이렇게 만들어가며 진행하는 과정이 시간이 오래 걸리는 것이 아닐까 라는 생각을 하였다.
그래서 입력된 값을 처음부터 세로로 만들고, 해당 값을 슬라이스 하여 비교하는 방식을 사용했다.
비교하는 방식은 하나씩 비교하는것 보다 set을 사용해서 전부 집어넣은 다음 총 갯수를 확인하는 방식을 사용했다. set의 중복이 불가능하다는 특성을 활용한 것이다.
이제 보니까 MutableSet보다는 HashSet을 쓸껄 그랬다. 이게 좀 더 빠른뎀
결과는 통과.
드디어 통과했다.
제일 빡치는건 C++로 3번째 방법을 사용한 내친구는 통과 했다는거...
Kotlin이 C++보다 느리긴 한가보다 젠장