[백준 20437번] 문자열 게임 2

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

 

<수정전>

T = gets.chomp.to_i
for i in 0...T
  alphabet = Array.new(26, 0)
  message = gets.chomp.to_s
  count = gets.chomp.to_i

  if count == 1
    puts [1,1].join(" ")
    next
  end
  length = message.length
  for j in 0...length
    alphabet[message[j].ord - 97] += 1
  end
  min = 999999
  max = -1
  for j in 0...length
    cnt = 1
    if alphabet[message[j].ord - 97] < count
      next
    end

    for k in j + 1...length
      if message[j] == message[k]
        cnt += 1
      end
      if cnt == count
        min = [min, (k - j + 1)].min
        max = [max, (k - j + 1)].max
        break
      end
    end

  end

  if min == 999999 || max == -1
    puts -1
  else
    puts [min, max].join(" ")
  end

end

 

<수정 후 1>

T = gets.chomp.to_i

T.times do
  message = gets.chomp
  n_count = gets.chomp.to_i

  if n_count == 1
    puts "1 1"
    next
  end

  length = message.length
  min_length = Float::INFINITY
  max_length = -Float::INFINITY

  ('a'..'z').each do |char|
    position = []

    message.chars.each_with_index do |mess, index|
      position << index if mess == char
    end

    if position.size < n_count
      next
    end

    (0..position.size - n_count).each do |i|
      length = position[i + n_count - 1] - position[i] + 1
      min_length = [min_length, length].min
      max_length = [max_length, length].max

    end
  end

  if min_length == Float::INFINITY || max_length == -Float::INFINITY
    puts -1
  else
    puts [min_length,max_length].join(' ')
  end
end

 

<수정 후 2>

T = gets.chomp.to_i

for i in 0...T
  message = gets.chomp.to_s
  count = gets.chomp.to_i

  if count == 1
    puts "1 1"
    next
  end

  positions = Hash.new { |h, k| h[k] = [] }  # 각 문자의 위치 저장

  # 각 문자의 등장 인덱스를 저장
  message.chars.each_with_index do |char, idx|
    positions[char] << idx
  end

  min = 999999
  max = -1

  # 각 문자에 대해 최소, 최대 길이 계산
  positions.each do |char, indices|
    next if indices.length < count  # 등장 횟수가 count보다 적으면 무시

    # 투 포인터처럼 count만큼 떨어진 위치를 확인하여 길이 계산
    for j in 0...(indices.length - count + 1)
      length = indices[j + count - 1] - indices[j] + 1
      min = [min, length].min
      max = [max, length].max
    end
  end

  if min == 999999 || max == -1
    puts "-1"
  else
    puts "#{min} #{max}"
  end
end

 

 

처음에는 시간 초과가 날 것 같았지만, 직접 실행해보니 예상대로 이중 for 문을 사용한 방식에서는 시간 초과가 발생했다. 그래서 알파벳별 등장 위치를 한 번에 저장한 뒤, 이를 활용해 필요한 구간을 빠르게 찾아가는 방식으로 코드를 수정했다.

이 과정에서 Hash를 활용하면 시간 복잡도를 줄일 수 있다는 점을 다시 한번 깨달았다.
이 문제 덕분에 한 단계 성장할 수 있었던 것 같다. 정말 ‘갓 문제’다!