22.11.12 / 문자열, 백트래킹

1316 그룹 단어 체커

나의 풀이

n = int(input())
group_count = n
for _ in range(n):
    s = input()
    group_set = set()
    p_word = ''
    for i in s:
        if p_word == i:
            pass
        elif i not in group_set:
            group_set.add(i)
            p_word = i
        else:
            group_count -= 1
            break
print(group_count)

파이썬은 문자열을 for문으로 한 문자씩 이용할 수 있다.

 

더 나은 풀이

python 코테 준비 기본 복습 3 (velog.io)

부분 내용을 이용하였다.

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

sorted의 key=word.find인자는 정렬을 할 때, 앞에 먼저 나온 알파벳 순으로 정렬한다.

예를 들어, happy와 abab에 대해 봐보자.

happy는 sorted(word, key=word.find)하여도 happy이다. h와 a다음에 p와 y가 나오기 때문이다.

abab는 sorted(word, key=word.find)한 결과는 aabb이다. a다음에 b가 나오기 때문이다.

 

리뷰

sorted의 key=word.find라는 인자를 통해 더 간단히 풀 수 있는 문제였다.
여러 문제를 통해 인자를 여러가지 학습하는 것도 코딩테스트에 도움이 될 것이다.

 

15649 N과 M (1)

나의 풀이

알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제 | ChanBLOG (chanhuiseok.github.io)

백트래킹은 해를 찾아 가는 도중 지금의 경로가 해가 될 것 같지 않으면 경로를 되돌아가는 것이다.
주로 깊이 우선 탐색DFS 에서 사용한다.
DFS는 기본적으로 모든 경로를 탐색하기 때문이다.

간단하게 조건을 확인하고 탐색할 것인지 결정 한다.

파이썬엔 순열 조합을 만들어 주는 from itertools import permutations 함수가 존재한다.

permutations(arr, 개수) 꼴

from itertools import permutations

n, m = map(int, input().split())

permutation = list(permutations([x+1 for x in range(n)], m))
permutation.sort()

for i in permutation:
    for j in i:
        print(j, end=' ')
    print()

더 나은 풀이

[백준] 15649번 N과 M(1) / 파이썬(python) (tistory.com)

n,m = list(map(int,input().split()))
 
s = []
 
def dfs():
    if len(s)==m:
        print(' '.join(map(str,s)))
        return
    
    for i in range(1,n+1):
        if i not in s:
            s.append(i)
            dfs()
            s.pop()
 
dfs()

풀어주신 해당 풀이에서는 DFS를 통해 풀이되었다. 출제자의 의도도 이것과 가까울 것이다. (DFS와 백트래킹 이용)

' '.join(list)를 통해 문자열을 합칠 수 있다.

리뷰

from itertools import permutations 함수를 몰랐을 때는 문제가 너무 막막했다.
결론은 파이썬은 존재하는 함수를 많이 알아두는 것이 유용하다.
하지만, 해당 함수를 몰랐다면 순열을 구현해서라도 문제를 푸는 것이 맞았을 것이다.

---

본인은 삼성 SSAFY를 준비하며 문제를 풀고 있었다.

SSAFY 에서 FAQ를 통해 SW Expert Academy의 문제를 풀어볼 것을 요하고 있으므로,

이 게시글 이후로는 그 문제들 위주로 풀어보려한다.