[BOJ] 1316번 그룹 단어 체커

BOJ 1316번 그룹 단어 체커

문제를 보자마자 든 생각은 받은 문자열을 정렬해서 비교하면 되겠구나 생각했다.
그런데 아스키코드 순이 아니라, 문자가 발견된 순서대로 정렬을 하는 방법을 몰라서 일단 2중 loop로 풀었다.

풀이

N = int(input())
answer = N

for i in range(N):
  inputStr = input()
  c = 0

  while c != len(inputStr):
    cnt = inputStr.count(inputStr[c]) 
    
    if inputStr[c:c+cnt] == inputStr[c]*cnt: 
      c += cnt
    else: 
      answer -= 1
      break
  
print(answer)

2중 loop라서 최악의 경우에 O(n^2)...

다른 사람의 풀이를 보니 python sorted 함수에 키를 잘 활용했다.

다른 풀이

result = 0
for i in range(int(input())):
    word = input()
    if list(word) == sorted(word, key=word.find):
        result += 1
print(result)

체크할 것

1. range() 안에 input()으로 코드를 줄일 수 있다.
2. sorted()의 key를 적절히 활용하자.

sorted()

파이썬의 기본 내장 라이브러리의 함수 중 하나
기본적으로는 오름차순으로 반환한다. reverse = True 값을 주면 내림차순으로 정렬할 수 있다.

key값으로도 정렬 가능하다.
보통은 lambda 함수를 많이 사용한다.

예시

1. string

   • testStr = 'This is a test string and happy new year'
     result = sorted(testStr.split(), key = str.lower)
     print(result)

     ['a', 'and', 'happy', 'is', 'new', 'string', 'test', 'This', 'year']

   • word = 'helloworld'
     print(sorted(word, key = word.find))

     ['h', 'e', 'l', 'l', 'l', 'o', 'o', 'w', 'r', 'd']

2. 객체

   • student = [
         ('alice', 23),
         ('sophia', 24),
         ('john', 18)
     ]
     print(sorted(student, key = lambda x: x[1]))

     [('john', 18), ('alice', 23), ('sophia', 24)]